编译原理第四章 习题与答案2.doc

1、第五章 习题5-1 设有文法 GS：SA/ AaAAS/(1) 找出部分符号序偶间的简单优先关系。(2) 验证 GS不是简单优先文法。5-2 对于算符文法 GS：SE EE-TT TT*FF F-PP P(E)i(1) 找出部分终结符号序偶间的算符优先关系。(2) 验证 GS不是算符优先文法。5-3 设有文法 GE：EE 1 E1E 1+T1|T1 T1T TT*F|F F(E)|i 其相应的简单优先矩阵如题图 5-3 所示，试给出对符号串（i+i）进行简单优先分析的过程。= = = = E E1 T1 T F + * ( ) i EE1T1TF+*()i 题图 5-3 文法 GE的简单优先矩

2、阵5-4 设有文法 GE：EE+T|TTT*F|FF(E)|i其相应的算符优先矩阵如题图 5-4 所示。试给出对符号串（i+i）进行算符优先分析的过程。( i * + ) #( i * + ) # 题图 5-4 文法 GE的算符优先矩阵5-5 对于下列的文法，试分别构造识别其全部可归前缀的 DFA 和 LR(0)分析表，并判断哪些是 LR(0)文法。(1) SaSbaScab(2) SaSSbaSSSc(3) SA AAba5-6 下列文法是否是 SLR(1)文法？若是，构造相应的 SLR(1)分析表，若不是，则阐明其理由。(1) SSabbR RSa(2) SaSABBA AaAB Bb(3

3、) SaAbB AcAd BcBdd5-7 对如下的文法分别构造 LR(0)及 SLR(1)分析表，并比较两者的异同。ScAdb AASca 5-8 对于文法 GS:SA ABA BaBb (1) 构造 LR(1)分析表；(2) 给出用 LR(1)分析表对输入符号串 abab 的分析过程。5-9 对于如下的文法，构造 LR(1)项目集族，并判断它们是否为 LR(1)文法。(1) SA AAB BaBb(2) SaSaa第 4 章 习题答案 25-1 解：(1) 由文法的产生式和如答案图 5-1(a)所示的句型 Aa的语法树，可得 G 中的部分优先关系如答案图 5-1(b)所示。答 案 图 5-

4、1(a) 句 型 A/a/的 语 法 树 (b) 部 分 符 号 序 偶 间 的 优 先 关 系/S/A aAA SA /A A A / (2) 由答案图 5-1(b)可知，在符号 A 和/之间，即存在等于关系，又存在低于关系，故文法 GS不是简单优先文法。5-2 解：(1) 由文法 GS的产生式可直接看出：（ ） =此外，再考察句型P(E)和 i*(T*F)的语法树 (见答案图 5-2(a)及(b)。由答案图 5-2(a)可得： , , ( 由答案图 5-2(b)可得： i * , * ( , ( * , * ） 答 案 图 5-2S- TE- PTFE FE )(- PST * F( E

5、)ETF*T FTPi(a)句 型 -P-(E)的 语 法 树 (b)句 型 i*(T*F)的 语 法 树(2) 由答案图 5-2(a)可知，在终结符号和之间，存在两种算符优先关系： , 故文法 GS不是算符优先文法。5-3 解：对符号串(i+i)进行简单优先分析的过程如答案表 5-3 所示。因为分析成功，所以符号串(i+i)是文法 GE的合法句子。答案表 5-3 符号串(i+i)的简单优先分析过程步骤 分析栈 关系当前符号余留输入串句柄所用产生式0 # 低于 （ i+i)# 1 #( 低于 i +i)# 2 #(i 优于 + i)# i Fi3 #(F 优于 + i)# F TF4 #(T

6、优于 + i)# T T1T5 #(T1 优于 + i)# T1 E1T 16 #(E1 等于 + i)# 7 #(E1+ 低于 i )# 8 #(E1+i 优于 ) # i Fi9 #(E1+F 优于 ) # F TF10 #(E1+T 优于 ) # T T1T11 #(E1+T1 优于 ) # E1+T1 E1E 1+T112 #(E1 优于 ) # E1 EE 113 #(E 等于 ) # 14 #(E) 优于 # (E) F(E)15 #F 优于 # F TF16 #T 优于 # T T1T17 #T1 优于 # T1 E1T 118 #E1 优于 # E1 EE 119 #E 优于

7、#分析成功5-4 解：对符号串(i+i)进行算符优先分析的过程如答案表 5-4 所示。 因为分析成功，所以符号串(i+i)是文法 GE的合法句子。句子(i+i)及其分析过程中所得句型的语法树如答案图 5-4 所示。答案表 5-4 符号串（i+i)的算符优先分析过程步骤 分析栈当前栈顶终结符号优先关系当前输入符号余留输入串最左素短语0 # # （ i+i)# 1 # ( （ i +i)# 2 # ( i i + i)# i3 # (F ( + i)# 4 # ( F+ + i )# 5 # ( F+ i i ) # i6 # ( F+F + ) # F+F7 # (E ( ) # 8 # ( E

8、) ) # (E)9 #F # #分析成功+ T( )E ETFi FiETF+ T( )E ETF FETF ( )EETF答 案 图 5-4 句 子 (i+i) 及 其 分 析 过 程 中 所 得 句 型 的 语 法 树5-5 解：(1) 在文法 GS中引入一个新的开始符号 S，且将 SS 作为第 0 个产生式添加到文法 G 中，从而得到 G 的拓广文法 GS：0.SS 2.SaSc1.SaSb 3.Sab识别文法 GS全部可归前缀的 DFA 如答案图 5-5-(1)所示。答 案 图 5-5-(1) 识 别 GS全 部 可 归 前 缀 的 DFAI0: S SS aSbS aScS abI

9、1: S S SI3: S aSbS aSc I6: S aScSI2: S aSbS aScS abS aSbS aScS ab I4: S abaaI5: S aSbbbc因为文法 GS的每个 LR(0)项目集中都不含冲突项目，所以文法 GS是 LR(0)文法，故可构造出不含冲突动作的 LR(0)分析表如答案表 5-5-(1)所示。答案表 5-5-(1) 文法 GS的 LR(0)分析表ACTION GOTO状态a b c # S0123456s2 s2r3 r1r2 s4s5r3r1 r2s6r3r1r2accr3r1r213(2) 在文法 GS中引入一个新的开始符号 S，且将 SS 作为

10、第 0 个产生式添加到文法 G 中，从而得到 G 的拓广文法 GS：0.SS 2.SaSSS1.SaSSb 3.Sc识别文法 GS全部可归前缀的 DFA 如答案图 5-5-(2)所示。答 案 图 5-5-(2) 识 别 GS全 部 可 归 前 缀 的 DFAI0: S SS aSbS aSSS cI1: S S SI4: S aSSbS aSSS aSbS aSSS cI6: S aSbcI2: S aSbS aSSS aSbS aSSS cI7: S aSSaaI3: S cc bSS ca I5: S aSbS aSSS aSbS aSSS ccSa因为文法 GS的每个 LR(0)项目集中

11、都不含冲突项目，所以文法 GS是 LR(0)文法，故可构造出不含冲突动作的 LR(0)分析表如答案表 5-5-(2)所示。答案表 5-5-(2) 文法 GS的 LR(0)分析表ACTION GOTO状态a b c # S0123s2 s2 r3 r3s3s3 r3accr3144567s2 s2r1r2 r1 r2s3s3r1r2r1r257(3) 在文法 GS中引入一个新的开始符号 S，且将 SS 作为第 0 个产生式添加到文法 G 中，从而得到 G 的拓广文法 GS：0.SS 2.AAb1.SA 3.Aa识别文法 GS全部可归前缀的 DFA 如答案图 5-5-(3)所示。答 案 图 5-5-(3) 识 别 GS全 部 可 归 前 缀 的 DFAI1: S S SI4: A Aba I2: S A A A bAI3: A a bI0: S SS AA AbA a因为在 LR(0)项目集 I2中含有移进-归约冲突项目，所以文法 GS不是 LR(0)文法，故构造出的 LR(0)分析表中含有冲突动作。文法 GS的 LR(0)分析表如答案表 5-5-(3)所示。答案表 5-5-(3) 文法 GS的 LR(0)分析表ACTION GOTO状态a b # S A01s3 acc1 2