編譯原理與實踐--第四章--答案

1、The exercises of Chapter Four4.2 Grammar: A ( A ) A | Assume we have lookahead of one token as in the example on p. 144 in the text book. Procedure A() if (LookAhead() () then Call Expect() Call A() Call Expect () Call A() else if (LookAhead() ), $) then return() else /* error */ fi fi end 4.3 Given

2、 the grammar statement assign-stmt|call-stmt|otherassign-stmtidentifier:=expcall-stmtidentifier(exp-list)SolutionFirst, convert the grammar into following forms:statement identifier:=exp | identifier(exp-list)|otherThen, the pseudocode to parse this grammar:Procedure statementBeginCase token of( ide

3、ntifer : match(identifer);case token of( := : match(:=); exp;( (: match(); exp-list;match();else error;endcase(other: match(other);else error;endcase;end statement4.7 a Grammar: A ( A ) A | First(A)=(, Follow(A)=$,)4.7 bSee theorem on P.178 in the text book1. First(First=2. Fist(A), First(A) Follow(

4、A)= both conditions of the theorem are satisfied, hence grammar is LL(1)4.9 Consider the following grammar:lexpatom|listatomnumber|identifierlist(lexp-seq)lexp-seqlexp, lexp-seq|lexpa. Left factor this grammar.b. Construct First and Follow sets for the nonterminals of the resulting grammar.c. Show t

5、hat the resulting grammar is LL(1).d. Construct the LL(1) parsing table for the resulting grammar.e. Show the actions of the corresponding LL(1) parser, given the input string (a,(b,(2),(c).Solutiona.lexpatom|listatomnumber|identifierlist(lexp-seq)lexp-seqlexp lexp-seqlexp-seq, lexp-seq|b.First(lexp

6、)=number, identifier, ( First(atom)=number, identifierFirst(list)=( First(lexp-seq)= number, identifier, ( First(lexp-seq)=, , Follow(lexp)=, $, Follow(atom)= , $, Follow(list)= , $, Follow(lexp-seq)=$, Follow(lexp-seq)=$, c. According to the defination of LL(1) grammar (Page 155), the resulting gra

7、mmar is LL(1) as each table entry has at most one production as shown in (d).d. The LL(1) parsing table for the resulting grammarMN,Tnumberidentifer(),$LexplexpatomlexpatomlexplistAtomatomnumberatomidentifierListlist(lexp-seq)Lexp-seqlexp-seqlexp lexp-seqlexp-seqlexp lexp-seqlexp-seqlexp lexp-seqLex

8、p-seqlexp-seqlexp-seq, lexp-seqlexp-seqe. The actions of the parser given the string (a,(b,(2),(c)Parsing stackInput stringAction$ lexp-seq(a,(b,(2),(c)$lexp-seqlexp lexp-seq$ lexp-seq lexp(a,(b,(2),(c)$lexplist$ lexp-seq list(a,(b,(2),(c)$list(lexp-seq)$ lexp-seq ) lexp-seq (a,(b,(2),(c)$match$ lex

9、p-seq ) lexp-seqa,(b,(2),(c)$lexp-seqlexp lexp-seq$ lexp-seq ) lexp-seq lexpa,(b,(2),(c)$lexpatom$ lexp-seq ) lexp-seq atoma,(b,(2),(c)$atomidentifier$ lexp-seq ) lexp-seq identifiera,(b,(2),(c)$match$ lexp-seq ) lexp-seq,(b,(2),(c)$lexp-seq, lexp-seq$ lexp-seq ) lexp-seq ,(b,(2),(c)$match$ lexp-seq

10、 ) lexp-seq(b,(2),(c)$lexp-seqlexp lexp-seq$ lexp-seq ) lexp-seq lexp(b,(2),(c)$lexplist$ lexp-seq ) lexp-seq list(b,(2),(c)$list(lexp-seq)$ lexp-seq ) lexp-seq)lexp-seq(b,(2),(c)$match$ lexp-seq ) lexp-seq)lexp-seqb,(2),(c)$lexp-seqlexp lexp-seq$ lexp-seq ) lexp-seq)lexp-seqlexpb,(2),(c)$lexpatom$

11、lexp-seq ) lexp-seq)lexp-seqatomb,(2),(c)$atomidentifier$ lexp-seq ) lexp-seq)lexp-seqidentifierb,(2),(c)$match$ lexp-seq ) lexp-seq)lexp-seq,(2),(c)$lexp-seq, lexp-seq$ lexp-seq ) lexp-seq)lexp-seq,(2),(c)$match$ lexp-seq ) lexp-seq)lexp-seq(2),(c)$lexp-seqlexp lexp-seq$ lexp-seq ) lexp-seq)lexp-se

12、qlexp(2),(c)$lexplist$ lexp-seq ) lexp-seq)lexp-seqlist(2),(c)$list(lexp-seq)$ lexp-seq ) lexp-seq)lexp-seq)lexp-seq(2),(c)$match$ lexp-seq ) lexp-seq)lexp-seq)lexp-seq2),(c)$lexp-seqlexp lexp-seq$ lexp-seq ) lexp-seq)lexp-seq)lexp-seqlexp2),(c)$lexpatom$ lexp-seq ) lexp-seq)lexp-seq)lexp-seqatom2),

13、(c)$atomnumber$ lexp-seq ) lexp-seq)lexp-seq)lexp-seqnumber2),(c)$match$ lexp-seq ) lexp-seq)lexp-seq)lexp-seq),(c)$lexp-seq$ lexp-seq ) lexp-seq)lexp-seq),(c)$match$ lexp-seq ) lexp-seq)lexp-seq),(c)$lexp-seq$ lexp-seq ) lexp-seq),(c)$match$ lexp-seq ) lexp-seq,(c)$lexp-seq, lexp-seq$ lexp-seq ) le

14、xp-seq,(c)$match$ lexp-seq ) lexp-seq(c)$lexp-seqlexp lexp-seq$ lexp-seq ) lexp-seqlexp(c)$lexplist$ lexp-seq ) lexp-seqlist(c)$list(lexp-seq)$ lexp-seq ) lexp-seq)lexp-seq(c)$match$ lexp-seq ) lexp-seq)lexp-seqc)$lexp-seqlexp lexp-seq$ lexp-seq ) lexp-seq)lexp-seqlexpc)$lexpatom$ lexp-seq ) lexp-se

15、q)lexp-seqatomc)$atomidentifier$ lexp-seq ) lexp-seq)lexp-seqidentifierc)$match$ lexp-seq ) lexp-seq)lexp-seq)$lexp-seq$ lexp-seq ) lexp-seq)$match$ lexp-seq ) lexp-seq)$lexp-seq$ lexp-seq ) )$match$ lexp-seq$lexp-seq$accept4.10 aLeft factored grammar: 1. decl type var-list 2. type int 3. type float

16、 4. var-list identifier B 5. B , var-list 6. B 4.10 b4.10 c4.10 dMN, T int float identifier ,$ decl 1 1 type 2 3 var-list 4 B 5 64.10 eSample input string: int x, y, z Parsing stack Input Action $ decl int x, y, z $ decl type var-list $ var-list type int x, y, z $ type int $ var-list int int x, y, z

17、 $ match int $ var-list x, y, z $ var-list identifer B $ B identifier x, y, z $ match identifier w/ x $ B , y, z $ B , var-list $ var-list , , y, z $ match , $ var-list y, z $ var-list identifer B $ B identifier y, z $ match identifier w/ y $ B , z $ B , var-list $ var-list , , z $ match , $ var-lis

18、t z $ var-list identifer B $ B identifier z $ match identifier w/ z $ B $ B $ $ Accept 4.12 a. Can an LL(1) grammar be ambigous? Why or Why not?b. Can an ambigous grammar be LL(1)? Why or Why not?c. Must an unambigous grammar be LL(1)? Why or Why not?SolutionDefination of an ambiguous grammar: A gra

19、mmar that generates a string with two distinct parse trees. (Page 116)Defination of an LL(1) grammar: A grammar is an LL(1) grammar if the associatied LL(1) parsing table has at most one priduction in each table entry.a. An LL(1) grammar can not be ambiguous, since the defination implies that an unambiguous parse can be constructed using the LL(1) parsing tableb. An ambiguous grammar can not be LL(1) grammar, but can be convert to be ambiguous by using disambiguating rule.c. An unambiguous grammar may be not an LL(1) grammar, since some ambiuous grammar can be parsed using LL(K) table, where