CS 4240, Fall 1999 Homework 2 Solutions ---------------------------------------------------------------------- In Problems 3-5, I add a production Z -> $ so that things work with my my tool which generates the solutions automatically. [c3] 20 1 S->ABBA first: ab der em: 1 follow: $ predict: ab$ 2 A->a first: a der em: 0 follow: ba$ predict: a 3 A-> first: der em: 1 follow: ba$ predict: ba$ 4 B->b first: b der em: 0 follow: ba$ predict: b 5 B-> first: der em: 1 follow: ba$ predict: ba$ 6 Z->S$ first: ab$ der em: 0 follow: predict: ab$ The grammar is not LL(1). (Note that predict(2) U predict(3) != null set) [c4] 20 1 S->aSe first: a der em: 0 follow: e$ predict: a 2 S->B first: bcd der em: 0 follow: e$ predict: bcd 3 B->bBe first: b der em: 0 follow: e$ predict: b 4 B->C first: cd der em: 0 follow: e$ predict: cd 5 C->cCe first: c der em: 0 follow: e$ predict: c 6 C->d first: d der em: 0 follow: e$ predict: d 7 Z->S$ first: abcd der em: 0 follow: predict: abcd The grammar is LL(1). a e b c d $ S 1 0 2 2 2 0 B 0 0 3 4 4 0 C 0 0 0 5 6 0 Z 7 0 7 7 7 0 [c5] 20 In this problem and the next, I use the following abbreviations: E stands for Expr F stands for ExprTail V stands for Var W stands for VarTail m stands for - i stands for id o stands for ( c stands for ) so that it works with my automatic tool. 1 E->mE first: m der em: 0 follow: c$ predict: m 2 E->oEc first: o der em: 0 follow: c$ predict: o 3 E->VF first: i der em: 0 follow: c$ predict: i 4 F->mE first: m der em: 0 follow: c$ predict: m 5 F-> first: der em: 1 follow: c$ predict: c$ 6 V->iW first: i der em: 0 follow: mc$ predict: i 7 W->oEc first: o der em: 0 follow: mc$ predict: o 8 W-> first: der em: 1 follow: mc$ predict: mc$ 9 Z->E$ first: moi der em: 0 follow: predict: moi The grammar is LL(1). m o c i $ E 1 2 0 3 0 F 4 0 5 0 5 V 0 0 0 6 0 W 8 7 8 0 8 Z 9 9 0 9 0 [c6] 20 Stack Action Remaining input -------------------------------------------------------------- Z 9 immiooicc$ $E 3 immiooicc$ $FV 6 immiooicc$ $FWi match mmiooicc$ $FW 8 mmiooicc$ $F 4 mmiooicc$ $Em match mmiooicc$ $E 1 miooicc$ $Em match miooicc$ $E 3 iooicc$ $FV 6 iooicc$ $FWi match iooicc$ $FW 7 ooicc$ $FcEo match ooicc$ $FcE 2 oicc$ $FccEo match oicc$ $FccE 3 icc$ $FccFV 6 icc$ $FccFWi match icc$ $FccFW 8 cc$ $FccF 5 cc$ $Fcc match cc$ $Fc match c$ $F 5 $ $ accept $ [c15] 20 The way Predict works in LL(k) implies uniqueness at each step--there is only one legal parse given the lookahead. An ambiguous grammar must (at some point) have multiple legal-next-steps. LL(k) precludes this. A quick example: 1 S -> A 2 | B 3 A -> x 4 B -> x predict(1) U predict(2) != null set, and that's where multiple parse trees come from.