编译原理期末复习题338.pdf

.3.2 是非判断，对下面的陈述，正确的在陈述后的括号内写T，否则写 F。(1)有穷自动机接受的语言是正则语言。（）(2)若 r1和 r2是上的正规式，则 r1|r2也是。（）(3)设 M 是一个 NFA，并且 L(M)x,y,z，则 M 的状态数至少为 4 个。（）(4)令 a,b，则 上所有以 b 为首的字构成的正规集的正规式为 b*(a|b)*。（）(5)对任何一个 NFA M，都存在一个 DFA M，使得 L(M)=L(M)。（）(6)对一个右线性文法 G，必存在一个左线性文法 G，使得 L(G)=L(G)，反之亦然。（）答案(1)T (2)T (3)F(4)F (5)T (6)T 3.3 描述下列各正规表达式所表示的语言。(1)0(0|1)*0 (2)(|0)1*)*(3)(0|1)*0(0|1)(0|1)(4)0*10*10*10*(5)(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*答案(1)以 0 开头并且以 0 结尾的，由 0 和 1 组成的符号串。(2)|0,1*(3)由 0 和 1 组成的符号串，且从右边开始数第 3 位为 0。(4)含 3 个 1 的由 0 和 1 组成的符号串。|0,1+，且 中含有 3 个 1 (5)|0,1*,中 0 和 1 为偶数 3.4 对于下列语言分别写出它们的正规表达式。(1)英文字母组成的所有符号串，要求符号串中顺序包含五个元音。(2)英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。(3)=0,1上的含偶数个 1 的所有串。(4)=0,1上的含奇数个 1 的所有串。(5)具有偶数个 0 和奇数个 1 的有 0 和 1 组成的符号串的全体。(6)不包含子串 011 的由 0 和 1 组成的符号串的全体。(7)由 0 和 1 组成的符号串,把它看成二进制数，能被3 整除的符号串的全体。答案(1)令 Letter 表示除这五个元音外的其它字母。(letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter)*(2)A*B*.Z*(3)(0|10*1)*(4)(0|10*1)*1.(5)分析 设 S 是符合要求的串，|S|=2k+1(k0）。则 SS10|S21，|S1|=2k(k0），|S2|=2k(k0）。且 S1是0,1上的串，含有奇数个 0 和奇数个 1。S2是0,1上的串，含有偶数个 0 和偶数个 1。考虑有一个自动机 M1接受 S1，那么自动机 M1如下：和 L(M1)等价的正规表达式，即 S1为：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*类似的考虑有一个自动机 M2接受 S2，那么自动机 M2如下：和 L(M2)等价的正规表达式，即 S2为：(00|11)|(01|10)(00|11)*(01|10)*因此，S 为：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*0|(00|11)|(01|10)(00|11)*(01|10)*1 (6)1*|1*0(0|10)*(1|)(7)接受 w 的自动机如下：对应的正规表达式：(1(01*0)1|0)*3.6 给出接受下列在字母表0,1上的语言的 DFA。(1)所有以 00 结束的符号串的集合。(2)所有具有 3 个 0 的符号串的集合。.答案(a)DFA M=(0，1，q0，q1，q2，q0，q2，)其中 定义如下:（q0，0）=q1 （q0，1）=q0（q1，0）=q2 （q1，1）=q0（q2，0）=q2 （q2，1）=q0 (b)正则表达式:1*01*01*01*DFA M=(0，1，q0，q1，q2，q3，q0，q3，)其中 定义如下:（q0，0）=q1 （q0，1）=q0（q1，0）=q2 （q1，1）=q1（q2，0）=q3 （q2，1）=q2（q3，1）=q3 3.7 构造等价于下列正规表达式的有限自动机。(1)10|（0|11）0*1(2)(0|1)*|(11)*答案(1)DFA M=(0，1，q0，q1，q2，q3，q0，q3，)其中 定义如下:.(2)（q0，0）=q1 （q0，1）=q2(3)（q1，0）=q1 （q1，1）=q3(4)（q2，0）=q3 （q2，1）=q1(5)(6)(2)DFA M=(0，1，q0，q0，q0，)(7)其中 定义如下:(8)（q0，0）=q0 （q0，1）=q0(9)3.8 给定右线性文法 G：S-0S|1S|1A|0B A-1C|1 B-0C|0 C-0C|1C|0|1 试求一个于 G 等价的左线性文法 G 3.9 试对于下列正规表达式使用证明定理 3。5 的构造算法构造非确定的有限自动机。请给出每个自动机在处理输入符号串 ababbab 的过程中的动作序列。(1)(a|b)*(2)(a*|b*)*(3)(|a)b*)*.3.10 转换练习 3.9 中的每个 NFA 为 DFA。并给出每个 DFA 在处理输入符号串 ababbab 的过程中的动作序列。3.11 试把练习 3.10 中得到的 DFA 的状态给以最小化。答案(1),(2),(3)的 DFA M 相同，化简结果为：(4)3.12 我们可以证明两个正规表达式是等价的，如果它们的最小状态 DFA 是相同的（除了状态的名字以外）。利用这一结论，请说明下列正规表达式都是等价的。(1)(a|b)*(2)(a*|b*)*(3)(|a)b*)*答案 根据 3.11 的结果知这几个正规表达式是等价的。3.13 对于下列正规表达式构造最小状态的 DFA。(1)(a|b)*a(a|b)(2)(a)b)*a(a|b)(a|b)5 对如下文法：GS：S a b S|a a B|a d B b b B|b 分别给出句子 abaabbb 和 ad 的句柄 句子 ad 的语法分析树为：.句子 abaabbb 的语法分析树为:所以句子 abaabbb 的句柄是 b；句子 ad 的句柄是 ad.二、（10 分）说明如下文法是否是 LL（1）文法，若不是，将其转换为 LL（1）文法。最后给出该文法的LL（1）分析表。GA：A B e B B b|a 文法中有左递归，不是 LL(1)文法。转换为 G：A B e B a B Bb B|Predict(A B e)=a Predict(B a B)=a Predict(Bb B)=b Predict(B )=e LL(1)分析表:a b e A B e B a B B b B S a b S a a B b b B b S a d.4.给出识别正则表达式(（a|bc）*d)+的 NFA。5 已知文法 GS：S S；GG G G(T)H H a (S)T T+S S 找出句型：a(T+S)；H；(S)的短语、简单短语和句柄。短语:a,T+S,a(T+S),H,a(T+S);H,(S)简单短语：a,T+S,H,(S)句柄是 a.6 已知文法 GS为：SAB|bC Ab|BaD|CAD|b DaS|c 对其每一个非终级符求 First 集和 Follow 集。First(S)=b,a,First(A)=b,First(B)=a,First(C)=b,a,c First(D)=a,c Follow(S)=#Follow(A)=a,c,#Follow(B)=#Follow(C)=#Follow(D)=#二、（10 分）设有文法 GA:A iB*e B SB|S eC|.i C eC|判定该文法是否为 LL(1)文法？若是则给出它的 LL(1)分析表，否则说明理由。先计算各个产生式的 Predict 集：Predict(A-iB*e)=i;Predict(B-SB)=,.Predict(B-)=*.Predict(S-eC)=Predict(S-.i)=.Predict(C-eC)=e Predict(C-)=因为 Predict 集没有冲突，所以是 LL(1)文法。LL(1)分析表如下：i *e .A-iB*e -B -S B -S B S -e C -.i C -eC -1、证明下面文法是 LL(1)的但不是 SLR(1)文法 SAaAb|BbBa A B 解：对于产生式 SAaAb|BbBa 来说 FIRST(AaAb)FIRST(BbBa)=ab=而 A，BVN仅有一条候选式。因此，这个文法是 LL(1)的。下面构造这个文法的识别活前缀的 DFA。I0=SS,SAaAb,SBbBa,A,B I1=SS I2=SAaAb I3=SBbBa I4=SAaAb,A I5=SBbBa,B I6=SAaAb I7=SBbBa I8=SAaAb I9=SBbBa 由于 FOLLOW(A)=FOLLOW(B)=a,b 因此项目集 I0 中存在归约归约冲突。在 I0状态下，当输入符号是 a 或是 b 时，不知用 A 还是 B进行归约。故此文法不是 SLR(1)的。但是，此文法是 LR(1)的。五、已知文法 GS，其产生式如下：S(L)|a L L，S|S .从 GS中消除左递归，并为之构造一个非递归预测分析器 LL(1)分析表。请说明在句子(a，(a，a)上的分析器的动作。（20 分）解：将所给文法消除左递归得 G：S(L)|a L SL L，SL|实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法 G有 FIRST(s)=(,a)FOLLOW(S)=,$FIRST(L)=(,a)FOLLOW(L)=FIRST(L)=,FOLLOW(L)=按以上结果，构造预测分析表 M 如下：文法 G是 LL(1)的，因为它的 LL(1)分析表不含多重定义入口。预测分析器对输入符号串(a,(a,a)做出的分析动作如下：例 5.3 的文法 G3S 为：SaA Sd AbAS A 不难看出由定义 5.3 可得：.SELECT(SaA)=a SELECT(Sd)=d SELECT(AbAS)=b SELECT(A)=a,d,#所以 SELECT(SaA)SELECT(Sd)=ad=SELECT(AbAS)SELECT(A)=ba,d,#=由定义 5.4 知例 5.3 文法是 LL(1)文法，所以可用确定的自顶向下分析。而对例 5.5 文法 G5S为：SaAS Sb AbA A 则 SELECT(SaAS)=a SELECT(Sb)=b SELECT(AbA)=b SELECT(A)=a,b 所以 SELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b 因此，例 5.5 文法不是 LL(1)文法，因而也就不可能用确定的自顶向下 表达式文法为：EE+T|T TT*F|F Fi|(E)构造步骤：(1)判断文法是否为 LL(1)文法 4.5 已知文法 GS，其产生式如下：S(L)|a L L，S|S 从 GS中消除左递归，并为之构造一个非递归预测分析器 LL(1)分析表。请说明在句子(a，(a，a)上的分析器的动作。解：将所给文法消除左递归得 G：S(L)|a L SL L，SL|实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法 G有 FIRST(s)=(,a)FOLLOW(S)=),$FIRST(L)=(,a)FOLLOW(L)=)FIRST(L)=,FOLLOW(L)=)按以上结果，构造预测分析表 M 如下：文法 G是 LL(1)的，因为它的 LL(1)分析表不含多重定义入口。预测分析器对输入符号串(a,(a,a)做出的分析动作如下：.4.6 对于练习 4.1 的文法，构造它的 LL(1)分析表。解：从练习 4.1 得到文法的产生式如下：R R|T|T T TF|F F F*|C C (R)|a|b 消除上面文法中的左递归 R TR R|TR|T FT T FT|F CF F *F|C (R)|a|b 计算 FIRST()和 FOLLOW(A).构造 LL(1)分析表。4.9 对于文法 GS，其产生式如下 S(L)|a(4.22)LL,S|S (1)给出句子(a，(a，a)，(a，a)的一个最右推导，并指出右句型的句柄。(2)按照(a)的最右推导，说明移进-归约分析器的工作步骤。解：(1)S=(L)=(L,S)=(L,(L)=(L,(L,S)=(L,(L,(L)=(L,(L,(L,S)=(L,(L,(L,a)=(L,(L,(S,a)=(L,(L,(a,a)=(L,(S,(a,a)=(L,(L),(a,a)=(L,(L,S),(a,a)=(L,(L,a),(a,a)=(L,(S,a),(a,a)=(L,(a,a),(a,a)=(S,(a,a),(a,a)=(a,(a,a),(a,a)右句型的句柄为每个右句型中用下划线标识出的部分。(2)对于(a)的最右推导，移进规约分析器的工作步骤如下：.4.11 下列文法是否为 SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。(a)SSab|bR RS|a 解：该文法的拓广文法 G为 (0)S S(1)S Sab(2)S bR(3)R S.(4)R a 其 LR(0)项目集规范族和 goto 函数(识别活前缀的 DFA)如下:I0=SS,SSab,SbR I1=SS,SSab I2=SbR,RS,Ra,SSab,SbR I3=SSab I4=SbR I5=RS,SSab I6=Ra I7=SSab 求 FOLLOW 集：FOLLOW(S)=FOLLOW(R)=FOLLOW(S)=a,在 I5中，出现移进归约冲突，且 FOLLOW(R)a=a因此，此文法不是 SLR(1)文法。b)SaSAB|BA AaA|B Bb 解：该文法的拓广文法 G为 (0)S S(1)S aSAB(2)S BA(3)A aA(4)A B(5)B b 其 LR(0)项目集规范族和 goto 函数(识别活前缀的 DFA)如下:I0=SS,SaSAB,SBA,Bb I1=SS I2=Bb I3=SaSAB,SaSAB,SBA,Bb I4=SBA,AaA,AB,Bb I5=SaSAB,AaA,AB,Bb I6=SaSAB,Bb I7=AaA,AaA,AB,Bb I8=AB I9=SBA I10=SaSAB I11=AaA 求 FOLLOW 集：FOLLOW(S)=FOLLOW(S)=a,b,FOLLOW(A)=a,b,FOLLOW(B)=a,b,.4.12 证明下面文法是 SLR(1)文法，并构造其 SLR 分析表。EE+T|T TTF|F FF*|a|b 解：该文法的拓广文法 G为 (0)E E(1)E E+T(2)E T(3)T TF(4)T F(5)F F*(6)F a(7)F b 其 LR(0)项目集规范族和 goto 函数(识别活前缀的 DFA)如下:I0=EE,EE+T,ET,TTF,TF,FF*,Fa,Fb I1=EE,EE+TI2=ET,TTF,FF*,Fa,Fb I3=TF,FF*I4=Fa I5=Fb I6=EE+T,TTF,TF,FF*,Fa,Fb I7=TTF,FF*I8=FF*I9=EE+T,TTF,FF*,Fa,Fb 求 FOLLOW 集：FOLLOW(E)=,FOLLOW(T)=,a,b FOLLOW(F)=,a,b,*.构造的 SLR 分析表如下：显然，此分析表无多重定义入口，所以此文法是 SLR 文法。4.13 下面文法属于哪类 LR 文法？试构造其分析表。S(SR|a R,SR|)解：该文法的拓广文法 G为 (0)S S(1)S (SR(2)S a(3)R ,SR(4)R )构造其 LR(0)项目集规范族和 goto 函数(识别活前缀的 DFA)如下:I0=SS,S(SR,Sa I1=SS I2=S(SR,S(SR,Sa I3=Sa I4=S(SR,R,SR,R)I5=S(SR I6=R)I7=R,SR,S(SR,Sa I8=R,SR,R,SR,R)I9=R,SR 每个 LR(0)项目集中没有冲突。因此，此文法是 LR(0)文法。其分析表如下：.4.14 设文法 G 为 SA ABA|BaB|b (1)证明它是 LR(1)文法。(2)构造它的 LR(1)分析表。(3)给出输入符号串 abab 的分析过程。解：(1)构造其拓广文法 G的产生式为 (0)S S(1)S A(2)A BA(3)A (4)B aB(5)B b 构造其 LR(0)项目集规范族和 goto 函数(识别活前缀的 DFA)如下:I0=SS,$,SA,$,ABA,$,A,$,BaB,a/b/$,Bb,a/b/$I1=SS,$I2=SA,$I3=ABA,$,ABA,$,A,$,BaB,a/b/$,Bb,a/b/$I4=Bb,a/b/$I5=BaB,a/b/$,BaB,a/b/$,Bb,a/b/$I6=ABA,$I7=BaB,a/b/$该文法的 LR(1)项目集规范族中没有冲突，所以该文法是 LR(1)文法。(2)构造 LR(1)分析表如下：.以上分析表无多的定义入口，所以该文法为 LR(1)文法。(3)对于输入串 abab，其分析过程如下：4.15 为下面的文法构造 LALR(1)分析表 SE EE+T|T T(E)|a 解：其拓广文法 G：(0)S S(1)S E(2)E E+T(3)E T(4)T (E)(5)T a 构造其 LR(1)项目集规范族和 goto 函数(识别活前缀的 DFA)如下:I0=SS,$,SE,$,EE+T,$/+,ET,$/+,T(E),$/+,Ta,$/+I1=SS,$I2=SE,$,EE+T,$/+I3=ET,$/+I4=T(E),$/+,EE+T,)/+,ET,)/+,T(E),)/+,Ta,)/+I5=Ta,$/+I6=EE+T,$/+,T(E),$/+,Ta,$/+I7=T(E),$/+,EE+T,)/+I8=ET,)/+I9=T(E),)/+,EE+T,)/+,ET,)/+,T(E),)/+,Ta,)/+I10=Ta,)/+I11=EE+T,$/+I12=T(E),$/+.I13=EE+T,)/+,T(E),)/+,Ta,)/+I14=T(E),)/+,EE+T,)/+I15=EE+T,)/+I16=T(E),)/+合并同心的 LR(1)项目集，得到 LALR 的项目集和转移函数如下：I0=SS,$,SE,$,EE+T,$/+,ET,$/+,T(E),$/+,Ta,$/+I1=SS,$I2=SE,$,EE+T,$/+I3,8=ET,$/+/)I4,9=T(E),$/+/),EE+T,)/+,ET,)/+,T(E),)/+,Ta,)/+I5,10=Ta,$/+/)I6,13=EE+T,$/+/),T(E),$/+/),Ta,$/+/)I7,14=T(E),$/+/),EE+T,)/+I11,15=EE+T,$/+/)I12,16=T(E),$/+/)LALR 分析表如下：br .4.16 考虑文法 GS，其产生式如下 SAS|b ASA|a(1)构造文法 GS的 LR(0)项目集规范族及相应的 DFA。(2)如果把每一个 LR(0)项目看成一个状态，并从每一个形如 BX 的状态出发画一条标识为 X 的箭弧到状态BX,而且从每一个形如BA的状态出发画标记为的箭弧到所有形如A的状态。这样就得到了一个 NFA。说明这个 NFA 与(a)的 DFA 是等价的。(3)构造文法的 SLR 分析表。(4)对于输入串 bab，给出 SLR 分析器所作出的动作。(5)构造文法的 LR(1)分析表和 LALR 分析表。解：(1)其拓广文法 G：(0)S S(1)S AS(2)S b(3)A SA(4)A a 构造其 LR(0)项目集规范族和 goto 函数(识别活前缀的 DFA)如下:I0=SS,SAS,Sb,ASA,Aa I1=SS,ASA,ASA,Aa,SAS,Sb I2=SAS,SAS,Sb,ASA,Aa I3=A a I4=Sb I5=ASA,SAS,SAS,Sb,ASA,Aa I6=ASA,ASA,Aa,SAS,Sb I7=SAS,ASA,ASA,Aa,SAS,Sb.(2)文法 GS的 LR(0)项目如下：(0)S S(1)S S(2)S AS(3)S AS(4)S AS(5)S b(6)S b(7)A SA(8)A SA(9)A SA(10)A a(11)A a 对上面的 NFA 通过求-cloasure 确定化，得到与(1)相同的识别文法 GS活前缀的 DFA。因此，此 NFA 与(1)的 DFA 等价。(3)求 FOLLOW 集：FOLLOW(S)=a,b,FOLLOW(A)=a,b GS的 SLR 分析表：.(4)注：GS的 SLR 分析表中有移进归约冲突，因此它不是一个 SLR 文法。其实，GS是一个二义性文法，对于句子 abab 有下面两棵不同的分析树。因此，GS不是任何 LR 文法。(5)文法 GS的 LR(1)项目集规范族及转移函数为：I0=SS,$,SAS,$/a,Sb,$/a,ASA,a/b,Aa,a/b I1=SS,$,ASA,a/b,ASA,a/b,Aa,a/b,SAS,a/b,Sb,a/b I2=SAS,$/a/b,SAS,$/a/b,Sb,$/a/b,ASA,a/b,Aa,a/b,.I3=Aa,a/b I4=Sb,a/b/$I5=ASA,a/b,ASA,a/b,Aa,a/b,SAS,a/b,Sb,a/b 6=ASA,a/b,SAS,a/b,SAS,a/b,Sb,a/b,ASA,a/b,Aa,a/b I7=SAS,a/b/$,ASA,a/b,ASA,a/b,Aa,a/b,SAS,a/b,Sb,a/b I8=SAS,a/b,SAS,a/b,Sb,a/b,ASA,a/b,aa,a/b I9=SAS,a/b/$,ASA,a/b,ASA,a/b,Aa,a/b,SAS,a/b,Sb,a/b,I10=Sb,a/b 合并同心项目集(I2和 I8，I7和 I9，I4和 I10)：I0=SS,$,SAS,$/a,Sb,$/a,ASA,a/b,Aa,a/b I1=SS,$,ASA,a/b,ASA,a/b,Aa,a/b,SAS,a/b,Sb,a/b I2,8=SAS,$/a/b,SAS,$/a/b,Sb,$/a/b,ASA,a/b,Aa,a/b,I3=Aa,a/b I4,10=Sb,a/b/$I5=ASA,a/b,SAS,a/b,SAS,a/b,Sb,a/b,ASA,a/b,Aa,a/b I6=ASA,a/b,ASA,a/b,Aa,a/b,SAS,a/b,Sb,a/b I7,9=SAS,a/b/$,ASA,a/b,ASA,a/b,Aa,a/b,SAS,a/b,Sb,a/b.LR(1)和 LALR 分析表从略。4.17 证明下面文法是 LL(1)的但不是 SLR(1)文法 SAaAb|BbBa A B 解：对于产生式 SAaAb|BbBa 来说 FIRST(AaAb)FIRST(BbBa)=ab=而 A，BVN仅有一条候选式。因此，这个文法是 LL(1)的。下面构造这个文法的识别活前缀的 DFA。I0=SS,SAaAb,SBbBa,A,B I1=SS I2=SAaAb I3=SBbBa I4=SAaAb,A I5=SBbBa,B I6=SAaAb I7=SBbBa I8=SAaAb I9=SBbBa 由于 FOLLOW(A)=FOLLOW(B)=a,b 因此项目集 I0 中存在归约归约冲突。在 I0状态下，当输入符号是 a 或是 b 时，不知用 A.还是 B 进行归约。故此文法不是 SLR(1)的。但是，此文法时 LR(1)的。4.19 判断题 对下面的陈述，正确的在陈述后的括号内画;否则画(1)存在有左递归规则的文法是 LL(1)的。()(2)任何算符优先文法的句型中不会有两个相邻的非终结符号。()(3)算符优先文法中任何两个相邻的终结符号之间至少满足三种 关系(，()之一。()(4)任何 LL(1)文法都是无二义性的。()(5)每一个 SLR(1)文法也都是 LR(1)文法。()(6)存在一种算法，能判定任何上下文无关文法是否是 LL(1)的。()(7)任何一个 LL(1)文法都是一个 LR(1)文法，反之亦然。()(8)LR(1)分析中括号中的 1 是指，在选用产生式 A 进行分析，看当前读入符号是否在 FIRST()中。()参考答案：(1)(2)(3)(4)(5)(6)(7)(8)