第四章习题解答 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-1<xj=xj+1=...=xi >xi+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重定义元素,不是算符优先文法 *><><|>< (3)改写方法: 将E→E-T中的减号与F→-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 是算符优先文法（=与<不 能并存）矛盾。 （2）、（3）类似可证。 31. 解： （1）算符优先矩阵： （2）用 Floyd 方法将优先矩阵线性化得到得的 优先函数为： + * ↑ ( ) i # F 3 5 5 1 7 7 1 G 2 4 6 6 1 6 1 - * （ ） i # - > < > < < > < > * > < > < > < ( < < < = < ) > > > > I > > > > # < < < < + * ↑ （ ） 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·