第四章 习题解答 2.解： eddfbbd SAbB 1,1.1(表示第1步，用产生式1.1推导,以下同) CAbbB 2,2.1edAbbB 3,4.1edCAbbbB 4,2.1ededAbbbB 5,4.1(不匹配)edaAbbbB 5，4.2 (不匹配，回溯到edAbbB)edBfbbB 4,2.2edCSdfbbB 5,3.1ededSdfbbB 6,4.1(不匹配)edaSdfbbB 6,4.2(不匹配，回溯到edBfbbB)eddfbbB 5,3.2eddfbbCSd 6,3.1eddfbbedSd 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}   a b #  S AbS’ bS’   S’  bS’ ε  A aA’    A’ aA’ ε   G’满足LL(1)文法的条件，是LL(1)文法。LL(1)分析表如右上。 证（反证法）：假设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)文法；这与前提矛盾，假设不成立，原命题得证。 证明：设xjxj+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出现在句柄中。从而xjxj+1...xi必为句柄。反之，若xjxj+1...xi是句柄，由简单优先关系的定义，必满足上述条件。 解：为描述方便，用符号表示各非终结符：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        >    是简单优先文法。 文法为：E→A↑E | A A→T * A | T/ A | T T→V +T | V- T | V V→i | (E) 解： - * （ ） i #  - > < > < < > < >  * > < > < > <   ( < < < = <   ) > >  >  >  I > >  >  >  # < < <  <   （1）构造算符优先矩阵： （2）在（-，-）、（-，*）和（*，-）处有多重定义元素，不是算符优先文法； （3）改写方法： 将E→E-T中的减号与F→-P中的赋值运算符强制规定优先关系； 或者将F-P中的赋值运算符改为别的符号来表示； 证：(1) 用反证法。设没有短语包含b但是不包含a，则a,b一定同时位于某个短语中，从而必使得a,b同时位于同一产生式的右部，所以a=b，与G是算符优先文法（=与<不能并存）矛盾。 （2）、（3）类似可证。 31. 解： + * ↑ （ ） i #  + > < < < > < >  * > > < < > < >  ↑ > > < < > < >  ( < < < < = <   ) > > >  >  >  I > > >  >  >  # < < < <  <   （1）算符优先矩阵： （2）用Floyd方法将优先矩阵线性化得到得的优先函数为： + * ↑ ( ) i #  F 3 5 5 1 7 7 1  G 2 4 6 6 1 6 1   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如下： 状态 项目集 经过的符号 到达的状态  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） 状态 项目集 经过的符号 到达的状态  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·     解： （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   a b # S A  0 S3   1 2  1   ACC    2  S4 R1    3  R3 R3    4  R2 R2    解：识别活前缀的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 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 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} 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）分析发现的更早些。 解：求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 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