编译原理第二版第五章答案

第五章第5章自顶向下语法分析 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 练习(P99)1?文法S->aF|(T)T->T,S|S(1)对(a,(a,a)和(((a,a),A,(a)),a)的最左推导。经改写后的文法是否为LL(1)的给出它的预测分析 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 。(4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。对(a,(a,a)的最左推导为：S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))对(((a,a),A,(a)),a)的最左推导为：S=>(T)=>(T,S)=>(S,S)=>((T),S)=>((T,S),S)=>((T,S,S),S)=>((S,S,S),S)=>(((T),S,S),S)=>(((T,S),S,S),S)=>(((S,S),S,S),S)=>(((a,S),S,S),S)=>(((a,a),S,S),S)=>(((a,a),A,S),S)=>(((a,a),A,(T)),S)=>(((a,a),A,(S)),S)=>(((a,a),A,(a)),S)=>(((a,a),A,(a)),a)改写文法为：S->aS->AS->(T)T->SNN->,SNN->￡SaTaAAFIRSTFOLLOW(#,)()N,￡)对左部为N2的产生式可知:FIRST(->,SN2)={,}FIRST(->s)={￡}FOLLOW(N2)={)}{,}n{)}=所以文法是LL⑴的。预测分析表aA()5#S->a->A->(T)T->SN->SN->SNN->s->,SN也可由预测分析表中无多重入口判定文法是LL(1)的。对输入串(a,a)#的分析过程为：步骤状态栈当前字符剩余输入串操作1#S(a,a)#S->(T)2#)T((a,a)#匹配3#)TA,a)#T->SN24#)N2SA,a)#S->a5#)N2aA,a)#匹配6#)N2Ja)#N2->,SN27#)N2S,1a)#匹配8#)N2Sa)#S->a9#)N2aa)#匹配10#)N2)#N2->s11#))#匹配12##可见输入串(a,a)#是文法的句子。2.对下面的文法G:ETTE'E'T+E|￡TTFT，T'TT|￡FTPF，F'TF，|&PT(E)|a|bF(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。⑵证明这个文法是LL(1)的。构造它的预测分析表。构造它的预测下降分析程序【解】(1)由 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 意分析得可推导出&的非终结符表为：各非终结符的FIRST集为：FIRST(E)=FIRST(T)={(a,b,A}FIRST(E，赳})+}￡￡}={+FIRST(T)=FIRST(F)={(a,b,A}FIRST(T，F)IRST(T)U{￡}={(a,b,A￡,}FIRST(F)=FIRST(P)={(a,b,A}FIRST(F，)U*{￡}={*s}FIRST(P)={(a,b,A}???最终求得各非终结符的FIRST集为：FIRST(E)={(a,b,A}FIRST(E，)={￡}FIRST(T)={(a,b,A}FIRST(T，{(=a,b,A,s}FIRST(F)=,a,b,A}FIRST(F，)={￡}FIRST(P)={(a,b,A}各非终结符的FOLLOW集为：FOLLOW(E)={#UFOLLOW(EU{)}FOLLOW(E)=FOLLOW(E)FOLLOW(T)=FOLLOW(T)U(FIRST(E-{')})FOLLOW(E)FOLLOW(T)=FOLLOW(T)FOLLOW(F)=(FIRST(T-{'￡UFOLLOW(T)FOLLOW(F)=FOLLOW(F)UFOLLOW(F')FOLLOW(P)=(FIRST(F-{'dUFOLLOW(F)???最终求得各非终结符的FOLLOW集为：FOLLOW(E)={#)}FOLLOW(E)=#,)}FOLLOW(T)={#,+,)}FOLLOW(T)=#,+,)}FOLLOW(F)={(,a,b，人,#,+,)}FOLLOW(F)=(,a,b,人,#,+,)}FOLLOW(P)={*,(,a,b，人,#,+,)}⑵各产生式的SELECT!为：SELECT(ET)=FIRST(TEIR'ST=T)={(a,b,A}TE'SELECT(E'T+E)=FIRST(+E)={+}SELECT(E'fd)=(FIRST(dd)OLLOW(E)=FOLLOW(E)={#)}SELECT(TTFT')=FIRST(FFHRST)(F)={(a,b,A}SELECT(T'TT)=FIRST{T)=a,b,A}SELECT(T'fd)=(FIR§TdU&F)OLLOW(T)=FOLLOW(T)={#+,)}SELECT(F~PF')=FIRST(PFIR'ST=°)={(,a,b,A}SELECT(F、*F')=FIRSTF*RST(F))={*}SELECT(F')=(FIRSTdUdOLLOW(F)=FOLLOW(F)={(a,b,A,#,+,)}SELECT(P~(E))=FIRST((E))={(}SELECT(P~a)=FIRST(a)={a}SELECT(P~b)=FIRST(b)={b}SELECT(P~A)=FIRS)={A}?由以上结果得相同左部产生式的SELECT^集为：SELECT(E'T+E7SELECT(Er{+=n{#)}SELECT(T'T(n)SELECT(T'^{(,)=1,b,A)n{#+,)}=①SELECT(F'T*F'SELECT(F'T￡)n{*}a,b,A,#,+,)}=①SELECT(FT(E))nSELECT(FTa)nSELECn(FTLECT(PTA)n{(}n{a}n{b①n{A}=?相同左部产生式的SELECT集合的交集为空。?这个文法是LL(1)的。⑶由以上算出的SELECT!可以构造该文法的预测分析表如下：+*()abA#ETTE'TTE'TTE'TTE'E'T+ETdTdTT，FF，PP()；F'()；TFT，TFT，TFT，TFT，TTTgTTTTTTTgTPF，TPF，TPF，TPF，T*F，TgTgTgTgTgTgT(E)TaTbTvoid°()Fchar();{Get='(‘ifch;Getchar();ifch1=')'Getchar(;}{E()ifch='aelsetchar();Geifch='belsetchar();Gesrror(),else}}voidF'(){Getchar();fch='*F'()；elseerror();}F'()；voidF(){}voidT'(){T()；}voidEQvoidvoidT(){{GetcharO;(TO；if如FF0；EX)；EO.TO；}elseEroO,})(4)不妨约定：在进入一个非终结符号相应的子程序前，已读到一个单词ch：存放当前读到的单词，Getchar()为一子程序，每调用一次，完成读取一单词的任务，Error()为出错处理程序。4?证明下述文法不是LL(1文法。S->C$C->bA|aBA->a|aC|bAAB->b|bC|aBB你能否构造一等价的文法，使其是LL(1)并给出判断过程。【解】因为SELECT(A->apSELECT(A->aC)①根据LL(1)文法的判定条件：(1)文法不含左递归对于文法U的任意两个不同的规则有:Select(U^a)nSelect(U~)=0一个文法若满足以上条件，称该文法G为LL(1)文法。得出该文法不是LL(1)文法。该文法含公共因子，消除后的文法为：S->C$C->bA|aBA->aA'|bAAA'->C|&B->bB'|aBBB'->C|&【证明】因为SELECT(C->bA)nSELECT(C->aB)=0SELECT(A->Aa)nSELECT(A->bAA)=0SELECT(A>C)nSELECT('->g)=(FIRST(C)-{&)nF0LL0W(A')工①因此消除公共因子后得到文法也不是LL(1)文法。LL(1)文法试对下面文法7?对于一个文法若消除了左递归，提取了左公共因子后是否一定为进行改写，并对改写后的文法进行判断。(1)A->baB|￡[1]⑵⑶B->Abb|a[2]ATaABe|a[1]Bb|d[2]STAa|b[1]ATSB[2]BTab[3]【解】对于一个文法若消除了左递归，提取了左公因子后不一定是LL(1)文法。题：A->baB|eB->Abb|a先改写文法为：A->baBA->eB->baBbbB->bbB->a再改写文法为：0)A->baBFIRSTFOLLOW1)A->e2)B->bNA{b}{#}3)B->aB{b,a}{#,b}4)N->aBbbN{b,a}{#,b}5)N->b预测分析表ab#A->baB->eB->a->bNN->aBbb->b由预测分析表中无多重入口判定文法是LL(1的。题：［2］将产生式［1］提取左公因子后得：ATa(ABe|e)进一步变换为文法G1:ATaA'A'TAbe'T￡TBb|d消除(2)中的直接左递归，将BTBb|d变换为：BTdB'B'TbB'e该文法最终改写成的形式为：ATaA'A'TAbe|eBTdB'B'TbB'e对此改写后的文法进行判断其是否是LL(1)文法。由分析得可推导出e的非终结符表为：AA'BB'否是否是各非终结符的FIRST集为：FIRST(A)={a}FIRST(A'F=RST(A)J{e}={ae}FIRST(B)=d}FIRST(B')={b{}e}={be}各非终结符的FOLLOW集为：FOLLOW(A)={#}U(FIRST(B)-{e})={#d}FOLLOW(A)=FOLLOW(A)={#d}FOLLOW(B)={e}FOLLOW(B)=FOLLOW(B)UFOLLOW(B)={e}各产生式的SELECT集为：SELECT(ATaA')=FIRST(aA')={a}SELECT(A、ABe)=FIRST(ABe)RST(A)={a}SELECT(A'r)=(FIRSTgU&F)LLOW(A)=FOLLOW(A)={#,d}SELECT(B~dB')=FIRST(dB')=d}SELECT(B'TbB')=FIRST({fcB')=SELECT(B')=(FIF-ST(U&F)LLOW(B)=FOLLOW(B)={e}由以上结果得相同左部产生式的SELECT^集为：SELECT(A'TABe)nSELECT(A')=}=}①门{#SELECT(B'TbnSELECT(B'T￡{b)=n{e}=①???相同左部产生式的SELECT集合的交集为空。???改写后的文法是LL(1)的。题：该文法的非终结符S,A为间接左递归，以S,A,B为序消除一切左递归。将(1)的右部代入(2)得：AtAaB|bB消除其直接左递归得：ATbBA'A'TaA'|￡此时文法变成如下形式：StAa|b(1)ATbBA'(2)A'TaA'|￡Btab此文法中的(1),(2)产生式存在隐含的左公因子,消除隐含的左公因子后文法变成如下的形式：STbS'S'TBA'a|&AtbBAAfaA'|￡BTab此形式中ATbBA'是不可达的产生式，是多余的，所以应将其去掉。所以文法最终改写成的形式为：STbS''TBAa|￡A'TaA'|￡Btab相同左部产生式的SELECT为：SELECT(S'tBA'a)={a}SELECT(S't￡)={#}SELECT(A'taAB')={a}SELECT(A't￡)={a}相同左部产生式的SELECT^集为：SELECT(S'TBA'a)nSELECT(S'T￡^={a}n{#}SELECT(A'TAB)nSELECT(A'T￡)=縛n{a}???关于A'的相同左部其产生式的SELEC-集的交集不为空此改写后的文法不是LL(1)的。题：S->AS|bA->SA|a该文法含间接左递归，因此运用间接左递归的算法对文法进行改写后的文法为：S->AS|bA->bAA'|aA'A'->SAA'|￡SELECT(SAS)nSELECT(->b)={b,a}n{b}去此改写后的文法不是LL(1)的。