編譯原理與實(shí)踐第四章答案

1、The exercises of Chapter FourGrammar: A f (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() $) thenretum()else/* error */fifie

2、nd4 3 Given the grammarstatementf assign-stmt|call-stmt|other assign-stmtf identifier :=exp call-stmtfidentifier (exp-list)SolutionFirst, con vert the grammar into following forms:state me ntf ide ntifier :=exp | ide ntifier (explist)| otherThen, the pseudocode to parse this grammar:Procedure statem

3、entBegi nCase token of(identifer: match(identifer);case token of(:=:match(:=);exp;(:match();exp-list;match();else error;endcase(other: match(other); else error;endcase;end statement4、7aGrammar: A f (A) / &First(A)=(, £ Follow(A)=$,)4、7bSee theorem on P 178 in the text book1. First( n First

4、£ =2. & Fist(A), First(A)n Follow(A)=both conditions of the theorem are satisfied, hence grammar is LL(1)4、9 Consider the following grammar: lexpfatom|list atomfnumber|identifier listf(lexp-seq)lexp-seqflexp, lexp-seq|lexpa、Left factor this grammar 、b、 Con struct First and Follow sets for t

5、he non terminals of the resulti ng grammar c Show that the resulting grammar is LL(1)d、Con struct the LL(1) parsi ng table for the resulti ng grammar 、e、 Show the acti ons of the corresp onding LL(1) parser, give n the in put string (a,(b,(2),(c)Solutiona、lexpfatom|list atomfnumber|identifier listf(

6、lexp-seq)lexp-seqflexp lexp- seq 'lexp-seq ； lexpseq| &b、First(lexp)=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')

7、=$,c According to the defination of LL(1) grammar (Page 155), the resulting grammar is LL(1) as each tableentry has at most one production as shown in (d)、d The LL(1) pars ing table for the result ing grammarMN,Tnu mberide ntifer()$Lexplexp T atomlexp T atomlexp T listAtomatom T numberatom T identif

8、ierListlistT(lexp-seq)Lexp-seqlexp-seq T lexplexp- seq，lexp-seq T lexplexp- seq，lexp-seq T lexplexp seqrLexp-seq 'lexp- seqrt£lexp-seq 'T,lexp-seqlexp- seq' T£e The actions of the parser give n the stri ng (a,(b，(2),(c)Parsing stackIn put stri ngActio n$ lexp-seq(a,(b,),(c)$ 1l

9、exp-seqTlexp lexp- seq*$ lexp-seq r lexp(a,(b,),(c)$lexp T list$ lexp-seq ' list(a,(b,),(c)$list T (lexp-seq)$ lexp-seq ' ) lexpeq (a,(b,),(c)$ 1match$ lexp-seq 1 ) lexpeqa,(b,),(c)$lexp-seqTlexp lexp seq'$ lexp-seq r ) lexpeq 1 lexpa,(b,(2),(c)$lexp T atom$ lexp-seq ' ) lexpeq 1 ato

10、ma,(b,(2),(c)$ :atom T identifier$ lexp-seq ' ) lexpeq 1 identifiera,(b,(2),(c)$match$ lexp-seq r )xp-seq 1,(b,(2),(c)$lexp- seq T, lexp-seq$ lexp-seq 1 ) lexpeq ,(b,),(c)$match$ lexp-seq ' ) lexpeq(b,),(c)$lexp-seqTlexp lexp- seq*$ lexp-seq r ) lexpeq 1 lexp(b,),(c)$lexp T list$ lexp-seq r

11、) lexpeq ' list(b,),(c)$list T (lexp-seq)$ lexp-seq ' ) lexpeq 1 )lexseq(b,(2),(c)$match$ lexp-seq ' ) lexpeq 1 )lexseqb,),(c)$lexp-seqTlexp lexp- seq'$ lexp-seq 1 ) lexpeq 1 )lexpeq 1 lexpb,(2),(c)$lexp T atom$ lexp-seq ' ) lexpeq 1 )lexpeq 1 atomb,(2),(c)$atom T identifier$ lex

12、p-seq ' ) lexpeq 1 )lexpeq 1 identifierb,(2),(c)$match$ lexp-seq r ) lexpeq 1 )lexpeq 1，),(c)$lexp- seq T, lexp-seq$ lexp-seq ' ) lexpeq 1 )lexseq,，),(c)$match$ lexp-seq ' ) lexpeq 1 )lexseq(2),(c)$lexp-seqTlexp lexp- seq*$ lexp-seq ' ) lexpeq 1 )lexpeq 1 lexp(2),(c)$lexp T list$ lex

13、p-seq ' ) lexpeq 1 )lexpeq 1 list(2),(c)$list T (lexp-seq)$ lexp-seq ' ) lexpeq 1 )lexpeq 1 )lexpeq(2),(c)$match$ lexp-seq ' ) lexpeq 1 )lexpeq 1 )lexpeq2),(c)$lexp-seqTlexp lexp seq'$ lexp-seq ' ) lexpeq 1 )lexpeq 1 )lexpeq 1 lexp2),(c)$lexp T atom$ lexp-seq ' ) lexpeq 1 )le

14、xpeq 1 )lexpeq 1 atom2),(c)$atom T number$ lexp-seq ' ) lexpeq 1 )lexpeq 1 )lexpeq 1 number2),(c)$match$ lexp-seq ' ) lexpeq 1 )lexseq r )lexpeq 1)，(c)$lexp- seq Tx$ lexp-seq ' ) lexpeq 1 )lexpeq 1)，(c)$match$ lexp-seq ' ) lexpeq 1 )lexpeq 1)，(c)$lexp- seq Tz$ lexp-seq ' ) lexpeq

15、 1)，(c)$match$ lexp-seq ' ) lexpeq 1,(c)$lexp- seq T, lexp-seq$ lexp-seq ' ) lexpeq,(c)$match$ lexp-seq ' ) lexpeq(c)$lexp-seqTlexp lexp- seqr$ lexp-seq r ) lexpeq 1 lexp(c)$lexp T list$ lexp-seq r ) lexpeq ' list(c)$list T (lexp-seq)$ lexp-seq ' ) lexpeq 1 )lexseq(c)$match$ lexp

16、-seq ' ) lexpeq 1 )lexseqc)$lexp-seqTlexp lexp- seqr$ lexp-seq ' ) lexpeq 1 )lexpeq 1 lexpc)$:lexp T atom$ lexp-seq ' ) lexpeq 1 )lexpeq 1 atomc)$atom T identifier$ lexp-seq ' ) lexpeq * )lexpeq 1 identifierc)$match$ lexp-seq ' ) lexpeq 1 )lexpeq 1)$：lexp- seq Tz$ lexp-seq1 ) lex

17、-seq 1)$match$ lexp-seq ' ) lexpeq 1)$lexp- seq Tx$ lexp-seq f)$match$ lexp-seq r$lexp- seq Tt$accept4、10 aLeft factored grammar:1、decl T type var-list2、type T int3、type T float4、var-list T identifier B5、B T, var-list6、B T e4、10b/ irsl(L/ecl 7) = ： i 1 it)/ trsl(type) /'A(intjo /、帀侄ij(float)

18、 Jim. lloul ；First (var一 list) = F>$t(iderM i Iler) = pdenti tier卜 irsf(出)一尸 A7r,v/一占；I iiofdecl:FolloulypeJ = Firi/fvar- list)二ideriljllcr!Folk ywr list) = Foliw(fi/ecl) = J$iFnllo vABA = / x ； ir /Av =月【JAfr.y/(int) C / float )=0戶 *imf (rCZrJT 伝)=Q2. e e A irsf(/iFfW(甘)c FO/OH (B) =0Boili condi

19、tions of the theorem are istisf沱d n grammar is IJ.( I)_4 10dMN,Tintfloatide ntifierJ$decl11type23var-list4B564、10eSample in put stri ng: int x, y, zPars ing stackIn putActio 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,

20、 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 ide ntifiery, z$match ide ntifier w/ y$B,z$B T, var-list$ var-list,z$match ,$ var-listz$var-list T identifer B$ B ide ntifierz$match ide ntif

21、ier w/ z$B$B“ £$Accept4、12a、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 un ambigous grammar be LL(1)? Why or Why not?Solutio nDefin ati on of an ambiguous grammar: A grammar that gen erates a stri ng with two disti net parse tree

22、s (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 becon structed using the LL(1) pars ing tableb. An ambiguous grammar can not be LL(1) grammar, but can be con vert to be ambiguous by using disambiguating rule c. An unambiguous grammar