i + * ( ) # ≯ ≯ ≯ ≯ ≮ ≮ ≮ ≯ ≯ ≯ ≮ ≮ ≯ ≯ ≯ ≯ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≯ ≯ ≯ ≯ ≡ 因为该文法是OP，同时任意两个终结符的优先关系唯一，所以该文法为OPG。 (3)(+(i(的分析过程 步栈 优先关当前符剩余输入串 移进或归约 骤 系 号 1 # #≮( ( (+(i(# 移进 2 #( (≯+ + (i(# 归约 3 #F #≮+ + (i(# 移进 4 #F+ +≮( ( i(# 移进 5 #F+( (≯i i (# 归约 6 #F+F +≯i i (# 归约 7 #F #≮i i (# 移进 8 #Fi i≮( ( # 移进 9 #Fi( (≯# # 归约 10 #FiF i≯# # 归约 11 #F #≡# # 接受 5、试为下列各文法建立算符优先关系表。 E->E and T|T T->T or F|F F->not F|N N->(E)|true[答案]
算符优先关系表如下：
true false not and or ( ) # true ≯ ≯ ≯ ≯ false ≯ ≯ ≯ ≯ not ≮ ≮ ≮ ≯ ≯ ≮ ≯ ≯ and ≮ ≮ ≮ ≯ ≯ ≮ ≯ ≯ or ≮ ≮ ≮ ≮ ≯ ≮ ≯ ≯ ( ≮ ≮ ≮ ≮ ≮ ≮ ≡ ) ≯ ≯ ≯ ≯ # ≮ ≮ ≮ ≮ ≮ ≮
六
1、已知文法 :A->aAd| aAb|ε ,判断该文法是否SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。
[答案] (1)拓广文法
(0)S->A (1) A->aAd (2)A-> aAb (3)A->ε (1)构造识别活前缀的DFA
FOLLOW(A)={d,b,#}
对于状态I0：FOLLOW(A)∩{a}=Ф 对于状态I1：FOLLOW(A)∩{a}=Ф
因为，在DFA中无冲突的现象，所以该文法是SLR(1)文法。 (3)SLR(1)分析表
(4)串ab#的分析过程
步骤 1 2 3 4 5 2、设文法G为 S ? A A ? BA | ε(1)证明它是LR(1)文法；
状态栈 0 02 023 0235 01 符号栈 # #a #aA #aAb #A B ? aB | b
(2)构造它的LR(1)分析表；
(3)给出输入符号串abab的分析过程。
[答案]
(1)拓广文法G’: (0) S' ? S (1) S ? A (2) A ? BA (3) A ?εFIRST(A) = {ε, a, b} FIRST(B) = {a, b} 构造的DFA如下:
(4) B ? aB (
由项目集规范族看出，不存在冲突动作。 ∴该文法是LR(1)文法。
(2)
状态 0 1 2 3 4 5 6 7 Action a S4 S4 S4 r5 r4 B S5 S5 S5 r5 r4 # r3 acc r1 r3 r5 r2 r4 S 1 Goto A 2 6 B 3 3 7 (3)输入串abab的分析过程为： 步骤 状态栈 符号栈 (1) 0 # (2) 04 #a (3) 045 #ab (4) 047 (5) 03 (6) 034 (7) 0345 (8) 0347 (9) 033 (10) 0 336 (11) 0 36 (12) 0 2 (13) 0 1 #aB #B #Ba #Bab #BaB #BB #BBA #BA # A #S 当前字符 剩余字符串 动作 a bab# 移进 b ab# 移进 a b# B?b 归约a a b # # # # # # # b# B?aB 归约b# 移进 # 移进 归约 B?b 归约 B?aB 归约 A?ε 归约 A?BA 归约 A?BA 归约 S?A acc
3、考虑文法S?A S | b A ? S A | a (1)构造文法的LR(0)项目集规范族及相应的DFA。
(2)如果把每一个LR(0)项目看成一个状态，并从每一个形如B ? α·Xβ的状态出发画一条标记为X的箭弧刀状态B ? αX·
(3)构造文法的SLR分析表。
(4)对于输入串bab，给出SLR分析器所作出的动作。 (5)构造文法的LR(1)分析表和LALR分析表。 [答案]
(1)令拓广文法G’为 (0)S’ ? S (1)S ? A S
(2)S ? b (3)A ? S A (4)A ? a
其LR(0)项目集规范族及识别该文法活前缀的DFA如下图所示： FOLLOW(S)={#,a,b} FOLLOW(A)={a,b}
(2)显然，对所得的NFA求ε闭包，即得上面的LR(0)项目集，即DFA中的状态。 故此NFA与(a)中DFA是等价的。 (3)文法的SLR分析表如下：
action A S4 S4 S4 r2 r4 S4/ r3 S4 S4 / r1 b S3 S3 S3 r2 r4 S3/r3 S3 S3 / r1 # acc r2 r4 R1 S 1 6 7 7 6 6 goto A 2 5 2 2 5 5 状态 0 1 2 3 4 5 6 7