编译原理,为文法G构造语法分析的预测分析程序。

文法G[S]如下:

S->aAaB|bAbB

A->S|db

B->bB|a

分析句子adbaba

要求:

提前消除文法的左递归及提取左公共因子。

求出FIRST集、FOLLOW集、SELECT集、判空、输出预测分析表、

输出对句子的分析过程。

一、主要内容

1、检查文法是否为LL(1)文法

2、代码介绍:

(1)初始定义参数,给定文法的开始符号、非终结符、终结符、文法产生式。定义三个字典用来表示FIRST集、FOLLOW集、SELECT集。

(移植到其他文法上只需修改这一部分初始定义的参数,其余的程序都是通用的。)

《编译原理,为文法G构造语法分析的预测分析程序。》

(2)初始化函数init(),打印开始符号、文法产生式。并将每个非终结符加入FIRST集、FOLLOW集作为“键”,同时将其“值”置空;将每个产生式加入SELECT集作为“键”,同时将其“值”置空。

再向开始符号G的FOLLOW集中加入“#”

《编译原理,为文法G构造语法分析的预测分析程序。》

(3)求FIRST集

①getFirst()函数,根据每条产生式,求出每个非终结符的FIRST集。

这里有两种情况:

I.产生式右部第一个元素为终结符(也即小写字母)的情况。将产生式按“->”分为左部、右部,然后判断右部第一个元素是否为小写字母(if not part_right[0].isupper())。如果是,说明该元素为终结符,则直接将其加入左部的非终结符的FIRST集中。

II.产生式右部第一个元素为非终结符,则将其自身的FIRST集取出,加入产生式左部的非终结符的FIRST集中。

《编译原理,为文法G构造语法分析的预测分析程序。》

②first()函数,去除FIRST集中的重复元素,并打印输出最终的FIRST集。

《编译原理,为文法G构造语法分析的预测分析程序。》

(4)求FOLLOW集

①getFollow()函数,根据每条产生式,求出每个非终结符的FOLLOW集。

I.产生式右部只有一个元素并且该元素为终结符(也即小写字母)的情况。(if len(part_right) == 1 and part_right.islower())。对于这种情况,直接略过该产生式。

《编译原理,为文法G构造语法分析的预测分析程序。》

II.解决了I情况后, 先将产生式右部逆序存入列表中

《编译原理,为文法G构造语法分析的预测分析程序。》

然后开始进行判断:

a.产生式右部最后一个元素是非终结符(也即大写字母,即列表的第一个元素为大写字母:if temp[0].isupper()),则直接将产生式左部非终结符的FOLLOW加入该非终结符的FOLLOW集中。

《编译原理,为文法G构造语法分析的预测分析程序。》

然后,开始对产生式右部元素逐个处理。当再次找到一个非终结符时(即if not i.isupper()不成立,此时i代表当前非终结符),

b.若其后一位元素为非终结符(if temp1.isupper())时,则将其FIRST集去除ε后加入i的FOLLOW集。

《编译原理,为文法G构造语法分析的预测分析程序。》

c.同时判断该非终结符能否推出ε(if (‘ε’ in FIRST.get(temp1))),若能,则将标志位flag加一。然后在判断flag长度是否等于产生式右部减一,若相等,说明i后面全是非终结符,并且非终结符全都能推出空,则将产生式左部的非终结符的FOLLOW集加入i的FOLLOW集中。

《编译原理,为文法G构造语法分析的预测分析程序。》

d.若其后一位元素为终结符时,则直接将终结符加入i的FOLLOW集

《编译原理,为文法G构造语法分析的预测分析程序。》

②follow()函数,去除FOLLOW集中的重复元素,并打印输出最终的FOLLOW集。

《编译原理,为文法G构造语法分析的预测分析程序。》

(5)求SELECT集

①getSelect()函数,根据每条产生式,求出每个产生式的SELECT集。

I.当产生式右部第一个元素为终结符时,则直接将该非终结符加入产生式的SELECT集

《编译原理,为文法G构造语法分析的预测分析程序。》

II.当产生式右部第一个元素为非终结符时,判断其是否为空,

a.若为空,则将其FIRST集去除ε后加入产生式的SELECT集,同时也将产生式左部非终结符的FOLLOW集加入产生式的SELECT集

b.若不为空,则直接将其FIRST集加入产生式的SELECT集。

《编译原理,为文法G构造语法分析的预测分析程序。》

②select()函数,去除SELECT集中的重复元素,并打印输出最终的SELECT集。

《编译原理,为文法G构造语法分析的预测分析程序。》

(6)输出预测分析表predTable()函数

《编译原理,为文法G构造语法分析的预测分析程序。》

(7)主控程序,对于输入的句子,根据每条产生式进行处理。

①当分析栈的栈顶符号等于某个产生式的左部非终结符时,同时当输入串的当前符号存在于产生式的SELECT集中,则使用该条产生式进行推导,将分析栈栈顶符号弹出,然后将产生式右部符号入栈

《编译原理,为文法G构造语法分析的预测分析程序。》

②当分析栈栈顶符号等于输入串当前符号时,判断相等的元素是否为“#”。

I.若为“#”,说明分析已经完成,分析成功,输出“ACCEPT”

II.若不为“#”,说明当前只是匹配到符号,则输出匹配信息

《编译原理,为文法G构造语法分析的预测分析程序。》

③最后,根据标志位,判断是否分析成功。

《编译原理,为文法G构造语法分析的预测分析程序。》

二、实验截图

《编译原理,为文法G构造语法分析的预测分析程序。》

【实验小结】

1、在求解FOLLOW集时,要根据每个产生式右部逐个符号分析。即对每个产生式进行循环判断,从产生式右部入手,对右部每个符号分析处理,而不是对每个非终结符处理,这样就避免了多次嵌套循环。同时,使用python中的字典数据结构,十分方便的实现FOLLOW集的存储和赋值(同样FIRST集与SELECT集)

也就是这个getFollow()函数,思考了好几个小时才搞出来。然后类似的FIRST集和SELECT集求解实现就简单得多了。

《编译原理,为文法G构造语法分析的预测分析程序。》

2、注意要对FIRST集、FOLLOW集、SELECT集中元素去重,去掉重复的元素。

3、输出预测分析表时,考虑到每个产生式的顺序随机,采用列表中的insert方法,将对应终结符的匹配的产生式插入相应的位置。也即按照VT列表中的位置顺序。

《编译原理,为文法G构造语法分析的预测分析程序。》

不然的话,有可能出现顺序错乱的问题。

《编译原理,为文法G构造语法分析的预测分析程序。》

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注