《编译原理与实践第四章答案.doc》由会员分享，可在线阅读，更多相关《编译原理与实践第四章答案.doc（6页珍藏版）》请在三一文库上搜索。
1、The exercises of Chapter FourGrammar: A f (A) A |&Assume we have lookahead of one token as in the example on p. 144 in the text book. Procedure A()if (LookAhead() ( ) thenCall Expect( ( )Call A()Call Expect () )Call A()elseif (LookAhead() ), $) thenreturn()else/* error */fifiendGiven the grammarstat
2、ement f assign-stmt|call-stmt| other assign-stmtfidentifier :=exp call-stmtfidentifier (exp-list)SolutionFirst, convert the grammar into following forms:statementf identifier :=exp | identifier (exp-list)| otherThen, the pseudocode to parse this grammar:Procedure statementBeginCase token of( identif
3、er : match(identifer);case token of( := : match(:=);exp;( (: match();exp-list;match();else error;endcase(other: match(other);else error; endcase;end statement4.7 aGrammar: A ( A ) A |&First(A)=(, Follow(A)=$,)bSee theorem on P.178 in the text book1. First( n First =2. & Fist(A), First(A)n Follow(A)=
4、 both conditions of the theorem are satisfied, hence grammar is LL(1)Consider the following grammar:lexp t atom|listatomt nu mber|ide ntifierlistt(lexp-seq)lexp-seqtlexp, lexp-seq|lexpa. Left factor this grammar.b. Construct First and Follow sets for the nonterminals of the resulting grammar.c. Show
5、 that 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.lexptatom|listatom tnumber|identifierlistt(lexp-seq)lexp-seqt lexp lexp-seqlexp-seq T, lexp-seq|
6、&b.First(lexp)=number, identifier, (First(atom)=number, identifierFirst(list)=( First(lexp-seq)= number, identifier, (First(lexp- seq )=, g Follow(lexp)=, $, Follow(atom)= , $, Follow(list)= , $, Follow(lexp-seq)=$, Follow(lexp- seq )=$,c. According to the defination of LL(1) grammar (Page 155), the
7、 resulting grammar is LL(1) as each table entry has at most one product ion as show n in (d).d. The LL(1) pars ing table for the result ing grammarMN,Tnu mberide ntifer()$LexplexpT atomlexp t atomlexpT listAtomatom t numberatom t identifierListlistt(lexp-seq)Lexp-seqlexp-seq t lexp lexp-seqlexp-seq
8、t lexp lexp-seqlexp-seq t lexp lexp-seqLexp-seq lexp-seqTlexp-seqt , lexp-seqlexp-seq te. The actions of the parser give n the stri ng (a,(b,(2),(c)Parsing stackIn put stri ngActio n$ lexp-seq(a,(b,(2),(c)$ 1lexp-seqT lexp lexp-seq$ lexp-seq lexp(a,(b,(2),(c)$lexpT list$ lexp-seq list(a,(b,(2),(c)$l
9、ist t (lexp-seq)$ lexp-seq ) le-seq (a,(b,(2),(c)$ :match$ lexp-seq ) lexpeqa,(b,(2),(c)$lexp-seqT lexp lexp-seq$ lexp-seq ) lexpeq lexpa,(b,(2),(c)$lexpT atom$ lexp-seq ) lexpeq atoma,(b,(2),(c)$ :atom t identifier$ lexp-seq ) lexpeq identifiera,(b,(2),(c)$match$ lexp-seq ) lexpeq ,(b,(2),(c)$lexp-
10、seq T, lexp-seq$ lexp-seq ) le-seq ,(b,(2),(c)$match$ lexp-seq ) le-seq(b,(2),(c)$lexp-seqT lexp lexp-seq$ lexp-seq ) lexpeq lexp(b,(2),(c)$lexpT list$ lexp-seq ) lexpeq list(b,(2),(c)$list t (lexp-seq)$ lexp-seq ) lexpeq )lexpeq(b,(2),(c)$match$ lexp-seq ) lexpeq )lexpeqb,(2),(c)$lexp-seqT lexp lex
11、p-seq$ lexp-seq ) lexpeq )lexpeq lexpb,(2),(c)$lexpT atom$ lexp-seq ) lexpeq )lexpeq atomb,(2),(c)$atom t identifier$ lexp-seq ) lexpeq )lexpeq identifierb,(2),(c)$match$ lexp-seq ) lexpeq )lexpeq ,(2),(c)$lexp-seq T, lexp-seq$ lexp-seq ) lexpeq )lexpeq,(2),(c)$match$ lexp-seq ) lexpeq )lexpeq(2),(c
12、)$lexp-seqT lexp lexp-seq$ lexp-seq ) lexpeq )lexpeq lexp(2),(c)$lexpT list$ lexp-seq ) lexpeq )lexaeq list(2),(c)$list t (lexp-seq)$ lexp-seq ) lexpeq )lexpeq )lexpeq(2),(c)$match$ lexp-seq ) lexpeq )lexpeq )lexpeq2),(c)$lexp-seqT lexp lexp-seq$ lexp-seq ) lexpeq )lexpeq )lexpeq lexp2),(c)$lexpT at
13、om$ lexp-seq ) lexpeq )lexpeq )lexpeq atom2),(c)$atom t number$ lexp-seq ) lexpeq )lexpeq )lexpeq number2),(c)$:match$ lexp-seq ) lexpeq )lexpeq exp-seq )，(c)$lexp-seq T$ lexp-seq ) lexpeq )lexpeq )，(c)$match$ lexp-seq ) lexpeq )lexpeq )，(c)$lexp-seq T$ lexp-seq ) lexpeq )，(c)$match$ lexp-seq ) lexp
14、eq ，(c)$lexp-seq T, lexp-seq$ lexp-seq ) le-qeq,，(c)$match$ lexp-seq ) le-qeq(c)$lexp-seqT lexp lexp-seq $ lexp-seq ) lexpeq lexp(c)$lexpT list$ lexp-seq ) lexpeq list(c)$:list t (lexp-seq)$ lexp-seq ) lexpeq )lexpeq(c)$match$ lexp-seq ) lexpeq )lexpeqc)$lexp-seqT lexp lexp-seq$ lexp-seq ) lexpeq )l
15、expeq lexpc)$lexpT atom$ lexp-seq ) lexpeq )lexpeq atomc)$atom t identifier$ lexp-seq ) lexpeq )lexpeq identifierc)$match$ lexp-seq ) lexpeq )lexpeq )$lexp-seq T$ lexp-seq ) lexpeq )$match$ lexp-seq ) lexpeq )$lexp-seq T$ lexp-seq )$match$ lexp-seq $lexp-seq T$accept4.10 aLeft factored grammar:1. de
16、clt type Vat2. typehnt3. typefloat4. var-listidfentifier B5. B t , vbst6. B t / irsl(L/ecl - 7) = ：i 1 it )/lrsttype)- b7r.v/(iiil)/) Jim. lloul ；Firxi (var list) = F$t(iderM 1 Iler) = idenl i tier 卜irst(出)一尸A7r,v/(s)一 占；I iiodecl :Folloulype = Firi/fvar- list) = idenijllci, Folk忒ywr - list) = Foliw
17、(fi/ecl) = J$iFnllowB = /- x ；ir /v =刖4.10 c】 Afr.s7(ini)C /rA/(tloai) 0 f irst (Jc 卜 irst 6 )二 02.社总 /7rA7(/J)/7r.s7(/?)r Fo/kw(再) 0Both condition* of the theoietm are satisfied gpimmiu is LL( 1)dMN, Tintfloatide ntifierJ$decl11type23var-list4B56eSample in put stri ng: int x, y, zPars ing stackIn p
18、utActio n$ declint x, y, z $decl t type var-list$ var-list typeint x, y, z $type t int$ var-list intint x, y, z $match int$ var-listx, y, z $var-list t identifer B$ B ide ntifierx, y, z $match ide ntifier w/ x$ B,y, z $B t , var-list$ var-list ,y, z $match ,$ var-listy, z $var-list t identifer B$ B
19、ide ntifiery, z $match ide ntifier w/ y$ B,z $B t , var-list$ var-list ,z $match ,$ var-listz $var-listidentifer B$ B ide ntifierz $match ide ntifier w/ z$ B$B$Accept4.12 a. Can an LL(1) grammar be ambigous Why or Why notb. Can an ambigous grammar be LL(1) Why or Why notc. Must an un ambigous gramma
20、r be LL(1) Why or Why notSolutio nDefin ati on of an ambiguous grammar : A grammar that gen erates a stri ng with two disti net parse trees. (Page 116)Defination of an LL(1) grammar : A grammar is an LL(1) grammar if the assoeiatied LL(1) parsing table has at most one priduet ion in each table en tr
21、y.a. An LL(1) grammar can not be ambiguous, since the defination implies that an unambiguous parse can be con structed using the LL(1) pars ing tableb. An ambiguous grammar can not be LL(1) grammar, but can be convert to be ambiguous by using disambiguati ng rule.c. An unambiguous grammar may be not
22、 an LL(1) grammar, since some ambiuous grammar can be parsed using LL(K) table, where K1.Left recursive grammars can not be LL(1):Consider a grammar with a production AA p with symbol t in its first set. IF A is on the top of thestack and the current look-ahead token is t, A will be popped off the s
23、tack and then p will be pushed onto the stack followed by A. A will aga in be the top of the stack and the look-ahead toke n will still be t, so it will repeat again, and again, infinitely, or until you get a stack overflow.Note: The first set for the recursive producti on will have a non-empty in tersecti on with the first set for the term in ati ng producti on, which will lead to a con flict whe n creat ing the LL(1) table.