第四章习题解答 2解: eddfbbd S→AbB1,1.1(表示第1步,用产生式1.1推导,以下同) CAbbB2,2.1→ edAbbB3,4.1→ edCAbbbB4,2.1→ ededAbbbB5,4.1(不匹 配)→ edaAbbbB5,4.2(不匹配,回溯到 edAbbB)→ edBfbbB4,2.2→ edcsdfbbB 5,3.1→ ededSdfbbB6,4.1(不匹配)→ edaSdfbbB6,4.2(不匹配,回溯到 edBfbbB)→ eddfbbB5,3.2= eddfbbCSd6,3.1→ eddfbbedSd7,4.1(不匹配)→ eddfbbaSd7,4.2(不匹配,回溯到 eddfbbB)→ eddfbbd6,3.2 FIRST集 FOLLOW集 S→aAB (a}+ b ) (b, #f)e →8 # 8解 (1)消除左递归性,得G S→AbSS→bS’S’→bS’|eA→aA’A’→aA 各产生式的 FIRST集和各非终结符的 FOLLOW集 FIRST集 OLLOW集 Abs [bI bs’bS E A→aA b aA G’满足LL(1)文法的条件,是LL(1)文法。LL(1)分析表如右上。 11.证(反证法):假设LL(1)文法G有形如B→aAAβ的产生式,且A→+E 及A→*a,即{e,a} CFIRST(A),根据 FIRST集 FOLLOW集的构造算法可知, FIRST(A)中一切非ε加到 FOLLOW(A)中,则a∈ FOLLOW(A);可见 FIRST(A{e}与 FOLLOW(A)的交集非空,由此可得G不是LL(1)文法;这 与前提矛盾,假设不成立,原命题得证 15证明:设xj+1-x是满足条件x1x=x+1==x1>x计+1的最左子串。由=关 系的定义,可知xx+1x必出现在某产生式的右部中。又因x1可知x1 与x不处于同一产生式,且x是某右部的首符。同理,x为某产生式的尾符 号。即存在产生式U→xy计+1-x设S→*UB,其中,0=*x1,B→*x+1 对于αU邛β可构造一语法树,并通过对其剪枝(归约),直到U出现在句柄中
第四章 习题解答 2.解： eddfbbd S AbB 1,1.1(表示第 1 步，用产生式 1.1 推导,以下同) CAbbB 2,2.1 edAbbB 3,4.1 edCAbbbB 4,2.1 ededAbbbB 5,4.1(不匹 配) edaAbbbB 5，4.2 (不匹配，回溯到 edAbbB) edBfbbB 4,2.2 edCSdfbbB 5,3.1 ededSdfbbB 6,4.1(不匹配) edaSdfbbB 6,4.2(不匹配，回溯到 edBfbbB) eddfbbB 5,3.2 eddfbbCSd 6,3.1 eddfbbedSd 7,4.1(不匹配) eddfbbaSd 7,4.2(不匹配，回溯到 eddfbbB) eddfbbd 6,3.2 4.解： 8.解： (1)消除左递归性,得 G’： S→AbS’ S→bS’ S’→bS’|ε A→aA’ A’→aA’|ε 各产生式的 FIRST 集和各非终结符的 FOLLOW 集： 产生式 FIRST 集 FOLLOW 集 S→AbS’ →bS’ {a} {b} {#} S’→bS’ →ε {b} {ε} {#} A→aA’ {a} {b} A’→aA’ →ε {a} {ε} {b} G’满足 LL(1)文法的条件，是 LL(1)文法。LL(1)分析表如右上。 11. 证（反证法）：假设 LL（1）文法 G 有形如 B→αAAβ 的产生式，且 A+ε 及 A*a,即{ε，a}FIRST(A)，根据 FIRST 集 FOLLOW 集的构造算法可知， FIRST(A)中一切非 ε 加到 FOLLOW(A)中，则 a∈FOLLOW(A)；可见 FIRST(A)-{ ε}与 FOLLOW(A)的交集非空，由此 可得 G 不是 LL(1)文法；这 与前提矛盾，假设不成立，原命题得证。 15. 证明：设 xj xj+1...xi 是满足条件 xj-1xi+1 的最左子串。由=关 系的定义，可知 xjxj+1...xi 必出现在某产生式的右部中。又因 xj-1<xj 可知 xj-1 与 xj 不处于同一产生式，且 xj 是某右部的首符。同理，xi 为某产生式的尾符 号。即存在产生式 U→xjxj+1...xi 设 S* αUβ, 其中，α*... xj-1, β* xi+1... 对于 αUβ 可构造一语法树，并通过对其剪枝（归约），直到 U 出现在句柄中。 a b # S AbS’ bS’ S’ bS’ ε A aA’ A’ aA’ ε
从而xy+1…x必为句柄。反之,若xy+1x是句柄,由简单优先关系的定 义,必满足上述条件。 16.解:为描述方便,用符号表示各非终结符:D=L=,V=T=,a=VAR,则消去V,并采用分层法改写文法,得到:D→aW:T W→LL→L,jT→rnbc 其全部简单优先关系是 D rIn/blc D rIn blc 是简单优先文法。 19.文法为:E→A↑E|AA→T*A|TA|TT→V+T|VT|vV→i|(E) 20.解: _日(D)构造算符优先知阵 (2)在(-,-)、(-,*)和(*,-)处有多 网PP【P重定义元素,不是算符优先文法 *><>·或者将FP中的赋值运算符改为别的符号来表 小; 6.证:(1)用反证法。设没有短语包含b但是不包含a,则ab一定同时位于某个短语中 从而必使得ab同时位于同一产生式的右部,所以a=b,与G是算符优先文法(=与<不 能并存)矛盾 (2)、(3)类似可证。 31.解 (1)算符优先矩阵: 日酝 (2)用 Floyd方法将优先矩阵线性化得到得的 优先函数为: 干干日
从而 xjxj+1...xi 必为句柄。反之，若 xjxj+1...xi 是句柄，由简单优先关系的定 义，必满足上述条件。 16. 解：为描述方便，用符号表示各非终结符：D=,L=, V= ,T=，a=VAR,则消去 V，并采用分层法改写文法，得到：D→aW:T; W→L L→L,i|i T→r|n|b|c 其全部简单优先关系是： D W T L a : ; , i r|n|b|c D W = T = L > = a = > > = i r|n|b|c > 是简单优先文法。 19. 文法为：E→A↑E | A A→T * A | T/ A | T T→V +T | V- T | V V→i | (E) 20. 解： （1）构造算符优先矩阵： （2）在（-，-）、（-，*）和（*，-）处有多 重定义元素，不是算符优先文法； （3）改写方法： • 将E→E-T中的减号与F→-P中的赋值运算符强 制规定优先关系； • 或者将 F-P 中的赋值运算符改为别的符号来表 示； 26. 证：(1) 用反证法。设没有短语包含 b 但是不包含 a，则 a,b 一定同时位于某个短语中， 从而必使得 a,b 同时位于同一产生式的右部，所以 a=b，与 G 是算符优先文法（=与 * > > > > I > > > > # * > > ↑ > > ( > > > > I > > > > > # < < < < <
33.解: (1)优先矩阵如下: (2)用Bel1方法求优先函数的过程如下 (3)显然,文法不是算符优先文法,所以不能线性化 35.解 (1)识别全部活前缀的DFA如下:(以表格的形式来表示,很容易可以转化为 图的形式,本章中其余的题目也是采用这种形式表示。) 状态项目集经过的符号到达的状态 S→·aSb IO S I2 I1s’→S S→a·Sb I2 ab SSs b I5 13 I4S→ab I5S→aSb L6s-asc· (2)识别全部活前缀的DFA如下
33. 解： （1）优先矩阵如下： [ ] a # [ > = ] > > a < # < < < （2）用 Bell 方法求优先函数的过程如下： 啊 [ ] a # f 5 7 5 1 g 5 5 6 1 （3）显然，文法不是算符优先文法, 所以不能线性化。 35. 解： （1）识别全部活前缀的 DFA 如下：（以表格的形式来表示，很容易可以转化为 图的形式，本章中其余的题目也是采用这种形式表示。） 状态 项目集 经过的符号 到达的状态 I0 S’ →·S S→·aSb S→·aSc S→·ab S a I1 I2 I1 S’ →S· I2 S→a·Sb S→a·Sc S→a·b S→·aSb S→·aSc S→·ab S a b I3 I2 I4 I3 S→aS·b S→aS·c b c I5 I6 I4 S→ab· I5 S→aSb· I6 S→aSc· （2）识别全部活前缀的 DFA 如下：
状态项目集经过的符号到达的状态 II I2 I1 S I2 Aca 15 I3|S→cA B 16 BAcba I10 I7 B→·b I 8 15 I5 I6S→ccB B→c·cB I7 CAa I 9 I10 15 B Ill I10 B 1 9 B→·b BAcba 15 Il|B→ccB 所求的LR(0)项目规范族C={I0,Il,…,Il}
状态 项目集 经过的符号 到达的状态 I0 S’ →·S S→·cA S→·ccB S c I1 I2 I1 S’ →S· I2 S→c·A S→c·cB A→·cA A→·a A c a I3 I4 I5 I3 S→cA· I4 S→cc·B A→c·A B→·ccB B→·b A→·cA A→·a B A c b a I6 I10 I7 I8 I5 I5 A→a· I6 S→ccB· I7 B→c·cB A→c·A A→·cA A→·a C A a I9 I10 I5 I8 B→b· I9 B→cc·B A→c·A B→·ccB B→·b A→·cA A→·a B A c b a I11 I10 I7 I8 I5 I10 A→cA· I11 B→ccB· 所求的 LR(0)项目规范族 C={I0,I1,…,I11}
(3) 目集陉过的符号到达的状态 s→·aSSb IO I2 I1 S S→a·SSb I3|s→·aSSb I2 I 3 I4s→·aSSb C s→·aSSS S→aSS·b S→aSS·S I3 b I2 I6s→aSSb I7S→aSSS 吠态[项目集过的符号倒达的状态 A I2 I 3 I I2 b
（3） 状态 项目集 经过的符号 到达的状态 I0 S’ →·S S→·aSSb S→·aSSS S→·c S c a I1 I2 I3 I1 S’ →S· I2 S→c· I3 S→a·SSb S→a·SSS S→·aSSb S→·aSSS S→·c S c a I4 I2 I3 I4 S→aS·Sb S→aS·SS S→·aSSb S→·aSSS S→·c S c a I5 I2 I3 I5 S→aSS·b S→aSS·S S→·aSSb S→·aSSS S→·c S a b c I7 I3 I6 I2 I6 S→aSSb· I7 S→aSSS· （4） 状态 项目集 经过的符号到达的状态 I0 S’ →·S S→·A A→·Ab A→·a S A a I1 I2 I3 I1 S’ →S· I2 S→A· S→A·b b I4 I3 A→a· I4 S→Ab·
36.解 (1)是LR(0)文法,其SLR(1)分析表如下: FOLLOW(S)={#,b,ck ACTION GOTO b S S2 2345 RI RI RI (2)是LR(0)文法,其SLR(1)分析表如下 FOLLOW (S)=FOLLOW (A)=FOLLOW(B)=#] ACTION GOTO abc#saB acc 2S5 $4 4S5S8S7 7s5■s91 R6 9|S5S8S7 10[11 10 11 R5 (3)是LR(0)文法,其SLR(1)分析表如下: FOLLOW(S)={#,a,b,c} ACTION GOTO ACC R3 R3 R3 5 457 RI 「7RR2R2R2 (4)因为I2中含有冲突项目,所以不是LR(0)文法,其SLR(1)分析表如下 FOLLOW(S)={#∩{b}=中(所以可以用SLR(1)规则解决冲突), FOLLOW(A)={b,#
36. 解： （1）是 LR(0)文法，其 SLR(1)分析表如下：FOLLOW(S)={#,b,c} ACTION GOTO a b c # S 0 S2 1 1 ACC 2 S2 S4 3 3 S5 S6 4 R3 R3 R3 5 R1 R1 R1 6 R2 R2 R2 （2）是 LR(0)文法，其 SLR(1)分析表如下： FOLLOW(S)=FOLLOW(A)=FOLLOW(B)={#} ACTION GOTO a b c # S A B 0 S2 1 1 acc 2 S5 S4 3 3 R1 4 S5 S8 S7 10 6 5 R4 6 R2 7 S5 S9 10 8 R6 9 S5 S8 S7 10 11 10 R3 11 R5 （3）是 LR(0)文法，其 SLR(1)分析表如下：FOLLOW(S)={#,a,b,c} ACTION GOTO a b c # S 0 S3 S2 1 1 ACC 2 R3 R3 R3 R3 3 S3 S2 4 4 S3 S2 5 5 S3 S6 S2 7 6 R1 R1 R1 R1 7 R2 R2 R2 R2 （4）因为 I2 中含有冲突项目，所以不是 LR(0)文法，其 SLR(1)分析表如下： FOLLOW(S)={#}∩{b}=φ(所以可以用 SLR(1)规则解决冲突), FOLLOW(A)={b,#}
ACTION GOTO 01234 ACC R3 39解:识别活前缀的DFA及LR(0分析表 狀态「项目集陉过的符号倒达的状 S→·AMAS cAd S→·b A→·ASc Aab 654B A II b I2|A→Sb· Ad AScS I3|A→·cd s→·AAd Aabcd 8954B7 Ad SSA b 15 SAA ASc I6|A→·cd SAab I10 S→·AAd ad b I7 SAA I9S→cA·d IlI
ACTION GOTO a b # S A 0 S3 1 2 1 ACC 2 S4 R1 3 R3 R3 4 R2 R2 39. 解：识别活前缀的 DFA 及 LR(0)分析表： 状态 项目集 经过的符号到达的状态 I0 S’ →·S S→·AAd S→·cAd S→·b A→·ASc A→·Sb A→·cd A→·a S A a b c I1 I6 I5 I4 I3 I1 S’ →S· A→S·b b I2 I2 A→Sb· I3 S→c·Ad A→c·d A→·ASc A→·Sb A→·cd A→·a S→·AAd S→·cAd S→·b S A a b c d I8 I9 I5 I4 I3 I7 I4 S→b· I5 A→a· I6 S→A·Ad A→A·Sc A→·ASc A→·Sb A→·cd A→·a S→·AAd S→·cAd S→·b S A a b c I11 I10 I5 I4 I3 I7 A→cd· I8 A→S·b b I2 I9 S→cA·d S I11
A→A·S I10 S→A·Ad Aabcd 54B A→·ASc A→·cd S→AA·d A→A·Sc S→·AAd I10 I10 →·cAd b A→·ASc Aabcd 54B A→·Sb I13 A d Ill A→AS·cb I12 I12A→ASc· Il3S→Ad I14|S→cAd ACTION GOTO 3|r3r3|r3|r3 r6r6r6r6r6l1110 9ss4s3■0 10s5s4s3s131110 13rlrlrl rl rl 14[r2r2r2r2r2 SLR(1)分析法:FOLL0wW(S)={c,b,#} FOLLOW(A)={a,b,c,d}
A→A·Sc S→A·Ad S→·AAd S→·cAd S→·b A→·ASc A→·Sb A→·cd A→·a A a b c d I10 I5 I4 I3 I14 I10 S→AA·d A→A·Sc S→A·Ad S→·AAd S→·cAd S→·b A→·ASc A→·Sb A→·cd A→·a S A a b c d I11 I10 I5 I4 I3 I13 I11 A→AS·c A→S·b b c I2 I12 I12 A→ASc· I13 S→AAd· I14 S→cAd· ACTION GOTO a b c d # S A 0 s5 s4 s3 1 6 1 s2 acc 2 r5 r5 r5 r5 r5 3 s5 s4 s3 s7 8 9 4 r3 r3 r3 r3 r3 5 r7 r7 r7 r7 r7 6 s5 s4 s3 7 r6 r6 r6 r6 r6 11 10 8 s2 9 s5 s4 s3 s14 11 10 10 s5 s4 s3 s13 11 10 11 s2 s12 12 r4 r4 r4 r4 r4 13 r1 r1 r1 r1 r1 14 r2 r2 r2 r2 r2 SLR(1)分析法：FOLLOW(S)={c,b,#} FOLLOW(A)={a,b,c,d}
CTION GOTO 2 卧 s5 s4s3s7 r3|r3 7|r6r6r6r611l10 11|10 10s5s4 1110 11 s2 s12 12|R4r4 13 两表的异同:两表都用ACTI0N表和G0T0表反映了移进、归约(包括接受)的状 态和动作。不同之处在于SLR(1)增加了在归约的时候考虑向前符号a以解释可 能岀现的“移进一一归约”冲突;SLR(1)的分析较稀疏些,原因是填写归约项 时,并不是在一状态对应行上全部填写归约动作,而是考虑了相应非终结符的 FOLLOW集因素。另外,在分析效率上SLR(1)分析的效率更高一些,因为在发 现错误方面,SLR(1)比LR(0)分析发现的更早些。 40.解:求LR(1)项目集和状态转换表 状态项目集过的符号倒达的状态 S,# S→·A,# 10/A→·BA,# →·aB,#,a,b ABab 2B4巧 B→·b,#,a,b 「S”→S·,# I2|S→A·,# A→B·A,# I3 I3|A→·BA,# aB, #, a, b B→·b,#,a,b B # a b aB # a b ABabBab B→·b,#,a,b I5B→b·,#,a,b 6[A→BA,#
ACTION GOTO a b c d # S A 0 s5 s4 s3 1 6 1 s2 acc 2 r5 r5 r5 r5 3 s5 s4 s3 s7 8 9 4 r3 r3 5 r7 r7 r7 r7 6 s5 s4 s3 7 r6 r6 r6 r6 11 10 8 s2 9 s5 s4 s3 s14 11 10 10 s5 s4 s3 s13 11 10 11 s2 s12 12 R4 r4 r4 r4 13 r1 r1 14 r2 r2 两表的异同：两表都用 ACTION 表和 GOTO 表反映了移进、归约（包括接受）的状 态和动作。不同之处在于 SLR(1)增加了在归约的时候考虑向前符号 a 以解释可 能出现的“移进——归约”冲突；SLR（1）的分析较稀疏些，原因是填写归约项 时，并不是在一状态对应行上全部填写归约动作，而是考虑了相应非终结符的 FOLLOW 集因素。另外，在分析效率上 SLR（1）分析的效率更高一些，因为在发 现错误方面，SLR（1）比 LR（0）分析发现的更早些。 40. 解：求 LR(1)项目集和状态转换表： 状态 项目集 经过的符号到达的状态 I0 S’→·S,# S→·A,# A→·BA,# A→·,# B→·aB,#,a,b B→·b,#,a,b S A B a b I1 I2 I3 I4 I5 I1 S’ →S·,# I2 S→A·,# I3 A→B·A,# A→·,# A→·BA,# B→·aB,#,a,b B→·b,#,a,b A B a b I6 I3 I4 I5 I4 B→a·B,#,a,b B→·aB,#,a,b B→·b,#,a,b B a b I7 I4 I5 I5 B→b·,#,a,b I6 A→BA·,#
I7 相应的LR(1)分析表为 STATE ACTION 0T0 b#SIA B 0 S4IS5 R3 23 23456 R5R5R5 R2 用LR(1)分析表对输入符号串abab的分析过程 步骙状悉践中符号余留符号分析动侑下一状态 0 ababa bab# 31045[#abah#R5 4|047#aB 503 ab#t 6034#B b# 7 b345 #Bab R4 0347#BaB R4 4573457366 033#B 10k336#BA R2 l1036#BA 1302 ####### 2D# acc
I7 B→aB·,#,a,b 相应的 LR(1)分析表为： STATE ACTION GOTO a b # S A B 0 S4 S5 R3 1 2 3 1 ACC 2 R1 3 S4 S5 R3 6 3 4 S4 S5 7 5 R5 R5 R5 6 R2 7 R4 R4 R4 用 LR(1)分析表对输入符号串 abab 的分析过程： 步骤状态栈中符号余留符号分析动作下一状态 1 0 # abab# S4 4 2 04 #a bab# S5 5 3 045 #ab ab# R5 7 4 047 #aB ab# R4 3 5 03 #B ab# S4 4 6 034 #Ba b# S5 5 7 0345 #Bab # R4 7 8 0347 #BaB # R4 3 9 033 #BB # R3 6 10 0336 #BBA # R2 6 11 036 #BA # R2 2 13 02 #A # R1 1 12 01 #S # acc