Posted on 2006-07-05 22:17
形式系统 阅读(2947)
评论(15) 编辑 收藏 引用 网摘 所属分类:
编译原理
文法:
A à (A)A | B
B à a | b | ε
说明:蓝色文字表示说明,讲解;黑色部分(除了为突出的红色文字外)为正式书面表述,即,答题时就可按黑色文字部分格式。
(1) 显然不含左递归
构造 First 及 Follow 集
|
First
|
Follow
|
A
|
( a b ε
|
# )
|
B
|
a b ε
|
# )
|
First((A)A ) ∩Fisrt(B)=Ф
First(a ) ∩Fisrt(b)∩Fisrt(ε)=Ф
B 含有 ε项的候选,由上表可知First(B)∩Follow(B)=Ф
故满足 LL(1) 文法。
(2) 预测分析表
预测分析表的含义:当前状态下(即栈顶为特定非终结符,同时面临特定的输入符号(终结符)时),应该用哪条产生式去推导。将该产生式放入表中以便查阅。其求法就是利用该非终结符的产生式的候选的First集。如,若'('∈First((A)A),而当前栈顶元素为A,输入恰好为(,那么就可以认为此时采用Aà(A)A进行推导是合理的。而LL文法的条件就限定了,一个非终结符,只能属于一个候选的First的集。因而下表的每个单元格,只可能填一条产生式候选。
|
a
|
b
|
(
|
)
|
#
|
A
|
Aà B
|
AàB
|
Aà(A)A
|
AàB
|
AàB
|
B
|
Bàa
|
Bàb
|
|
Bàε
|
Bàε
|
|
|
|
|
|
|
(3) 堆栈的变化
假设输入串为((a)b)
序号
|
堆栈
|
输入
|
说明(答题时,本列可不写)
|
1
|
#A
|
( (a)b)
|
查表,A行, ( 列,采用Aà(A)A推导
|
2
|
#A)A(
|
((a)b)#
|
若与栈顶元素相同,则消解。下面桔黄项同理。请注意,入栈顺序是按文法由右到左的顺序。
|
3
|
#A)A
|
( a)b)#
|
Aà(A)A
|
4
|
#A)A)A(
|
(a)b)#
|
|
5
|
#A)A)A
|
a )b)#
|
AàB
|
6
|
#A)A)B
|
a )b)#
|
Bàa
|
7
|
#A)A)a
|
a )b)#
|
|
8
|
#A)A)
|
) b)#
|
|
9
|
#A)A
|
b )#
|
AàB
|
10
|
#A)B
|
b )#
|
Bàb
|
11
|
#A)b
|
b )#
|
|
12
|
#A)
|
) #
|
|
13
|
#A
|
#
|
#作为输入结束的界符,AàB
|
14
|
#B
|
#
|
Bàε
|
15
|
#
|
#
|
如果输入串正确,则必然会到达这个状态
|
上表中,红色部分只是个例子,说明怎样查分析表,即栈顶元素指示分析表的行,输入元素指示分析表的列,从分析表中查出相应的产生式,利用其推导。
(4) 递归下降程序实现
程序代码:http://yhspace.ys168.com
其下的编译原理子目录,Compile01.rar,Compile02.rar.
调试成功,用VC打开可运行。如未装VC,用文本编辑器分别打开main.cpp,compile02.cpp也可查看代码。