精品文档
2 - 0 ε a 1 a b ε + 3
（2）将（1）所得的非确定有限自动机确定化
ε a b -0 1 2 +3 1 1 3 12 2 +
-+ a 0 b a 1 + a
（3）对（2）得到的DFA化简，合并状态0和2 为状态2：
2 -+ b a 1 + a
（4）令状态1和2分别对应非终结符B和A
G: A→aB|a|ε； B→aB|bA|a|b|ε；可化简为：G: A→aB|ε；B→aB|bA|ε
四、
设将文法G改写成等价的LL(1)文法，并构造预测分析表。
G：S→S*aT|aT|*aT； T→+aT|+a
解：消除左递归后的文法G’: S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT|+a
提取左公因子得文法G’’: S→aTS’|*aTS’ S’→*aTS’|ε T→+aT’
T’→T|ε Select(S→aTS’)={a} Select(S→*aTS’)={*}
Select(S→aTS’)∩Select(S→*aTS’)=Ф Select(S’→*aTS’)={*}
Select(S’→ε)=Follow(s’)={#} 精品文档
精品文档
Select(S’→*aTS’)∩Select(S’→ε)= Ф Select(T→+aT’)={+}
Select(T’→T)=First(T) ={+}
Select(T’→ ε)=Follow(T’)={*,#}
Select(T’→T)∩Select(T’→ε)= Ф 所以该文法是LL(1)文法。 预测分析表： * + a # S →*aTS’ →aTS’ S’ →*aTS’ →ε T →+aT’ T’ → ε →T → ε
6设文法G 为：
S→A；A→BA|ε；B→aB|b 解：（1）拓广文法G’：(0) S’→S (1) S→A (2) A→BA(3) A→ε(4) B→aB (5) B→b ；a, b}；FIRST(B) = {a, b} 构造的DFA 如下:
项目集规范族看出，不存在冲突动作。∴该文法是LR(1)文法。 （2） LR(1)分析表如下：
(3)输入串abab 的分析过程为：
精品文档
FIRST(A) = {ε,
精品文档
五、 对文法G(S)：S → a | ^ | (T)；T → T，S | S
FIRSTVT(S)?{a,^,(} 答：(1) FIRSTVT(T)?{,,a,^,(}
LASTVT(S)?{a,^,)}LASTVT(T)?{,,a,^,)}
(2) 是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。（2
分）
(3) 给出输入串(a,a)#的算符优先分析过程。 步骤 1 2 3 4 5 6 7 8 9 10 栈 当前输入字符 剩余输入串 动作 # #( #(a #(N #(N, #(N,a #(N,N #(N #(N) #N ( a , , a ) ） ) # # a,a# ,a)# a)# a)# )# # # # #<( 移进 (, 归约 (<, 移进 ,) 归约 ,>) 归约 (=) 移进 )># 归约 接受 a ^ ) a ^ ( ) , # > > > > > > = > > > < ( < < < = < , < < < > > # < <
五、设有文法G[A]：
A→BCc | gDB B→bCDE |ε C→DaB | ca D→dD |ε E→gAf | c
(1) 计算该文法的每一个非终结符的FIRST集和FOLLOW集； (2) 试判断该文法是否为LL（1）文法。（15） A B 精品文档
FIRST A,b,c,d,g b FOLLOW A,c,d 精品文档 C D E A,c,d D C,g C,d,g A,b,c,g 是LL（1）文法。
2．对于文法G[S]：S?AB，A?Aa|bB，B?a|Sb求句型baSb的全部短语、直接短语和句柄？
S
句型baSb的语法树如图五(2)所示。
A B
b b B S
a
解：baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语和句柄。
3．设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，?，{A}，{C})，其中：
? (A，0)={C} ? (A，1)={A，B} ? (B，1)={C} ? (C，1)={C}。请画出状态转换距阵和状态转换图。 解：状态转换距阵为：
? A B C 0 C ? ? 1 A，B C C
状态转换图为 1 1
1 1 ABC1 0 七 已知文法G为:
（0） S′→ S （1） S → aAd （2） S → bAc （3） S → aec （4） S → bed （5） A → e
试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。 【】【答案：】 S I1：S′→S · , # I0:
S′→· S , #
a S→· aAd , # A I4： S→aA· d , I2： S→ · bAc , #
S→a · Ad , # S→ ·aec , # e I5：S→ae·精品文档 c , #S→a · ec , # S→ · bed , # A→e · , d A→· e , d d I8：S→aAd · , # c I9：S→aec · , # I10： b