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

1、The exercises of Chapter Four4、2Grammar: 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() ( ) thenCall Expect( ( )Call A()Call Expect () ')Call A()elseif (LookAhead() ) , $) then return()else/* error */fifiend4、3 Given

2、the grammar statement assign-stmt|call-stmt| other assign-stmt identifier :=exp call-stmt identifier (exp-list)SolutionFirst, convert the grammar into following forms:statement identifier :=exp | identifier (exp-list)| other Then, the pseudocode to parse this grammar:Procedure statementBeginCase tok

3、en of( identifer : 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)=$,)4、7 bSee theorem on P、178 in the text book1. First( First = 2. Fist(A), F

4、irst(A) Follow(A)= both conditions of the theorem are satisfied, hence grammar is LL(1)4、9 Consider the following grammar:lexp atom|list atom number|identifier list (lexp-seq) lexp-seq lexp, lexp-seq|lexpa、Left factor this grammar 、b、Construct First and Follow sets for the nonterminals of the result

5、ing grammar 、c、Show 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、 lexp atom|list atom number|identifier list (lexp-seq) lexp-seq lexp lexp- se

6、q ' lexp- seq ' , lexp-seq|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 ' )=$, c、According to

7、 the defination of LL(1) grammar (Page 155), the resulting grammar 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()$Lexplexp atomlexp atomlexp listAtomatom numberatom identifierListlist (lexp-seq)Lexp-s

8、eqlexp-seq lexp lexp- seq 'lexp-seq lexp lexp- seq 'lexp-seq lexp lexp- seq 'Lexp-seq 'lexp- seq' lexp- seq ' , lexp-seqlexp- seq ' e、 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 

9、9;$ lexp- seq ' lexp(a,(b,(2),(c)$lexp list$ lexp- seq ' list(a,(b,(2),(c)$list (lexp-seq)$ lexp- seq ' ) le-xspeq (a,(b,(2),(c)$match$ lexp- seq ' ) le-xspeqa,(b,(2),(c)$lexp-seqlexp lexp- seq '$ lexp- seq ' ) le-xspeq ' lexpa,(b,(2),(c)$lexp atom$ lexp- seq ' ) le-x

10、speq ' atoma,(b,(2),(c)$atom identifier$ lexp- seq ' ) le-xspeq ' identifiera,(b,(2),(c)$match$ lexp- seq ' ) xlpe-seq ',(b,(2),(c)$lexp- seq' , lexp-seq$ lexp- seq ' ) le-xspeq ,(b,(2),(c)$match$ lexp- seq ' ) le-xspeq(b,(2),(c)$lexp-seqlexp lexp- seq '$ lexp- se

11、q ' ) le-xspeq ' lexp(b,(2),(c)$lexp list$ lexp- seq ' ) le-xspeq ' list(b,(2),(c)$list (lexp-seq)$ lexp- seq ' ) le-xspeq ' )lex-speq(b,(2),(c)$match$ lexp- seq ' ) le-xspeq ' )lex-speqb,(2),(c)$lexp-seqlexp lexp- seq '$ lexp- seq ' ) le-xspeq ' )lex-speq

12、 ' lexpb,(2),(c)$lexp atom$ lexp- seq ' ) le-xspeq ' )lex-speq ' atomb,(2),(c)$atom identifier$ lexp- seq ' ) le-xspeq ' )lex-speq ' identifierb,(2),(c)$match$ lexp- seq ' ) le-xspeq ' )lex-speq ',(2),(c)$lexp- seq' , lexp-seq$ lexp- seq ' ) le-xspeq &

13、#39; )lex-speq,(2),(c)$match$ lexp- seq ' ) le-xspeq ' )lex-speq(2),(c)$lexp-seqlexp lexp- seq '$ lexp- seq ' ) le-xspeq ' )lex-speq ' lexp(2),(c)$lexp list$ lexp- seq ' ) le-xspeq ' )lex-speq ' list(2),(c)$list (lexp-seq)$ lexp- seq ' ) le-xspeq ' )lex-sp

14、eq ' )lex-speq(2),(c)$match$ lexp- seq ' ) le-xspeq ' )lex-speq ' )lex-speq2),(c)$lexp-seqlexp lexp- seq '$ lexp- seq ' ) le-xspeq ' )lex-speq ' )lex-speq ' lexp2),(c)$lexp atom$ lexp- seq ' ) le-xspeq ' )lex-speq ' )lex-speq ' atom2),(c)$atom numb

15、er$ lexp- seq ' ) le-xspeq ' )lex-speq ' )lex-speq ' number2),(c)$match$ lexp- seq ' ) le-xspeq ' )lepx-seq ' )lex-speq '),(c)$lexp- seq'$ lexp- seq ' ) le-xspeq ' )lex-speq '),(c)$match$ lexp- seq ' ) le-xspeq ' )lex-speq '),(c)$lexp- seq&

16、#39;$ lexp- seq ' ) le-xspeq '),(c)$match$ lexp- seq ' ) le-xspeq ',(c)$lexp- seq' , lexp-seq$ lexp- seq ' ) le-xspeq,(c)$match$ lexp- seq ' ) le-xspeq(c)$lexp-seqlexp lexp- seq'$ lexp- seq ' ) le-xspeq ' lexp(c)$lexp list$ lexp- seq ' ) le-xspeq ' lis

17、t(c)$list (lexp-seq)$ lexp- seq ' ) le-xspeq ' )lex-speq(c)$match$ lexp- seq ' ) le-xspeq ' )lex-speqc)$lexp-seqlexp lexp- seq'$ lexp- seq ' ) le-xspeq ' )lex-speq ' lexpc)$lexp atom$ lexp- seq ' ) le-xspeq ' )lex-speq ' atomc)$atom identifier$ lexp- seq &

18、#39; ) le-xspeq ' )lex-speq ' identifierc)$match$ lexp- seq ' ) le-xspeq ' )lex-speq ')$lexp- seq'$ lexp-seq' ) lex-pseq ')$match$ lexp- seq ' ) le-xspeq ')$lexp- seq'$ lexp- seq ' )$match$ lexp- seq '$lexp- seq'$accept4、10 aLeft factored gramm

19、ar:1、 decl type var-list2、 type int3、type float4、var-list identifier B5、B , var-list6、B 4、10 b4、 10 c4、10 dMN, Tintfloatidentifier$decl11type23var-list4B564、10 eSample input string: int x, y, zParsing stackInputAction$ declint x, y, z $decl type var-list$ var-list typeint x, y, z $type int$ var-list

20、 intint x, y, z $match int$ var-listx, y, z $var-list identifer B$ B identifierx, y, z $match identifier w/ x$ B, y, z $B , var-list$ var-list , y, z $match ,$ var-listy, z $var-list identifer B$ B identifiery, z $match identifier w/ y$ B, z $B , var-list$ var-list , z $match ,$ var-listz $var-list

21、identifer B$ B identifierz $match identifier w/ z$ B$B $Accept4、 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 grammar that generates a st

22、ring with two distinct parsetrees、 (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 canbe 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 unamb