第四章 语法分析 4.30设文法G为S→A (a)证明它是LR(I)文法， b)构造它的LR()分析表： (C)给出输入符号串abb的分析过程。 解：(a)拓 0)S→S ()S→A (2)ABA (3)A→E 4④B→aB (5)B→b FIRST(A)=(e,a,b FIRST(B)=(a,b} I0={[S'→S,$.[S→A,S],[A→BA,s,[A→，$]， [B→aB,a/b/S,[B→b,a/b/] I1={[s→S·,$]} I2={[S→A:,$]} I3={[A→BA,$],[A→BA,$],[A→·，s】,[B→aB,a/b/S], [Bb,a/b/s]) I4={B→aB,a/b/],[B→aB,a/b/],[B→b,a/s]》 I5={B→b·,a/b/S]} I6={A→BA·,S]} I7={[B→aB,a/b/s]} 由项目集规范族看出，不存在冲突动作 该文法是LR)文法， b)识别该文法所有活前爱的DFA如下图所示： I1 (I2 (IO A 4 (I6 I3 a I5 I4 17
第四章 语法分析 4.30 设文法 G 为 S → A A → BA | ε B → aB | b (a) 证明它是 LR(1)文法； (b) 构造它的 LR(1)分析表； (c) 给出输入符号串 abab 的分析过程。 解：（a）拓广文法 G’: (0) S → S (1) S → A (2) A → BA (3) A →ε (4) B → aB (5) B → b FIRST(A) = {ε, a, b} FIRST(B) = {a, b} I0 = { [S’→•S, $], [S→•A, $], [A→•BA, $], [A→•, $], [B→•aB, a/b/$], [B→•b, a/b/$]} I1 = {[S’→S•, $]} I2 = {[S→A•, $]} I3 = {[A→B•A, $], [A→•BA, $], [A→•, $], [B→•aB, a/b/$], [B→•b, a/b/$]} I4 = {[B→a•B, a/b/$], [B→•aB, a/b/$], [B→•b, a/b/$]} I5 = {[B→b•, a/b/$]} I6 = {[A→BA•, $]} I7 = {[B→aB•, a/b/$]} 由项目集规范族看出，不存在冲突动作。 ∴该文法是 LR(1)文法。 (b) 识别该文法所有活前缀的 DFA 如下图所示： I0 I1 I2 I3 I4 I6 I5 I7 S A B b a b a B A b a B
LR(1)分析表如下： STATE B S4 35 S4 S5 S4 S5 r5 r5 r4 r4 4 (c)输入串abab的分析过程为 痛入 动作相 10 20a4 babs Shift 30a4b5 ab reduce by B→b 4B Ba 160B3a4 (7)0B3a4b5 reduce by B→t 803B reduce by B 00B3B3A6 1110B3A6 reduce by A>BA (12)0A2 reduce by S→A 13)0S1 acc 4.31为下面的文法构造它的LR(1)项目集规范族，并判断它是否为L(1)文法？若是，请 构造它的分析表。 →E E→E+TIT T→(E)a 解：文法的拓广文法G为：0)S)S 1S3E (②E→E+T (3)E→T (4)T→(E) (5)T)a 该文法的LR(1)项目集规范族为： I0={S→S,】,[→E,】,[E→E+T,$+],[E→T,$+] [T(E),$+],[T→a,$+} 1={S→S·,$]} 2={S→E·,$],[EE+T,$|+]}
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 (c) 输入串 abab 的分析过程为： 栈 输入 动作 (1)0 abab$ Shift (2)0a4 bab$ Shift (3)0a4b5 ab$ reduce by B→b (4)0a4B7 ab$ reduce by B→aB (5)0B3 ab$ Shift (6)0B3a4 b$ Shift (7)0B3a4b5 $ reduce by B→b (8)0B3a4B7 $ reduce by B→aB (9)0B3B3 $ reduce by A→ε (10)0B3B3A6 $ reduce by A→BA (11)0B3A6 $ reduce by A→BA (12)0A2 $ reduce by S→A (13)0S1 $ acc 4.31 为下面的文法构造它的 LR(1)项目集规范族，并判断它是否为 LR(1)文法？若是，请 构造它的分析表。 S → E E → E + T | T T → ( E ) | a 解：文法的拓广文法 G’为：(0) S’ → S (1) S → E (2) E → E + T (3) E → T (4) T → ( E ) (5) T → a 该文法的 LR(1)项目集规范族为： I0 = {[S’→•S, $], [S→•E, $], [E→•E+T, $|+], [E→•T, $|+], [T→•(E), $|+], [T→•a, $|+]} I1 = {[S’→S•, $]} I2 = {[S→E•, $], [E→E•+T, $|+]}
B=E→T,$1+]} 4={T→E),$+,E→E+T,)+1E→T,)川+]，[T→（®，）+]， T*a, 5=T今a,s+] l6={E→E+T,s+],[T→(E),$+],[T→a,s|+} I7={T→(E),$+],[E→E+T,)+]》 8=E→T,)+]) 9=T(~E) ,[E→E+T,)+,[ET,)川+，[T→(),)+] 10=T今a,)l+]} 11={EE+T,s引+]} I12=T→E).+1月 3={E→E+T )+1,[T,)川+1，[Ta,)+} 14={T→E,)+], [E→E+灯，)川+]) I15={E→E+T,)+]】 16={T→(E)·,)+]} 识别该文法所有活前缀的DA如下图所示： 1) 12 I3 I12 15 I7 13 14 16 I9 114 16 不存在冲突入口，该文法是LR(I)文法。 造LR(1)分析表如下： action goto STATE 0 95 ac 3 r3 S10 r5 r5 6 S5 S4 11
I3 = {[E→T•, $|+]} I4 = {[T→(•E), $|+], [E→•E+T, )|+], [E→•T, )|+], [T→•(E), )|+], [T→•a, )|+]} I5 = {[T→a•, $|+]} I6 = {[E→E+•T, $|+], [T→•(E), $|+], [T→•a, $|+]} I7 = {[T→(E•), $|+], [E→E•+T, )|+]} I8 = {[E→T•, )|+]} I9 = {[T→(•E), )|+}, [E→•E+T, )|+], [E→•T, )|+], [T→•(E), )|+], [T→•a, )|+]} I10 = {[T→a•, )|+]} I11 = {[E→E+T•, $|+]} I12 = {[T→(E)•, $|+]} I13 = {[E→E+•T, )|+], [T→•(E), )|+], [T→•a, )|+]} I14 = {[T→(E•), )|+], [E→E•+T, )|+]} I15 = {[E→E+T•, )|+]} I16 = {[T→(E)•, )|+]} 识别该文法所有活前缀的 DFA 如下图所示： I0 I1 I10 I9 I2 I3 I5 I4 I14 I6 I12 I7 I8 I16 I11 I13 I15 S a ( E T a ( a ( + a ( E T T E ) + ) T + T ( a 不存在冲突入口，∴该文法是 LR(1)文法。 构造 LR(1)分析表如下： STATE action goto a + ( ) $ S E T 0 S5 S4 1 2 3 1 acc 2 S6 r1 3 r3 r3 4 S10 S9 7 8 5 r5 r5 6 S5 S4 11
7 S13 S12 3 r3 9 S10 S9 14 10 r5 r5 11 12 r4 13 S10 S9 15 14 s13 S16 15 r2 r2 16 r4 r4 构造1A1R文法加下】 首先合并同心的项目集。 0={S→5。 [→E,$],[E→E+T,$+],[E→T,+] [T→(E),$引+]，[T→a,$|+] 1={IS→s·,s]} 2={S→E·,],[EE+T,$|+]} B.8=E→T,$+)]} 4,9=T→()，$+，[E→E+,)川+，[E→T,),[T→(),)+, [T→a,)+) 5,10={T→a,s+)]} 16,13={E→E+T,s+)],[T→(E),s+)],[T→a,$|+)]} I7.14=T>(E).$|+l)1.[EE+T.)+]} 11,15={E→E+T,s+)]》 I12,16={T(E),$1+)]》 DFA如下图所示： I1 I2 6,13 I11,15 T 13,8 + I5,10 I4,9 I7,14 I12.16 构造LALR分析表如下 action STATAE goto A+()$ 0☐55,101 4,9 123.8
7 S13 S12 8 r3 r3 9 S10 S9 14 8 10 r5 r5 11 r2 r2 12 r4 r4 13 S10 S9 15 14 S13 S16 15 r2 r2 16 r4 r4 构造 LALR 文法如下： 首先合并同心的项目集， I0 = {[S’→•S, $], [S→•E, $], [E→•E+T, $|+], [E→•T, $|+], [T→•(E), $|+], [T→•a, $|+]} I1 = {[S’→S•, $]} I2 = {[S→E•, $], [E→E•+T, $|+]} I3,8 = {[E→T•, $|+|)]} I4,9 = {[T→(•E), $|+|)], [E→•E+T, )|+], [E→•T, )|+], [T→•(E), )|+], [T→•a, )|+]} I5,10 = {[T→a•, $|+|)]} I6,13 = {[E→E+•T, $|+|)], [T→•(E), $|+|)], [T→•a, $|+|)]} I7,14 = {[T→(E•), $|+|)], [E→E•+T, )|+]} I11,15 = {[E→E+T•, $|+|)]} I12,16 = {[T→(E) •, $|+|)]} DFA 如下图所示： I1 I0 I4,9 I2 I3,8 I5,10 I7,14 I6,13 I11,15 I12,16 S ( ( E T a a + T E ) + a ( T 构造 LALR 分析表如下： STATAE action goto A + ( ) $ S E T 0 S5,10 S4,9 1 2 3,8
acc 2 S6,13 rl 3,8 r3 r3 r3 4,9S510 S4.9 7.14 3.8 5,10 r5 5 6,13 S5,10 S4,9 11,15 7,14 S6.13 S12.16 11,15 r9 r9 12,16 r4 r4
1 acc 2 S6,13 r1 3,8 r3 r3 r3 4,9 S5,10 S4,9 7,14 3,8 5,10 r5 r5 r5 6,13 S5,10 S4,9 11,15 7,14 S6,13 S12,16 11,15 r2 r2 r2 12,16 r4 r4 r4