5、 已知文法G[S]为： S→aAd|；Bd|aB↑|；A↑ A→a B→a ① 试判断G[S]是否为LALR(1)文法 ② 当一个文法是LR(1)而不是LALR(1)时，那么LR(1)项目集的同心集合并后会出现哪几种冲突，请说明理由。
6、 将文法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 S’Ta, N S’ S’Ta, N T T’ ε, P a #
7、 已知文法G[S]：
T’a, N T, P TS’T, N ε, N # ε, P ε, P OK S→ UTa | Tb T→ S | Sc | d U→ US | e
(1) 试判断G是LR(0)，SLR(1)，LALR(1)还是LR(1)，说明理由。 (2) 构造相应的分析表。
解：
(1) 首先拓广文法为G'，增加产生式S'→S
(0) S'→S (1) S→UTa (2) S→Tb (3) T→S (4) T→Sc (5) T→d (6) U→US (7) U →e G′的LR(0)项目集族及识别活前缀的DFA如下图所示：
（2）在I1中：
S' →S.为接受项目，T →S. 为归约项目，T →S.c为移进项目，存在接受-归约和移进-归约冲突，因此所给文法不是LR(0)文法。 在I1中：
Follow(S') ∩ Follow(T)= { #} ∩{a ，b}=
Follow(T) ∩{ c}= { a ，b} ∩{c}= 在I8中：
Follow(U) ∩ Follow(T) ∩{ c}={d,e}∩{ a ，b} ∩{c}=
所以在I1中的接受-归约和移进-归约冲突与I8中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法。 构造的SLR(1)分析表如下： 状态(State) 0 1 2 3 4 5 6 7 8 9 10 8、 文法G及其LR分析表如下，请给出对串dada#的分析过程。
G: S → VdB ①
V → e ② V → ε ③ B → a ④ B → Bda ⑤ B → ε ⑥ 状态 0 1 2 3 4 5 6 7 8 ACTION d S4 r2 r6 r4 S7 r5 e a S5 S8 # acc r6 r4 r1 r5 S 1 r3 S3 GOTO B 6 V 2 Action a b c d e # S5 S4 r3 r3 S6 Acc S5 S4 S9.................. r7 r7 r5 r5........................ r4 r4......................... S10 S9......................... r3 r3. S6 r6 r6...... r2 r2. r2 r2 r2 r2 r1 r1. r1 r1 r1 r1 Goto S U T 1 2 3 . 8 2 7 解：对输入串dada#的分析过程 步骤 状态栈 1 0 符号栈 # 剩余输入符号 动作 dada# 用V →ε归约 2 3 4 5 6 7 8 9 02 024 0245 0246 02467 024678 0246 01 #V #Vd #Vda #VdB #VdBd #VdBda #VdB #S dada# ada# da# da# a# # # # 移进 移进 用B →a归约 移进 移进 用B →Bda 归约 用S →VdB 归约 接受 9、 设有文法G[S]: S ? LaR|R L ? bR|c R ? L
判断该文法是否为LR(1)文法。若是则给出它的LR(1)状态机以及LR分析表。
LR(1)状态机如下：
因为状态机中没有冲突，所以是LR(1)文法。 LR(1)分析表如下： (1) S? LaR (2) S? R (3) L? bR (4) L? c
(5) R? L
1 2 3 4 5 6 7 8 9 10 11 12 13 14 a R4 S7 R5 R3 b S6 S6 S12 S12 c S4 S4 S13 S13 # Acc R2 R4 R5 R5 R3 R1 R5 R4 R3 S 2 L 5 8 11 11 14 R 3 9 10
10、 证明下面文法是SLR(1)文法，并构造其SLR分析表。
E?E + T | T T?T F | F F?F* | a | b
11、 证明下面文法是SLR(1)文法, 并构造其SLR分析表. E ? E + T (1) E ?T (2) T ? T F (3) T ?F (4) F ? F* (5) F ? a (6) F ? b (7)