编译原理作业与答案.doc

编译原理独立作业 2010.5一、简答题1、 构造一个文法使其生成的语言是不允许0打头的偶正整数集合。2、文法：，构造句型的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。3、 某LL(1)文法的预测分析表如下，请在下述分析过程表中填入输入串（ a , a ）$ 的分析过程。a,()$SSaSS(A)AASBASBASABB,SBB分析过程表：步骤符号栈输入串动作4、 文法：，求增广文法中LR(1)项目集的初态项目集I0。5、文法：，求出各非终结符的FISTVT和LASTVT集合。二、分析题：1、构造自动机，使得它能识别字母表0,1上以00结尾的符号串，将构造的自动机确定化，并写出相应的正规文法。2、文法： ，写出每个非终结符的FIRST集和FOLLOW集，并判断该文法是否为LL(1)文法。3、若有文法： (1)试证明该文法是SLR(1) 文法，并构造SLR(1)分析表。 （2）给出输入串aa# 的分析过程。参考答案一、 简答题1、构造一个文法使其生成的语言是不允许0打头的偶正整数集合。2、文法：，构造句型的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。EET+T*FE-TiT短语：T，T-T，i，T*i，T-T+T*i直接短语：T， i句柄： T素短语（P72）：T-T,i最左素短语：T-T3 某LL(1)文法的预测分析表如下，请在下述分析过程表中填入输入串（ a , a ）$ 的分析过程。a,()$SSaSS(A)AASBASBASABB,SBB（P68）分析过程表：步骤符号栈输入串动作1$S(a,a)$符号栈出栈，对应产生式反向进栈2$)A(a,a)$匹配3$)Aa,a)$栈顶出栈，读下一个符号4$)BSa,a)$对应产生式ASB反向进栈5$)Baa,a$匹配$)B,a)$栈顶出栈，读下一个符号$)BS,a)$匹配$)BSa)$栈顶出栈，读下一个符号$)Baa)$匹配$)B)$栈顶出栈，读下一个符号$)$B出栈$)$匹配，出栈$匹配，分析成功4、文法：，求增广文法中LR(1)项目集的初态项目集I0(P90)I0：5. 文法：，求出各非终结符的FISTVT和LASTVT集合。(P71)FIRSTVTLASTVTSGH; ( a（ a（ a； ） a） a） a二、分析题1. 构造自动机，使得它能识别字母表0,1上以00结尾的符号串，将构造的自动机确定化，并写出相应的正规文法。(P41)NFA: SAB010001SABSS,AS,A,BS,AS,A,BS,A,BSSS100SAB110DFA:100SAB110最小DFA:最小化： S,AB0:SAB正规文法： 2、 文法： ，写出每个非终结符的FIRST集和FOLLOW集，并判断该文法是否为LL(1)文法。(P61)FIRST(S)=a,b,d,e, FIRST(T)=a,b, FIRST(R)=d, FIRST(D)=a,bFOLLOW(S)=$ FOLLOW(T)=FOLLOW(S)=$ FOLLOW(R)=a,b,$FOLLOW(D)=d,$SELECT()=eSELECT()=a,b,dSELECT()=a,bSELECT()=$SELECT()=a,bSELECT()=dSELECT()=aSELECT()=dSELECT()SELECT()=SELECT()SELECT()=SELECT()SELECT()=SELECT()SELECT()=该文法是LL(1)文法。3、若有文法： (1)试证明该文法是SLR(1) 文法，并构造SLR(1)分析表。 （2）给出输入串aa# 的分析过程。增广文法:0) SS 1) SAB 2) AaBa 3) Ae 4) BbAb 5) Be FOLLOW(S)=$ FOLLOW(A)=b,$ FOLLOW(B)=a,$ ACTION GOTOab$SAB0S3121acc2r5S5r543r5S5r564r15S3r3r376S97S88r4r49r2r2步骤状态栈符号栈输入串动作012345600303603690202401#a#aB#aBa#A#AB#Saa#a#a#S3r5S9r2r5r1acc