编译原理-第5章-习题与答案2上课讲义

1、编译原理-第 5 章-习题与答案 2精品文档第五章 习题5-1 设有文法GS：A/aA/(1) 找出部分符号序偶间的简单优先关系。(2) 验证GS不是简单优先文法。5-2 对于算符文法GS：SETT*FFPP(E)i(1) 找出部分终结符号序偶间的算符优先关系。(2) 验证GS不是算符优先文法。5-3 设有文法：EEEE+T|TTT1TT*F|FF(E)|i11111其相应的简单优先矩阵如题图5-3所示，试给出对符号串（）进行简单优先分析的过程。EETTF+*()i1111 )i题图 5-3文法 GE的简单优先矩阵收集于网络，如有侵权请联系管理员删除精品文档5-4 设有文法GE：EE+T|TT

2、T*F|FF(E)|i其相应的算符优先矩阵如题图5-4所示。试给出对符号串（）进行算符优先分析的过程。+)#(i*+)# 题图 5-4 文法 GE的算符优先矩阵5-5 对于下列的文法，试分别构造识别其全部可归前缀的DFA和LR(0)分析表，并判断哪些是LR(0)文法。(1) SaScab(2) SaSSbaSSSc(3) SAa5-6 下列文法是否是文法？若是，构造相应的SLR(1)分析表，若不是，则阐明其理由。(1) SbRSa(2) SaSABBA(3) SbBaABcAdbcBdd收集于网络，如有侵权请联系管理员删除精品文档5-7 对如下的文法分别构造LR(0)及 SLR(1)分析表，并

3、比较两者的异同。cAdba5-8 对于文法GS:SABAaBb(1) 构造LR(1)分析表；(2) 给出用LR(1)分析表对输入符号串abab的分析过程。5-9 对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法。(1) AABaBb(2) a第 5章 习题答案25-1 解：(1) 由文法的产生式和如答案图5-1(a)所示的句型A的语法树，可得G 中的部分优先关系如答案图5-1(b)所示。收集于网络，如有侵权请联系管理员删除精品文档S/AaAS/AaAA/AA/aa/(a) 句型A/a/的语法树(b)部分符号序偶间的优先关系答案图5-1(2) 由答案图5-1(b)可知，在符

4、号A和之间，即存在等于关系，又存在低于关系，故文法GS不是简单优先文法。5-2 解：(1) 由文法GS的产生式可直接看出：（ = ）此外，再考察句型P(E)和 i*(T*F)的语法树 (见答案图5-2(a)(b)。由答案图5-2(a)可得： , , (由答案图5-2(b)可得：i * ,* ( , ( * , * ）收集于网络，如有侵权请联系管理员删除精品文档ETT-*FF(E)F-T-P()T* F(a)句型 -P-(E)的语法树(b)句型i*(T*F)的语法树(2)由答案图5-2(a)可知，在终结符号和之间，存在两种算符优先关系： , 故文法 GS不是算符优先文法。5-3 解：对符号串进行

5、简单优先分析的过程如答案表5-3所示。因为分析成功，所以符号串(i+i)是文法的合法句子。答案表5-3 (i+i)的简单优先分析过程当前符号（余留输入串i+i)#+i)#i)#所用步骤分析栈关系低于句柄产生式低于 i优于 +优于 +优于 +优于 +2 #(i3 #(F4 #(T5 #(Ti Fii)#i)#1i)#T ET1111收集于网络，如有侵权请联系管理员删除精品文档#(E等于低于优于优于优于优于优于等于优于优于优于优于优于i)#)#1#(E+#(E+iiFT#(E+F#10#(E+T#11 #(E+T#111#EEE11#TT11EEE11分析成功优于5-4 解：对符号串进行算符优先分

6、析的过程如答案表5-4所示。因为分析成功，所以符号串(i+i)是文法GE的合法句子。句子(i+i)及其分析过程中所得句型的语法树如答案图5-4所示。答案表5-4 i+i)的算符优先分析过程当前栈顶终结符号优先当前输余留最左步骤分析栈关系入符号 输入串素短语0123 # ( i+i# (F(+i)#收集于网络，如有侵权请联系管理员删除精品文档 i#分析成功#ETF(E+)()(E)ETFi答案图5-4 句子(i+i)及其分析过程中所得句型的语法树5-5 解：(1) 在文法GS中引入一个新的开始符号，且将SS作为第0个产生式添加到文法G中，从而得到G的拓广文法GS：0.SSaScab1.SaSb收

7、集于网络，如有侵权请联系管理员删除精品文档识别文法GS全部可归前缀的DFA如答案图5-5-(1)所示。10abc23a答案图5-5-(1) 识别GS全部可归前缀的DFA因为文法GS的每个项目集中都不含冲突项目，所以文法GS是 文法，故可构造出不含冲突动作的LR(0)分析表如答案表5-5-(1)所示。答案表5-5-(1) 文法GS的LR(0)分析表状态#01234563245312srrr6312rrrrrrr3123r1r2(2) 在文法GS中引入一个新的开始符号，且将SS 作为第0 个产生式添加到文法G 中，从而得到G 的拓广文法GS：收集于网络，如有侵权请联系管理员删除精品文档0.SSaS

8、SSc1.SaSSb识别文法GS全部可归前缀的DFA如答案图5-5-(2)所示。S10cacccbSSaaaS因为文法GS的每个项目集中都不含冲突项目，所以文法GS是 文法，故可构造出不含冲突动作的LR(0)分析表如答案表5-5-(2)所示。答案表5-5-(2) 文法GS的LR(0)分析表状态#0123453srss423333rr33ss5722收集于网络，如有侵权请联系管理员删除精品文档67rrrrrr12121212r(3) 在文法GS中引入一个新的开始符号，且将SS作为第0个产生式添加到文法G中，从而得到G的拓广文法GS：0.SSAba1.SA识别文法GS全部可归前缀的DFA如答案图5

9、-5-(3)所示。SI : SS 10a2Ab34答案图5-5-(3) 识别GS全部可归前缀的DFA因为在 LR(0)项目集I中含有移进归约冲突项目，所以文法GS不是 文2法，故构造出的LR(0)分析表中含有冲突动作。文法GS的LR(0)分析表如答案表5-5-(3)所示。答案表5-5-(3) 文法GS的LR(0)分析表状态01234accr11rrr323r2r2收集于网络，如有侵权请联系管理员删除精品文档5-6 解：(1) 在文法GS中引入一个新的开始符号，且将SS作为第0个产生式添加到文法G中，从而得到G的拓广文法GS：0.SS1.SSab2. SbRSa识别文法GS全部可归前缀的DFA如

10、答案图5-6-(1)所示。a01I : Sa bSS ab6bb32aba答案图5-6-(1)识别GS全部可归前缀的DFA由答案图5-6-(1)可知，在项目集I 和 I中都存在“移进-归约”冲突。在项目集I144= RS, SSab 中, 由于FOLLOR(R)=a，FOLLOR(R)a=a ，所以其项目集的“移进归约冲突不可能通过 SLR(1)规则得到解决，从而该文法不是 SLR(1)文法。(2) 在文法GS中引入一个新的开始符号，且将SS作为第0个产生式添加到文法G中，从而得到G的拓广文法GS：收集于网络，如有侵权请联系管理员删除精品文档0.SS1.SaSAB2.SBAaABb识别文法GS

11、全部可归前缀的DFA如答案图5-6-(2)所示。S10SaI : a SABBB2aS aSABS BA baAbI44Bbb893BBAAabI4答案图 5-6-(2) 识别 全部可归前缀的DFA因为文法GS的每个项目集中都不含冲突项目，所以文法GS是 文法，故也是SLR(1)文法。因为 FOLLOW(S)=a,b,#, FOLLOW(A)=a,b,#, FOLLOW(B)=a,b,#,所以文法GS的 SLR(1)分析表如答案表5-6-(2)所示。答案表5-6-(2) 文法GS的SLR(1)分析表状态a#S1B30ss42收集于网络，如有侵权请联系管理员删除精品文档accssrsrsrsrr

12、52445424441369751011rr13r3(3) 在文法GS中引入一个新的开始符号，且将SS作为第0个产生式添加到文法G中，从而得到G的拓广文法GS：0.SS1.SaAcBdd2.SbB3. AcAd识别文法GS全部可归前缀的DFA如答案图5-6-(3)所示。收集于网络，如有侵权请联系管理员删除精品文档S109ccbBaBd2Adc5cdA 由答案图5-6-(3)可知，在项目集I ,I ,I 和 I 中都存在“移进归约”冲突。2359因为在项目集I 和 I 中, 由于 FOLLOR(A)=d,#，FOLLOR(A)c=，所以其项25目集的移进-”冲突能通过SLR(1)规则得到解决；又

13、因为在项目集I 和 I 中, 由于FOLLOR(B)=d,#，FOLLOR(B)c=，所以其39项目集的“移进归约冲突也能通过SLR(1)规则得到解决；所以文法GS是 SLR(1)文法。因为 FOLLOR(S)=#，FOLLOR(A)=d,#FOLLOR(B)=d,#，所以文法的SLR(1)分析表如答案表5-6-(3)所示。答案表5-6-(3) 文法GS的SLR(1)分析表状态as#B01223accsrr4454收集于网络，如有侵权请联系管理员删除精品文档rrr866146477rrrr332696101112rr555-7 解：在文法中引入一个新的开始符号S，且将SS作为第0个产生式添加到

14、文法G中，从而得到G的拓广文法GS：0.SS1.ScAd2.SbASca识别文法GS全部可归前缀的DFA如答案图5-7所示。S10bcAS2cc8ad4 收集于网络，如有侵权请联系管理员删除精品文档因为文法GS的每个项目集中都不含冲突项目，所以文法GS是 文文法 GS的 LR(0)分析表如答案表5-7-(a)所示。法。答案表5-7-(a) 文法GS的LR(0)分析表状态a#01234567832srr224472rr118rrrr33333因为 FOLLOR(S)=#,cFOLLOR(A)=b,c,d，所以文法GS的 SLR(1)分析表如答案表 5-7-(b)所示。答案表5-7-(b) 文法G

15、S的SLR(1)分析表状态as#01234563242rr44ss726rr11收集于网络，如有侵权请联系管理员删除精品文档78sr83rr33两个表的相同之处为：(1) 两个表的GOTO表部分完全相同。(2) 在两个表的ACTION表中，不含归约项目的项目集对应的行的元素完全相同，即第 0,2,5,7行完全相同。两个表的不同之处为：在两个表的ACTION表中，含有归约项目的项目集对应的行的元素不同，即第3,4,6,8行的元素不同。以第3行为例，答案表5-7-(a)中的所有元素都为r ；而在答2案表 5-7-(b)中 ,因为FOLLOR(S)=#,c，故仅在“#”和“c”列对应的元素为r 。2

16、5-8 解：(1) 在文法GS中引入一个新的开始符号，且将SS作为第0个产生式添加到文法G中，从而得到G的拓广文法GS：0.SS1.SAaBb2.ABA文法 GS的 LR(1)项目集及DFA如答案图5-8所示。收集于网络，如有侵权请联系管理员删除精品文档S1 A ,# ,# ,#AaI :BA ,#3bb ,b ,I :b5baa ,Bb , 文法 GS的 LR(1)分析表如答案表5-8-(1)所示。答案表5-8-(1) 文法GS的LR(1)分析表状态012345674acc6rr4r44(2) 用 LR(1)分析表对输入符号串abab的分析过程如答案表5-8-(2)所示。因为分析成功，所以符

17、号串abab是文法GS的合法句子。收集于网络，如有侵权请联系管理员删除精品文档答案表5-8-(2) 符号串abab的 LR分析过程步骤1状态栈符号栈余留输入串分析动作下一状态I0452II0#a#ab#aB#BGOTOI ,B=704GOTOI ,B=300II0#Ba#Bab#BaB#BB#BBA#BA#A04GOTOI ,B=7044GOTOI ,B=3043GOTOI ,A=603310111213GOTOI ,A=60363GOTOI ,A=2032160IIGOTOI ,S=100II0#S#acc5-9 解：(1) 在文法GS中引入一个新的开始符号，且将SS作为第0个产生式添加到文

18、法G中，从而得到G的拓广文法GS：0.SS1.SAaBb2.AAB文法 GS的 LR(1)项目集及DFA如答案图5-9-(1)所示。收集于网络，如有侵权请联系管理员删除精品文档S10AA AB , a/b/#A , a/b/#I : A , #2AA B , a/b/# aB , a/b/# b , a/b/#aa aB , a/b/# b , a/b/#Bb答案图5-9-(1) 文法GS的LR(1)项目集及DFA文法 GS的 LR(1)分析表如答案表5-9-(1)所示。因为分析表中不含多重定义的元素，所以文法GS是LR(1)文法。答案表5-9-(1) 文法GS的LR(1)分析表状态01234563accsrrsr525546r4r4(2) 在文法GS中引入一个新的开始符号，且将SS 作为第0 个产生式添加到文法G 中，从而得到G 的拓广文法GS：收集于网络，如有侵权请联系管理员删除精品文档0.SS1.SaSa2.Sa文法 GS的 LR(1)项目集及DFA如答案图5-9