Review CMSC 330 Organization of Programming Languages Why should we study CFGs What are the four parts of a CFG How do we tell if a string is accepted by a CFG Context Free Grammars What s a parse tree CMSC 330 Review Leftmost and Rightmost Derivation Example S a SbS A sentential form is a string of terminals and nonterminals produced from the start symbol Inductively The start symbol If A is a sentential form for a grammar where and N and A is a production then is a sentential form for the grammar CMSC 330 3 Another Example cont d Leftmost Derivation S SbS abS aba Rightmost Derivation S SbS Sba aba At every step apply production to leftmost non terminal At every step apply production to rightmost non terminal CMSC 330 4 Ambiguity S a SbS A string is ambiguous for a grammar if it has more than one parse tree Is ababa in this language S SbS abS abSbS ababS ababa String aba Both derivations happen to have the same parse tree A parse tree has a unique leftmost and a unique rightmost derivation Not every string has a unique parse tree Parse trees don t show the order productions are applied In this case we say that A derives in one step which is written as A A leftmost derivation 2 Another leftmost derivation S SbS SbSbS abSbS ababS ababa Equivalent to more than one leftmost or more than one rightmost derivation A grammar is ambiguous if it generates an ambiguous string It s can be hard to see this with manual inspection Exercise can you create an unambiguous grammar for S a SbS CMSC 330 5 CMSC 330 6 1 Are these Grammars Ambiguous 1 S aS T T bT U U cU 2 S T T T Tx Tx x x 3 S SS S Ambiguity of Grammar Example 3 2 different parse trees for the same string 2 distinct leftmost derivations S SS SSS SS S S SS S SS S We need unambiguous grammars to manage programming language semantics CMSC 330 7 More on Leftmost Rightmost Derivations Is the following derivation leftmost or rightmost Tips for Designing Grammars A xA A yA y Zero or more x s One or more y s 2 Use separate non terminals to generate disjoint parts of a language and then combine in a production How about the following derivation S SbS SbSbS SbabS ababS ababa G S AB A aA B bB L G a b 9 Tips for Designing Grammars cont d CMSC 330 10 Tips for Designing Grammars cont d 3 To generate languages with matching balanced or related numbers of symbols write productions which generate strings from the middle anbn n 0 not a regular language S aSb Example S aSb aaSbb aabb anbm m 2n n S aSbb B B bB b 0 The following grammar also works S aSbb B B bB anb2n n 0 S aSbb CMSC 330 8 1 Use recursive productions to generate an arbitrary number of symbols S aS aT aU acU ac There s at most one non terminal in each sentential form so there s no choice between left or right nonterminals to expand CMSC 330 CMSC 330 How about the following S aSbb bS 11 CMSC 330 12 2 Tips for Designing Grammars cont d Tips for Designing Grammars cont d anbman m n 0 m 0 Rewrite as anbmaman which now has matching superscripts two pairs 4 For a language that s the union of other languages use separate nonterminals for each part of the union and then combine Would this grammar work S aSa B Doesn t allow m 0 B bBa ba Corrected S aSa B B bBa an bm cm m n anan The outer are generated first then the inner bmam CMSC 330 13 Can be rewritten as anbm m n ancm m n 0 0 0 CMSC 330 Tips for Designing Grammars cont d Tips for Designing Grammars cont d anbm m n 0 ancm m n 0 anbm m n 0 ancm m n 0 S T U T aTb Tb b U aUc Uc c T generates the first set U generates the second set Will this fix the ambiguity S T U T aTb bT b U aUc cU c What s the parse tree for string abbb Ambiguous CMSC 330 14 It s not amgiguous but it can generate invalid strings such as babb 15 CMSC 330 16 Tips for Designing Grammars cont d CFGs for Languages anbm m n 0 ancm m n 0 Recall that our goal is to describe programming languages with CFGs Unambiguous version We had the following example which describes limited arithmetic expressions S T V T aTb U U Ub b V aVc W W Wc c E a b c E E E E E E E What s wrong with using this grammar It s ambiguous CMSC 330 17 CMSC 330 18 3 Example a b c E E E a E a E E ab E a b c The Issue Associativity E E E E E E a E E a b E a b c Ambiguity is bad here because if the compiler needs to generate code for this expression it doesn t know what the programmer intended So what do we mean when we write a b c In mathematics this only has one possible meaning It s a b c since subtraction is left associative a b c would be the meaning if subtraction was rightassociative Corresponds to a b c Corresponds to a b c CMSC 330 19 Another Example If Then Else CMSC 330 20 Parse Tree 1 stmt assignment if stmt if stmt if expr stmt if expr stmt else stmt Here s are used to denote nonterminals and for productions Consider the following program fragment if x y if x z a 1 else a 2 Note Ignore newlines CMSC 330 Else belongs to inner if 21 Parse Tree CMSC 330 22 Fixing the Expression Grammar Idea Require that the right operand of all of the operators is not a bare expression E E T E T E T T T a b c E Now there s only one parse tree for a b c Exercise Give a derivation for the string a b c Else belongs to outer if CMSC 330 23 CMSC 330 24 4 What if We Wanted Right Associativity Parse Tree Shape Left recursive productions are used for leftassociative operators Right recursive productions are used for rightassociative operators Left The kind of recursion associativity determines the shape of the parse tree left recursion right recursion E E T E T E T T T a b c E Right E T E T E T E T T a b c E CMSC 330 Exercise draw a parse tree for a b c in the prior grammar in which subtraction is right associative 25 A Different Problem 26 Final Expression Grammar How about the string a b c E E T E T T T T P P P a …
View Full Document
Unlocking...