P4

姓名：田昊东 学号：211275022

编译原理作业 p 4

4.6.2

^dfc11a

• 添加增广文法S'->S

S'->S
S->SS+
S->SS*
S->a

• 计算项集闭包
• \(I_0=\{S'\to ·S,S\to ·SS+,S\to ·SS*,S\to ·a\}\)
• \(I_1=\{S'\to S·,S\to S·S+,S\to S·S*,S\to ·SS+,S\to ·SS*,S\to ·a\}\)
• \(I_2=\{S\to a·\}\)
• \(I_3=\{S\to SS·+,S\to SS·*\}\)
• \(I_4=\{S\to SS+·\}\)

• \(I_5=\{S\to SS*·\}\)

• 计算GOTO函数

• \(GOTO(I_0,S)=I_1\)，\(GOTO(I_0,a)=I_2\)
• \(GOTO(I_1,S)=I_3\)，\(GOTO(I_1,a)=I_2\)

• \(GOTO(I_3,+)=I_4\)，\(GOTO(I_3,*)=I_5\)

• 计算FOLLOW

• \(FOLLOW(S)=[+,*,a,\$]\)

• 绘制语法分析表

状态	ACTION				GOTO
	+	*	a	$	S
0			s2		1
1			S2	acc	3
2	r4	r4	r4	r4
3	s4	s5
4	r2	r2	r2	r2
5	r3	r3	r3	r3

• 没有出现冲突，是SLR语法

4.6.3

栈	符号	输入	动作
0		aa*a+$	移入
02	a	a*a+$	根据S->a规约
01	S	a*a+$	移入
012	Sa	*a+$	根据S->a规约
013	SS	*a+$	移入
0135	SS*	a+$	根据S->SS*规约
01	S	a+$	移入
012	Sa	+$	根据S->a规约
013	SS	+$	移入
0134	SS+	$	根据S->SS+规约
01	S	$	接受

4.6.6

• FIRST
• \(FIRST(A)=a\)

• \(FIRST(S)=a\)

• FOLLOW

• \(FOLLOW(S)=[a,\$]\)

• \(FOLLOW(A)=[a,\$]\)

• 由于\(FIRST(SA)\bigcap FIRST(A)=a!=\phi\)因此不符合LL(1)语法

• 下面通过计算SLR语法分析表说明是SLR(1)的

• 增加增广文法

S'->S
S->SA
S->A
A->a

• 计算项集闭包
• \(I_0=\{S'\to ·S,S\to ·SA,S\to ·A,A\to ·a\}\)
• \(I_1=\{S'\to S·,S\to S·A,A\to ·a\}\)
• \(I_2=\{S\to A·\}\)
• \(I_3=\{S\to SA·\}\)
• \(I_4=\{A\to a·\}\)
• 计算GOTO函数
• \(GOTO(I_0,S)=I_1,GOTO(I_0,A)=I_2,GOTO(I_0,a)=I_4\)
• \(GOTO(I_1,A)=I_3,GOTO(I_1,a)=I_4\)
• 绘制语法分析表

状态	ACTION		GOTO
	a	$	S	A
0	s4		1	2
1	s4	acc	3
2	r3
3	r2
4	r4

• 不存在冲突，因此符合SLR(1)

4.7.1

• 先求解规范 LR 项集族 ^266be1

• \[ I_0=\{[S'\to ·S,\$],[S\to ·SS+,\$/a],\\ [S\to·SS*,\$/a],[S\to ·a,\$/a]\} \]
• \[ I_1=GOTO(I_0,S)=\{[S'\to S·,\$],[S\to S·S+,\$/a],\\ [S\to S·S*,\$/a],[S\to ·SS+,+/*/a],[S\to·SS*,+/*/a],[S\to·a,+/*/a]\} \]

• \(I_2=GOTO(I_0,a)=\{[S\to a·,\$/a]\}\)

• \[ I_3=GOTO(I_1,S)=\{[S\to SS·+,\$/a],[S\to SS·*,\$/a]\\ ,[S\to S·S+,+/*/a],[S\to S·S*,+/*/a],\\ [S\to ·SS+,+/*/a],[S\to·SS*,+/*/a],[S\to·a,+/*/a]\} \]

• \(I_4=GOTO(I_3,+)=\{[S\to SS+·,\$/a]\}\)

• \(I_5=GOTO(I_3,*)=\{[S\to SS*·,\$/a]\}\)

• \(I_6=GOTO(I_3,a)=GOTO(I_1,a)=GOTO(I_7,a)=\{S\to a·,+/*/a\}\)

• \[ I_7=GOTO(I_3,S)=GOTO(I_7,S)=\{[S\to SS·+,+/*/a],[S\to SS·*,+/*/a],\\ [S\to S·S+,+/*/a],[S\to S·S*,+/*/a],\\ [S\to ·SS+,+/*/a],[S\to·SS*,+/*/a],[S\to·a,+/*/a]\} \]

• \(I_8=GOTO(I_7,+)=\{S\to SS+·,+/*/a\}\)

• \(I_9=GOTO(I_7,*)=\{S\to SS*·,+/*/a\}\)

• LALR项集族 ^253900

• \[ I_0=\{[S'\to ·S,\$],[S\to ·SS+,\$/a],\\ [S\to·SS*,\$/a],[S\to ·a,\$/a]\} \]
• \[ I_1=GOTO(I_0,S)=\{[S'\to S·,\$],[S\to S·S+,\$/a],\\ [S\to S·S*,\$/a],[S\to ·SS+,+/*/a],[S\to·SS*,+/*/a],[S\to·a,+/*/a]\} \]
• \[ I_{26}=GOTO(I_0,a)=GOTO(I_3,a)=GOTO(I_1,a)=GOTO(I_7,a)\\ =\{[S\to a·,\$/+/*/a]\} \]

• \(I_{59}=GOTO(I_3,*)=GOTO(I_7,*)=\{S\to SS*·,\$/+/*/a\}\)

• \(I_{48}=GOTO(I_3,+)=GOTO(I_7,+)=\{S\to SS+·,\$/+/*/a\}\)

• \[ I_{37}=GOTO(I_1,S)=GOTO(I_3,S)=GOTO(I_7,S)=\\ \{[S\to SS·+,\$/+/*/a],[S\to SS·*,\$/+/*/a]\\ ,[S\to S·S+,+/*/a],[S\to S·S*,+/*/a],\\ [S\to ·SS+,+/*/a],[S\to·SS*,+/*/a],[S\to·a,+/*/a]\} \]