Posted on 2006-06-01 20:33
形式系统 阅读(5077)
评论(0) 编辑 收藏 引用 网摘 所属分类:
编译原理
考虑以下的文法G（E）：
E→(L) | a
L→L , E | E
（1） 构造LR(0)项目集规范簇及识别活前缀的DFA。
首先引入新的开始符和产生式S→E，同时将原来产生式候选拆开。构建其拓广文法并编号：
0） S→E
1） E→(L)
2） E→a
3） L→L , E
4） L→E
以S-->•E开始依次求其闭包元素。
考察集合中项目的点号后面的元素，如S→E
（2） 构造SLR（1）分析表。
分析表的结构说明：分析表的行表示状态，列表示不同的输入符号。分析表的内容为不同的状态面临不同的输入时，应该作的操作。其操作有：
1） 入栈：用符号Sj 表示当前状态j入状态栈，同时当前输入符号（即列名）入符号栈。
2） 归约：归约即是用产生式的左部替换产生式的右部。需要归约的时候通常是栈顶元素恰是是某产生式的右部模式。在该表中记作：Rj ，即用第j条产生式进行归约。
3） 接受：引入拓广文法之后，当项目集中含有S→E·时。则说明已经归约到了语法树的最上层。此时可以接受整个的被分析句子。
4） 出错：即使用上述方法在表中填入之后，表中还有空格的情况。通常由文法的内在结构不可能产生的输入。
表的构造算法：
1） 若当前项目集 Ij 只包含移进项目或规约项目：则考察其引出的弧。又分为两种情况考虑：
a) 若弧所对应的跳转字符是终结符，则在下表中的第j行，该终结符所对应的列的单元格内填上S j
b) 若跳转弧对应的字符为非终结符，则在GOTO子表中对应的位置填上j。
2）若当前项目集只含有归约项目（不允许同时含有归约和移进。也不能同时含有两格以上的归约项目，否则不是SLR文法）。则从文法中选定产生式。假定其一般化的形式及标号为 (j) A→γ 则求Follow(A)，对于任意终结符 a∈FOLLOW(A)。在下表中填入R j 。
如状态2（I2）包含的项目文法为E→γ。该产生式编号为②故其动作为R2。 另一方面，查FOLLOW(E)集合包含{‘(‘ , ‘,’ , ‘# ‘)。则在ACTION子表的 “(“ , “,” , “# ”所对应的列中填上R2
3） 若当前项目集只含有接受项目，就在该行“＃”所对应的列中填入acc。
1）求FOLLOW集：
易知：FIRST(S)=FIRST(E)=FIRST(L)={ “(“ ,“a”)
由产生式 0）得 “# ”∈FOLLOW(S)，
由产生式 1） “ )“∈FOLLOW(L) (“L”后面紧相邻的是”)”)
由产生式 3） “,” ∈FOLLOW(L) (“L”后面紧相邻的是”,”)
由产生式 3）或4）FOLLOW（L）包含于FOLLOW(E)
由1）FOLLOW(S)包含于FOLLOW(E)
故：FOLLOW(S)={‘#’}
FOLLOW(L)={‘)‘ , ‘,’ )
FOLLOW(E)={‘)‘ , ‘,’ , ‘# ‘)
2）根据前面DFA图，考察每个结点。构造下表。
|
状态
|
ACTION
|
GOTO
|
|
（
|
a
|
)
|
,
|
#
|
S
|
E
|
L
|
|
0
|
S2
|
S3
|
|
|
|
|
1
|
|
|
1
|
|
|
|
|
acc
|
|
|
|
|
2
|
S2
|
S3
|
|
|
|
|
5
|
4
|
|
3
|
|
|
R2
|
R2
|
R2
|
|
|
|
|
4
|
|
|
S6
|
S7
|
|
|
|
|
|
5
|
|
|
R4
|
R4
|
|
|
|
|
|
6
|
|
|
R1
|
R1
|
R1
|
|
|
|
|
7
|
S2
|
S3
|
|
|
|
|
8
|
|
|
8
|
|
|
R3
|
R3
|
|
|
|
|
（1） 显示分析栈和输入串，((a) , a , (a , a))的SLR(1)分析程序的动作。
状态栈
|
符号栈
|
输入
|
0
|
#
|
(
|
02
|
# (
|
(
|
022
|
# ((
|
A
|
0223
|
# ((a
|
)
|
0225
|
# ((E
|
)
|
0224
|
# ((L
|
)
|
02246
|
# ((L)
|
,
|
025
|
# (E
|
,
|
024
|
# (L
|
,
|
0247
|
# (L,
|
a
|
02473
|
# (L,a
|
,
|
02478
|
# (L,E
|
,
|
024
|
# (L
|
,
|
0247
|
# (L,
|
(
|
02472
|
# (L,(
|
a
|
024723
|
# (L,(a
|
,
|
024725
|
# (L,(E
|
,
|
024724
|
# (L,(L
|
,
|
0247247
|
# (L,(L,
|
a
|
02472473
|
# (L,(L,a
|
)
|
02472478
|
# (L,(L,E
|
)
|
024724
|
# (L,(L
|
)
|
0247246
|
# (L,(L)
|
)
|
02478
|
# (L,E
|
)
|
024
|
# (L
|
)
|
0246
|
# (L)
|
#
|
01
|
# E
|
#
|
到达状态1同时后续是# 时，查表为acc，分析成功。