编译原理作业与答案新.docVIP

编译原理独立作业 2010.5 一、简答题 构造一个文法使其生成的语言是不允许0打头的偶正整数集合。 2、文法：，，，构造句型的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。 某LL(1)文法的预测分析表如下，请在下述分析过程表中填入输入串（ a , a ）$ 的分析过程。 a^,()$SS?aS?^S?(A)AA?SBA?SBA?SABB?,SBB?ε分析过程表： 步骤符号栈输入串动作文法：，，，，，求增广文法中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、文法：，，，构造句型的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。 E E T + T * F E - T i T 短语：T，T-T，i，T*i，T-T+T*i 直接短语：T， i 句柄： T 素短语（P72）：T-T,i 最左素短语：T-T 某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)$栈顶出栈，读下一个符号$)BS,,a)$匹配$)BSa)$栈顶出栈，读下一个符号$)Baa)$匹配$)B)$栈顶出栈，读下一个符号$))$B?ε出栈$))$匹配，出栈$$匹配，分析成功4、文法：，，，，，求增广文法中LR(1)项目集的初态项目集I0 (P90) I0： 5. 文法：，，，求出各非终结符的FISTVT和LASTVT集合。 (P71) FIRSTVTLASTVTS G H; ( a （ a （ a； ） a ） a ） a 二、分析题 1. 构造自动机，使得它能识别字母表{0,1}上以00结尾的符号串，将构造的自动机确定化，并写出相应的正规文法。(P41) NFA: S A B 0 1 0 0 01S A’ B’S S,A S,A,BS,A S,A,B S,A,BS S S 1 0 0 S A’ B’ 1 1 0 DFA: 1 0 0 S A’ B’ 1 1 0 最小DFA: 最小化： {S,A’}{B’} 0:{S}{A’}{B} 正规文法： ’ 文法： ，写出每个非终结符的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()={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、若有文法： (1)试证明该文法是SLR(1) 文法，并构造SLR(1)分析表。 （2）给出输入串aa# 的分析过程。 增广文法: 0) S?S 1) S?AB 2) A?aBa 3) A?? 4) B?