资源描述：
《编译原理作业与答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编译原理独立作业2010.5一、简答题1、构造一个文法使其生成的语言是不允许0打头的偶正整数集合。2、文法：，，，构造句型的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。3、某LL(1)文法的预测分析表如下，请在下述分析过程表中填入输入串（a,a）$的分析过程。a^,()$SS®aS®^S®(A)AA®SBA®SBA®SABB®,SBB®ε分析过程表：步骤符号栈输入串动作4、文法：，，，，，求增广文法中LR(1)项目集的初态项目集I0。5、文法：，，，求出各非终结符的FISTVT和LAS
2、TVT集合。二、分析题：1、构造自动机，使得它能识别字母表{0,1}上以00结尾的符号串，将构造的自动机确定化，并写出相应的正规文法。2、文法：，写出每个非终结符的FIRST集和FOLLOW集，并判断该文法是否为LL(1)文法。3、若有文法：(1)试证明该文法是SLR(1)文法，并构造SLR(1)分析表。（2）给出输入串aa#的分析过程。参考答案一、简答题1、构造一个文法使其生成的语言是不允许0打头的偶正整数集合。2、文法：，，，构造句型的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。E
3、ET+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^,()$SS®aS®^S®(A)AA®SBA®SBA®SABB®,SBB®ε（P68）分析过程表：步骤符号栈输入串动作1$S(a,a)$符号栈出栈，对应产生式反向进栈2$)A((a,a)$匹配3$)Aa,a)$栈顶出栈，读下一个符号4$)BSa,a)$对应产生式A®SB反向进栈5
4、$)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结尾的符号串，将
5、构造的自动机确定化，并写出相应的正规文法。(P41)NFA:SAB010001SA’B’SS,AS,A,BS,AS,A,BS,A,BSSS100SA’B’110DFA:100SA’B’110最小DFA:最小化：{S,A’}{B’}0:{S}{A’}{B'}正规文法：’1、文法：，写出每个非终结符的FIRST集和FOLLOW集，并判断该文法是否为LL(1)文法。(P61)FIRST(S)={a,b,d,e,}FIRST(T)={a,b,}FIRST(R)={d,}FIRST(D)={a,b}FOLLOW(S
6、)={$}FOLLOW(T)=FOLLOW(S)={$}FOLLOW(R)={a,b,$}FOLLOW(D)={d,$}SELECT()={e}SELECT()={a,b,d}SELECT()={a,b}SELECT()={$}SELECT()={a,b}SELECT()={d}SELECT()={a}SELECT()={d}SELECT()∩SELECT()=SELECT()∩SELECT()=SELECT()∩SELECT()=SELECT()∩SELECT()=∴该文法是LL(1)文法。3、若有文法
7、：(1)试证明该文法是SLR(1)文法，并构造SLR(1)分析表。（2）给出输入串aa#的分析过程。增广文法:0)S'®S1)S®AB2)A®aBa3)A®e4)B®bAb5)B®eFOLLOW(S)={$}FOLLOW(A)={b,$}FOLLOW(B)={a,$}ACTIONGOTOab$SAB0S3121acc2r5S5r543r5S5r564r15S3r3r376S97S88r4r49r2r2步骤状态栈符号栈输入串动作012345600303603690202401＃#a#aB#aBa#A#AB#
8、Saa#a#a#####S3r5S9r2r5r1acc
