編譯原理與實踐第四章答案編譯原理與實踐第四章答案編譯原理與實踐第四章答案資料僅供參考文件編號：2022年4月編譯原理與實踐第四章答案版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：TheexercisesofChapterFourGrammar:A→(A)A|εAssumewehavelookaheadofonetokenasintheexampleonp.144inthetextbook.ProcedureA()if(LookAhead()∈{‘(‘})thenCallExpect(‘(‘)CallA()CallExpect(‘)’)CallA()elseif(LookAhead()∈{‘)‘,$})thenreturn()else/*error*/fifiendGiventhegrammar statement→assign-stmt|call-stmt|other assign-stmt→identifier:=exp call-stmt→identifier(exp-list)[Solution] First,convertthegrammarintofollowingforms: statement→identifier:=exp|identifier(exp-list)|other Then,thepseudocodetoparsethisgrammar: Procedurestatement Begin Casetokenof (identifer:match(identifer); casetokenof (:=:match(:=); exp; ((:match((); exp-list; match()); elseerror; endcase (other:match(other); elseerror; endcase; endstatementaGrammar:A→(A)A|εFirst(A)={(,ε}Follow(A)={$,)}bSeetheoremoninthetextbookFirst{(}∩First{ε}=Φε∈Fist(A),First(A)∩Follow(A)=Φbothconditionsofthetheoremaresatisfied,hencegrammarisLL(1)Considerthefollowinggrammar: lexp→atom|list atom →number|identifier list→(lexp-seq) lexp-seq→lexp,lexp-seq|lexpa.Leftfactorthisgrammar.b.ConstructFirstandFollowsetsforthenonterminalsoftheresultinggrammar.c.ShowthattheresultinggrammarisLL(1).d.ConstructtheLL(1)parsingtablefortheresultinggrammar.e.ShowtheactionsofthecorrespondingLL(1)parser,giventheinputstring(a,(b,(2)),(c)).[Solution]a. lexp→atom|list atom →number|identifier list→(lexp-seq) lexp-seq→lexplexp-seq’ lexp-seq’→,lexp-seq|εb. First(lexp)={number,identifier,(} First(atom)={number,identifier} First(list)={(} First(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.TheLL(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-seq’→εe.Theactionsoftheparsergiventhestring(a,(b,(2)),(c))ParsingstackInputstringAction$lexp-seq(a,(b,(2)),(c))$lexp-seq→lexplexp-seq’$lexp-seq’lexp(a,(b,(2)),(c))$lexp→list$lexp-seq’list(a,(b,(2)),(c))$list→(lexp-seq)$lexp-seq’)lexp-seq((a,(b,(2)),(c))$match$lexp-seq’)lexp-seqa,(b,(2)),(c))$lexp-seq→lexplexp-seq’$lexp-seq’)lexp-seq’lexpa,(b,(2)),(c))$lexp→atom$lexp-seq’)lexp-seq’atoma,(b,(2)),(c))$atom →identifier$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’)lexp-seq(b,(2)),(c))$lexp-seq→lexplexp-seq’$lexp-seq’)lexp-seq’lexp(b,(2)),(c))$lexp→list$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-seq→lexplexp-seq’$lexp-seq’)lexp-seq’)lexp-seq’lexpb,(2)),(c))$lexp→atom$lexp-seq’)lexp-seq’)lexp-seq’atomb,(2)),(c))$atom →identifier$lexp-seq’)lexp-seq’)lexp-seq’identifierb,(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-seq→lexplexp-seq’$lexp-seq’)lexp-seq’)lexp-seq’lexp(2)),(c))$lexp→list$lexp-seq’)lexp-seq’)lexp-seq’list(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-seq→lexplexp-seq’$lexp-seq’)lexp-seq’)lexp-seq’)lexp-seq’lexp2)),(c))$lexp→atom$lexp-seq’)lexp-seq’)lexp-seq’)lexp-seq’atom2)),(c))$atom →number$lexp-seq’)lexp-seq’)lexp-seq’)lexp-seq’number2)),(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’)lexp-seq,,(c))$match$lexp-seq’)lexp-seq(c))$lexp-seq→lexplexp-seq’$lexp-seq’)lexp-seq’lexp(c))$lexp→list$lexp-seq’)lexp-seq’list(c))$list→(lexp-seq)$lexp-seq’)lexp-seq’)lexp-seq((c))$match$lexp-seq’)lexp-seq’)lexp-seqc))$lexp-seq→lexplexp-seq’$lexp-seq’)lexp-seq’)lexp-seq’lexpc))$lexp→atom$lexp-seq’)lexp-seq’)lexp-seq’atomc))$atom →identifier$lexp-seq’)lexp-seq’)lexp-seq’identifierc))$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’→ε$$acceptaLeftfactoredgrammar:1.decl→typevar-list2.type→int3.type→float4.var-list→identifierB5.B→,var-list6.B→εbcdM[N,T]intfloatidentifier,$decl11type23var-list4B56eSampleinputstring:intx,y,zParsingstackInputAction$declintx,y,z$decl→typevar-list$var-listtypeintx,y,z$type→int$var-listintintx,y,z$matchint$var-listx,y,z$var-list→identiferB$Bidentifierx,y,z$matchidentifierw/x$B,y,z$B→,var-list$var-list,,y,z$match,$var-listy,z$var-list→identiferB$Bidentifiery,z$matchidentifierw/y$B,z$B→,var-list$var-list,,z$match,$var-listz$var-list→identiferB$Bidentifierz$matchidentifierw/z$B$B→ε$$Accepta.CananLL(1)grammarbeambigousWhyorWhynotb.CananambigousgrammarbeLL(1)WhyorWhynotc.MustanunambigousgrammarbeLL(1)WhyorWhynot[Solution] Definationofanambiguousgrammar:Agrammarthatgeneratesastringwithtwodistinctparsetrees.(Page116) DefinationofanLL(1)grammar:AgrammarisanLL(1)grammariftheassociatiedLL(1)parsingtablehasatmostonepriductionineachtableentry.AnLL(1)grammarcannotbeambiguous,sincethedefinationimpliesthatanunambiguousparsecanbeconstructedusingtheLL(1)parsingtableAnambiguousgrammarcannotbeLL(1)grammar,butcanbeconverttobeambiguousbyusingdisambiguatingrule.Anunambiguousgrammarm