编译原理作业与答案

编译原理独立作业2010.5一、简答题1、构造一个文法使其生成的语言是不允许0打头的偶正整数集合。2、文法][EG：TTETEE，FFTFTT/*，iEF)(，构造句型iTTT*的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。3、某LL(1)文法的预测分析表如下，请在下述分析过程表中填入输入串（a,a）$的分析过程。a^,()$SSaS^S(A)AASBASBASABB,SBBε分析过程表：步骤符号栈输入串动作4、文法][SG：RLS，RS，RL*，iL，LR，求增广文法中LR(1)项目集的初态项目集I0。5、文法][SG：GGSS;，()GGtH，)(SaH，求出各非终结符的FISTVT和LASTVT集合。二、分析题：1、构造自动机，使得它能识别字母表{0,1}上以00结尾的符号串，将构造的自动机确定化，并写出相应的正规文法。2、文法][SG：RTeTSDRTdRRbdaD，写出每个非终结符的FIRST集和FOLLOW集，并判断该文法是否为LL(1)文法。3、若有文法][SG：ABSaBaAbAbB(1)试证明该文法是SLR(1)文法，并构造SLR(1)分析表。（2）给出输入串aa#的分析过程。参考答案一、简答题1、构造一个文法使其生成的语言是不允许0打头的偶正整数集合。8|6|4|2|ABCZ9|8|7|6|5|4|3|2|1A|0|BABB|8|6|4|2|0C2、文法][EG：TTETEE，FFTFTT/*，iEF)(，构造句型iTTT*的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。短语：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$)Baa,a$匹配$)B,a)$栈顶出栈，读下一个符号EET+T*FE-TiT$)BS,,a)$匹配$)BSa)$栈顶出栈，读下一个符号$)Baa)$匹配$)B)$栈顶出栈，读下一个符号$))$Bε出栈$))$匹配，出栈$$匹配，分析成功4、文法][SG：RLS，RS，RL*，iL，LR，求增广文法中LR(1)项目集的初态项目集I0(P90)I0：',$SS,$SLR,$SR,/$Li*,/$LR,$RL5.文法][SG：GGSS;，()GGtH，)(SaH，求出各非终结符的FISTVT和LASTVT集合。(P71)FIRSTVTLASTVTSGH;(a（a（a；）a）a）a二、分析题1.构造自动机，使得它能识别字母表{0,1}上以00结尾的符号串，将构造的自动机确定化，并写出相应的正规文法。(P41)NFA:最小化：{S,A’}{B’}0:{S}{A’}{B'}正规文法：AS0’SS1'0BA’SA1''0'BBSB1''B2、文法][SG：RTeTSDRTdRRbdaD，写出每个非终结符的FIRST集和FOLLOW集，并判断该文法是否为LL(1)文法。(P61)FIRST(S)={a,b,d,e,}FIRST(T)={a,b,}FIRST(R)={d,}FIRST(D)={a,b}FOLLOW(S)={$}FOLLOW(T)=FOLLOW(S)={$}FOLLOW(R)={a,b,$}FOLLOW(D)={d,$}SELECT(TeS)={e}SELECT(RTS)={a,b,d}SELECT(DRT)={a,b}SELECT(T)={$}SELECT(R)={a,b}SELECT(dRR)={d}SELECT(aD)={a}SELECT(bdD)={d}SELECT(TeS)∩SELECT(RTS)=01SA’B’SS,AS,A,BS,AS,A,BS,A,BSSSSAB0100100SA’B’110DFA:100SA’B’110最小DFA:SELECT(DRT)∩SELECT(T)=SELECT(R)∩SELECT(dRR)=SELECT(aD)∩SELECT(bdD)=∴该文法是LL(1)文法。3、若有文法][SG：ABSaBaAbAbB(1)试证明该文法是SLR(1)文法，并构造SLR(1)分析表。（2）给出输入串aa#的分析过程。增广文法:0)S'S1)SAB2)AaBa3)A4)BbAb5)BAaBaAABSSS':0IABS:4IbbAB:7IbAbB:8I:1ISS':9IaBaA:6IaaBAAaBaAAbbB':5IBbAbBBaaA:3I5I3ISAaBbaaAbBbBbAbBBAS:2IFOLLOW(S)={$}FOLLOW(A)={b,$}FOLLOW(B)={a,$}ACTIONGOTOab$SAB0S3121acc2r5S5r543r5S5r564r15S3r3r376S97S88r4r49r2r2步骤状态栈符号栈输入串动作012345600303603690202401＃#a#aB#aBa#A#AB#Saa#a#a#####S3r5S9r2r5r1acc