10/9/2009110/9 Discussion SessionContext-Free GrammarsExam ReviewRecall: Context-Free Grammars• Regular Expressions are great ... but not good enough to capture a programming language!– Example: RE for balanced pairs of parentheses– L = {"()", "(())", ...} (same # of "(" and ")“)• CFGs subsume REs:– (a | b)* same as S-> aS | bS |Generating Strings from CFGs• S -> aS | bS |– Means “we can replace S with aS, bS, or e”– Generate (derive) string “abba”• S => aS => abS => abbS => abbaS => abba• S -> ( S ) |– Matching pairs of ( )– S => ( S ) => ( ( S ) ) => ( ( ) )Describing Grammars• Example 1:– S -> abS | a• Example 2: – S -> aSb |• Example 3:– S -> aS | T– T -> bT | U– U -> cU |Describing Grammars• Example 1: S -> abS | a– (ab)*a• Example 2: S -> aSb | – Any # of a’s followed by the same number of b’s– anbn– RE?• Example 3: S -> aS | T, T -> bT | U, U -> cU | – Any # of a’s, followed by any # of b’s, followed by any # of c’s– a*b*c*Deriving Strings• Example 1: S -> abS | a• Example 2: S -> aSb |• Example 3: S -> aS | T, T -> bT | U, U -> cU |10/9/20092Deriving Strings• 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 PLs• Basic Arithmetic Expressions• Boolean ExpressionsWorking Toward PLs• Basic Arithmetic Expressions– E -> a | b | c | E + E | E-E | E*E | (E)• Boolean Expressions– S -> S and S | S or S | (S) | true | falseProperties of Grammars - Ambiguity• Ambiguity– Multiple leftmost or rightmost derivations• Leftmost/Rightmost Derivation– When deriving string, always derive ___-most non-terminal first• Example: S -> S and S | S or S | (S) | true | false• Derive ((true and false) or (false and true and true))Leftmost Derivation• Leftmost:• S => • ( S ) => • (S or S) => • ((S) or S) => • ((S and S) or S) => • ((true and S) or S) => • ((true and false) or S) => • ((true and false) or (S)) => • ((true and false) or (S and S)) =>• ((true and false) or (S and S and S)) =>• ((true and false) or (false and S and S)) =>• ((true and false) or (false and true and S)) =>• ((true and false) or (false and true and true))Properties of Grammars - Ambiguity• Is our grammar for basic boolean expressions ambiguous?– If so, what is an example?10/9/20093Properties of Grammars - Ambiguity• Is our grammar for basic boolean expressions ambiguous?– Yes; Consider the leftmost derivation of “true and true and true”:• S => S and S => true and S => true and S and S => true and true and S => true and true and true• S => S and S => S and S and S => true and S and S => true and true and S => true and true and trueDesigning Grammars• Tip 1: Use recursive productions to generate an arbitrary number of symbols:– A -> aA | (zero or more As)– B -> bB | b (one or more Bs)• Tip 2: Use separate nonterminals to consider disjoint parts of a language, then combine with a production:– G -> AB– A -> aA | (grammar for a*bb*)– B -> bB | bDesigning Grammars• Tip 3: To generate languages with matching, balanced, or related numbers of symbols, write productions which generate strings from the middle:– S -> aSb (anbn)– What about anb2n?Designing Grammars• Tip 3: To generate languages with matching, balanced, or related numbers of symbols, write productions which generate strings from the middle:– S -> aSb (anbn)– What about anb2n? S -> aSbb• Try to rewrite “balanced” strings in terms of their power, e.g. anbnDesigning Grammars• Tip 4: For a language that’s a union of other languages, use separate non-terminals for each part of the union, then combine:– {an (bm| cm), m > n >= 0}EQUIVALENT TO– {an bm, m > n >= 0} U {an cm, m > n >= 0} • What is the grammar for this expression?Designing Grammars• What is the grammar for this expression?– S -> T | U– T -> aTb | Tb | b (but it’s AMBIGUOUS!)– U -> aUc | Uc | c (consider abbb)• Fixing ambiguity is a later topic … any thoughts?10/9/20094Practice Designing Grammars1. axby, where x = y2. axby, where x > y3. axby, where x = 2y4. axbyaz, where z = x+y5. All strings of a and b that are palindromes.6. All strings of a and b that include substring “baa”.7. All strings of a and b with an odd number of a’sand an odd number of b’s.Practice Designing Grammars1. axby, where x = y1. S -> aSb |2. axby, where x > y1. S -> aL2. L -> aL | aLb | 3. axby, where x = 2y1. S -> aaSb |Practice Designing Grammars4. axbyaz, where z = x+y1. S -> aSa | L2. L -> bLa | 5. All strings of a and b that are palindromes.1. S -> aSa | bSb | L2. L -> a | b |Practice Designing Grammars6. All strings of a and b that include substring “baa”.1. S -> LbaaL2. L -> aL | bL | (all strings over a,b)7. All strings of a and b with an odd number of a’sand an odd number of b’s.1. S -> EaEbE | EbEaE2. E -> EaEaE | EbEbE | SS | (even # of a’s &
View Full Document
Unlocking...