0 X ε 0 ε 1 1 2 ②子集法确定化 I {X, 0, 1, 3, Y} {0, 1, 3, Y} {2} {1, 3, Y} 重新命名状态，即得： S 1 2 0 ε 3 a 0 ε I4: S’→ aS? S Y 0 I2: S→ a?S S→ ?aS S→ ?bS S→ ?a S→ a? I0 I0: S’→ ?S S→ ?aS S→ ?bS S→ ?a b S I1: S’→ S? I1 b a {0, 1, 3, Y} {0, 1, 3, Y} {1, 3, Y} {1, 3, Y} 0 2 2 {2} {2} - {2} I5: 1 S’→ bS? I3: S→ b?S S→ ?aS S→ ?bS S→ ?a S 3 3 （2）在状态I2存在“移近冲突，3 4 - -归约”因此该文法不是LR(0)文法。 4 4 3 计算S的FOLLOW集合： ③ 最小化
FOLLOW(S)= {#}
首先分为终态集和非终态集 {3} {1, 2,
I2中的冲突用FOLLOW集合可以解
4} 因为10 = 2 20 = 2 40 = 4 状态均属于
决，所以该文法是SLR(1)文法。
集合{1, 2, 4}，所以对于输入符号0不能
构造SLR(1)分析表如下：
区分开1，2，4三个状态；11 = 3 21 = 3 41
ACTION = 3状态均属于集合{3}，所以对于输入符号状态 a b 1也不能区分开1，2，4三个状态；因此最
0 s2 s3 终的状态划分即为: {3} {1, 2, 4}，其对
1 应的DFA如下图所示：
2 s2 s3 0 3 s2 s3 1 4 1 0 5 0
28解：
（1）将文法G(S)拓广为G’(S’)：
(0) S’→S (1) S→aS (2) S→bS (3) S→a
识别该文法所产生的活前缀的DFA：
# acc r3 r1 r2
29【解】 用子集法将NFA确定化，如图所示。
21
I{X}{1}{3}{2,3,Y}{3,Y}{3,4}{2,3,4,Y}{3,4,Y}Ia{1}{2,3,Y}—{2,3,Y}{2,3,Y]{3,4}{2,3,4,Y}{2,3,4,Y}Ib{3}{3,Y}{3,4}{2,3,4,Y}{3,4}{3,4,Y}{2,3,4,Y}{3,4,Y}34【解】 Sab 1）求各非终结符的 FISRT 集和 FOLLOW 12集： 014 = { (, a ) 3 2—5= { (, ), 重新命名 FIRST(L) = { a }? FIRST(S) 336a } FOLLOW(S) = {, # } 435 FOLLOW(L) = FOLLOW(S) ={ , # } 557FIRST(( L)∩{a}=66Φ 6FIRST(S , L)∩{)}=Φ 767 所以是LL（1）文法 2）预测分析表： S a确定化的DFA如下图所示：
a3a4b2bb5ab7a( S→ ( L a S→ a , } L → ) aa01bbL L→ S , L L→ S , L 6b30．解:
35 【解】 S’ ? .S S’ ? S . S bI1 S ? .A a S ? .b A c A S ? A .a S ? .d c I2 S ? .b d a A ? .d S ? b .A c b I 0S ? b .d a
A ? .d d I3
S ? d .c Follow(S)={#} A ? d . c S ? d c . Follow(A)={a,c} I4 Follow(A)∩{c}={ c} I8 I4存在冲突且I7存在冲突且Follow(A)∩{a}={ a} 所以不是SLR(1)文法
36【解】 先划分为终态集{Y}和非终态集
I={X,1,2,3}
a S ? A I5A S ? bI6d S ? b A ? dI732【解】
0（+，a, b ,T1）
1（uminus，T1，-，T2） 2（+，c, d , T3） 3（*，T2，T3，T4） 4（+，e，f，T5） 5（+，T4，T5，T6）
33【解】(1) (a,a,a)的最左推导
S=>(T) =>(T,S) =>( T,S,S) =>( S,S,S) =>(a,S,S) =>(a,a,S) =>(a,a,a)
X面对输入符号b时下一状态属于I，而1,2,3面对输入符号b时下一状态属于{Y}，故划分为{X}、{1,2,3}
非终态2和非终态3面对输入符号a的下一状态相同，而1不同，即最简状态{X}、{1}、{2，3}、{Y}。按顺序重新命名为0、1、2、3，则得到最简DFA，
22
a0ab1a2b3FOLLOW(D)={#} 因为FIRST(int)∩FIRST(real)=Φ FIRST(, id R)∩FOLLOW(R)=Φ 所以是LL（1）文法，LL（1）分析表如下： real D ? TL T ? real id L ? id R , # D T L R bint D ? TL T ? int 37．【解】 R ? , id R R ? ? １-９ 1 ０-９ 2 0 ?(其它) 3
38【解】该文法是二义文法，因为该文法存
在句子i*i+i,该句子有两棵不同的语法树如图所示。
S S i (1) 42【解】注意到状态I1存在“移进-归纳”冲突，计算S的FOLLOW集合： FOLLOW(S)={#}
{a}∩{b}∩FOLLOW(R)=Φ
可以采用SLR冲突消解法，得到如下的SLR分析表。
从分析表可以看出，表中没有冲突项，所以该文法是SLR(1)文法。 S 表1 SLR分析表 + S i * S i S + S i S i S * 状态 1 2 3 4 5 S ACTION a S1 S1 S1 答
：
语
法
b S2 S2 S2 0 i (2)
40【解】(1) (j>, A, B, 3) (2) (j, _, _, 11) (3) (j>, C, D, 5) (4) (j, _, _, 8) (5) (*, Y, Z, T1) (6) (=, T1, _, X) (7) (j, _, _, 1) (8) (+, Y, Z, T2) (9) (=, T2, _, X) (10) (j, _, _, 1) (11)
41【解】FIRST(T)={ int FOLLOW(T)={ id } FIRST(L)={ id FOLLOW(L)={ #}
FIRST(R)={ , FOLLOW(R)={ #}
FIRST(D)={ int
a 43三元式
树
+ + * / real }
} ?}
- a * b b c d e real }
23
①（-，a，-） ②（*，①，b） ③（*，b，c） ④（+，②，③） ⑤（/，d，e） ⑥（+，④，⑤）
将1，2合并用1代表，3，4合并用3代表，最终的最小化DFA如下：
a 0 b 1 b a b 3 48答：I2，I5分别如下图所示： I2 :P→a. P→.a44证明：
（1）first（AaAb）={a} first（BbBb）={b} ，有first（AaAb）∩first（BbBb）=Φ
所以根据LL（1）文法的定义，该文法是LL（1）文法。（2分） （2）为了构造识别活前缀的DFA，初态集包含如下四个项目：S→.AaAb S→.BbBa A→. B→.
但该项目中有两个可归约项目：A→. B→.，产生归约-归约冲突，而follow（A）={a，b}，follow（B）={a，b}，有follow（A）∩follow（B）≠Φ，所以使用向前看一个终结符的方法不能解决此冲突，所以该文法不是SLR（1）文法。（3分）
45答：最左推导：S=〉（T）=〉（T，S）=〉（S，S）=〉（a，S）=〉（a，（T））=〉（a，（T，S））=〉（a，（S，S））=〉（a，（a，S））=〉（a，（a，a））
最右推导： S=〉（T）=〉（T，S）=〉（T，（T））=〉（T，（T，S））=〉（T，（T，a））=〉（T，（S，a））=〉（T，（a，a））=〉（S，（a，a））=〉（a，（a，a））
句型的句柄是为加下划线的部分
46答：初始划分：II={{0，1，2}，{3，4}}（1分）
（1）考查{0，1，2}，1和2接受a，b后都转向相同的状态，且接受b后转向终态，而0接受b后转向非终态2，所以0与1，2可分，IInew={{0}，{1，2}，{3，4}}(1分)
（2）考查{3，4}，接受a，b后都转向相同的状态，所以3，4不可分。IInew={{0}，{1，2}，{3，4}}（1分）
P→.QFollow（P）={b，$} 1分 Q→.bFollow（Q）={ b，c，$} 1分 Q→.bFollow（S）={c，a} 1分 SLR（1）分析表：
Action表 a b c $ P0 S2 S5 11 Acc 2 S2 S5 43 R2 R2 4 S7 5 S6 S5 6 R6 R6 7 R1 R1 8 R3 R3 R3 9 S8 10 S12 S11 11 R4 R4 R4 12 R5 R5
49答:语法树如下： 四元式序列：
24
* + + / a d e b c
识别活前缀的DFA：（4分）
I：S′→.S 0 S→.(A) S I1：S′→S. ( ) I2：S→(.A) A→.ABB A→.B B→.b B I5： A→B. I4： B→b. A I3：S→(A.) A→A.BB B→.b b B 51解答：用D表示数字0-9，用L表示字母a-z|A-Z，则C语言标识符的正规式为： （L|_）（L|D|_）* 55解： （1）（5分）G′：S→bAS′ S′→b S′|ε
A→aA′
A′→A|ε
（2）（1分）FIRST（S）={ b } FIRST（S′）={ b，ε} FIRST（A）={a} FIRST（A′）={a，ε} FOLLOW（S）={#} FOLLOW（S′）={#} FOLLOW（A）={b，#} FOLLOW（A′）=（b，#） LL（1）分析表：
S S′ A A′ a A→aA′ A′→A ①（+，a，b，T1） ②（/，d，e，T2） ③（+，c，T2，T3） ④（*，T1，T3，T4） b
FIRST集和follow集：（1分） First（S）={（follow( S)={#} First（A）follow(A)={b,)} First（B）follow(B)={b,)}
SLR(1)分析表：（4分） 0 1 2 3 4 5 b （ S2 # S′→ ε ） S6 R4 R3 R2 ，c} ={b} ={b}
ACTION b S4 S4 R4 R3 S4 R2 # Acc R1 S16 S→bAS′7 S′→b S′ 8 56解：拓广文法：（1分） S′→S （0）
S→（A） （1） A→ABB （2）
A→B （3） B→b （4）
A′→ε A′→ε 58 Xab+-cd-/abc*+-= 60
解：拓广文法：（1分） （0）S?→S （1）S→BB （2）B→aB （3）B→b
25