资源描述:
《编译原理与实践 第四章 答案.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、TheexercisesofChapterFour4.2Grammar:A→(A)A
2、εAssumewehavelookaheadofonetokenasintheexampleonp.144inthetextbook.ProcedureA()if(LookAhead()∈{‘(‘})thenCallExpect(‘(‘)CallA()CallExpect(‘)’)CallA()elseif(LookAhead()∈{‘)‘,$})thenreturn()else/*error*/fifiend4.3Giventhegrammarstatement→assign-stmt
3、
4、call-stmt
5、otherassign-stmt→identifier:=expcall-stmt→identifier(exp-list)[Solution]First,convertthegrammarintofollowingforms:statement→identifier:=exp
6、identifier(exp-list)
7、otherThen,thepseudocodetoparsethisgrammar:ProcedurestatementBeginCasetokenof(identifer:match(identifer);casetokenof(:=:
8、match(:=);exp;((:match(();exp-list;match());elseerror;endcase(other:match(other);elseerror;endcase;endstatement4.7aGrammar:A→(A)A
9、εFirst(A)={(,ε}Follow(A)={$,)}4.7bSeetheoremonP.178inthetextbook1.First{(}∩First{ε}=Φ2.ε∈Fist(A),First(A)∩Follow(A)=Φbothconditionsofthetheoremaresatisfied,henc
10、egrammarisLL(1)4.9Considerthefollowinggrammar:lexp→atom
11、listatom→number
12、identifierlist→(lexp-seq)lexp-seq→lexp,lexp-seq
13、lexpa.Leftfactorthisgrammar.b.ConstructFirstandFollowsetsforthenonterminalsoftheresultinggrammar.c.ShowthattheresultinggrammarisLL(1).d.ConstructtheLL(1)parsingtableforth
14、eresultinggrammar.e.ShowtheactionsofthecorrespondingLL(1)parser,giventheinputstring(a,(b,(2)),(c)).[Solution]a.lexp→atom
15、listatom→number
16、identifierlist→(lexp-seq)lexp-seq→lexplexp-seq’lexp-seq’→,lexp-seq
17、εb.First(lexp)={number,identifier,(}First(atom)={number,identifier}First(list)={(}Firs
18、t(lexp-seq)={number,identifier,(}First(lexp-seq’)={,,ε}Follow(lexp)={,$,}}Follow(atom)={,$,}}Follow(list)={,$,}}Follow(lexp-seq)={$,}}Follow(lexp-seq’)={$,}}c.AccordingtothedefinationofLL(1)grammar(Page155),theresultinggrammarisLL(1)aseachtableentryhasatmostoneproductionasshownin(d).d.TheL
19、L(1)parsingtablefortheresultinggrammarM[N,T]numberidentifer(),$Lexplexp→atomlexp→atomlexp→listAtomatom→numberatom→identifierListlist→(lexp-seq)Lexp-seqlexp-seq→lexplexp-seq’lexp-seq→lexplexp-seq’lexp-seq→lexplexp-seq’Lexp-seq’lexp-seq’→εlexp-seq’→,lexp-seqlexp