Posted on 2006-07-03 23:57
形式系统 阅读(1090)
评论(4) 编辑 收藏 引用 网摘 所属分类:
编译原理
给出文法,
G(S): A
à
(A) | a
构造
SLR
分析表。
(1)建立拓广文法并编号:
0) S
à
A
1) A
à
(A)
2) A
à
a
(2)构造项目集簇和状态转换图:
(3)构造分析表
若为SLR分析法,还需求First及Follow集。
|
First
|
Follow
|
S
|
( a
|
#
|
A
|
( a
|
) #
|
构造分析表如下:
| ACTION | GOTO |
a | ( | ) | # | S | A |
0 | S3 | S2 | | | | 1 |
1 | | | | Acc | | |
2 | S3 | S2 | | | | 4 |
3 | | | R2 | R2 | | |
4 | | | S5 | | | |
5 | | | R1 | R1 | | |
请注意图中的颜色项和表中的颜色项的对应关系。
Sj表示当前输入符号和状态j入栈。
Rj表示采用第j条产生式进行归约。
(4) 堆栈的变化
假定输入串为:((a))
| 状态栈 | 符号栈 | 输入 | 说明(本列答题时可不写) |
1 | 0 | # | ( (a))# | 查表,状态0,输入(,为S2,即将(入符号栈,2入状态栈。 |
2 | 02 | #( | ( a))# | ( 移进 |
3 | 022 | #(( | a ))# | a移进 |
4 | 0223 | #((a | ))# | 查表,状态3,面临输入),为R3,使用第3条产生式(即Aàa)规约。 |
5 | 0224 | #((A | ) )# | )移进 |
6 | 02245 | #((A) | ) # | 状态5面临)输入,R1,即使用Aà(A)归约。红色部分为先出栈元素,出栈后将产生式左边的符号,即A入栈,同时此时状态栈的栈顶元素是2,查SLR分析表,状态2面临输入 |
7 | 024 | #(A | ) # | )移进 |
8 | 0245 | #(A) | # | 使用Aà(A)归约 |
9 | 01 | #A | # | Acc(接受项目) |