Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Context Free GrammarsCMSC 330Discussion Section2/25/2011The Problem●REs are pretty cool, but they don't capture very many interesting things about PLs●Consider parsing–What can we actually ``parse'' with REs?●Not much!–We need a more powerful set of languages●From a theory perspective, we need a more powerful underlying model (called PDA)More Power!The Solution: CFGs●Key Points:–CFGs subsume REs (part of the Chomsky Hierarchy)●We can represent REs as a CFG–CFGs directly map to string generation–CFGs expressed as a 4 tuple:●Alphabet (AKA Terminals)●Nonterminals●Productions●Start SymbolCFGmanREGetting Down to Business w/CFGs●A toy grammar: S → aS | bS | ●Derive “abba”–S → aS → abS → abbS → abbaS → abba●Equivalent RE?–(a | b) *●Some Utility: S → ( S ) | –What does this grammar do?Describing Grammars●Example 1–S → abS | a–(ab)*a●Example 2–S → aSb | –anbn●Example 3–S → aS | T–T → bT | U–U → cU |–a*b*c*String Derivation●Example 1–S → abS | a–a, ababa●Example 2–S → aSb | –ab, aaabbb●Example 3–S → aS | T–T → bT | U–U → cU |–aabbbbcc, bbcWorking Toward PLsArithmetic Expressions●E → a | b | c | E + E | E - E | E * E | ( E )Boolean Expressions●S → true | false | S and S | S or S | ( S )Finally! Something useful!Derivation PracticeTry leftmost derivations of the following:●((true and false) or (false and true and true))●true and true and trueShow the parse tree for each.Problem : Ambiguity●Restricting derivation to Rightmost or Leftmost, we can consider the ambiguity of a grammar–If a grammar has multiple rightmost or leftmost derivations of the same string, it's ambiguous–Equivalently, if the same string has multiple parse trees, the grammar is ambiguous●Is our boolean expression grammar ambiguous?Designing Grammars 1) axby, where x = yS → aSb | 2) axby, where x > yS → aLL → aL | aLb | 3) axby, where x = 2yS → aaSbDesigning Grammars4) axbyaz, where z = x + yS → aSa | LL → bLa | 5) All strings of {a,b} that are palindromesS → aSa | bSb | LL → a | bGenerating Grammars6) All strings of {a, b} that include substring “baa”S → LbbaLL → aL | bL |7) All strings of {a, b} with an odd # of a's and b'sS → EaEbE | EbEaEE → EaEaE | EbEbE | SS |Photo Credits●Slide 2: –http://www.wchstv.com/abc/homeimprov/timallen.html●Slide 3: –http://haktech.blogspot.com/2010/05/pacman-30th-anniversary.html●Slide
View Full Document
Unlocking...