【编译原理笔记】第四章
第四章 语法分析
- 语法分析程序的功能和语法分析方法
- 自顶向下语法分析法
- 自底向上算符优先分析法
- LR分析法
4.1 语法分析程序的功能
1. 自上而下的分析法
从文法的开始符号出发,根据文法规则正向推导出给定句子的一种方法;或者说,从树根开始,往下构造语法树,直到建立每个叶的分析方法。
2. 自下而上的分析法
从给定的输入串开始,根据文法规则逐步进行归约,直至归约到文法开始符号的一种方法;或者说,从语法树的未端开始,步步向上归约,直至根结点的分析方法。
4.2 自上而下语法分析法
非确定的自上而下分析法的基本思想是:
对任何输入串W试图用一切可能的办法,从文法的开始符号出发,自上而下地为它建立一棵语法树。或者说,为输入串寻找一个最左推导。如果试探成功,则W为相应文法的一个句子,否则W就不是文法句子。
4.2.1 非确定的自上而下分析法的思想
也就是说,这种分析过程本质上是一种穷举试探过程,是反复使用不同规则,谋求匹配输入串的过程。
上述自上而下为输入串W建立语法树的过程,实际也是设法为输入串建立一个最左推导序列:S=>aAb=>adb。由于对输入串从左向右进行扫描,使用最左推导,才能保证按从左到右扫描顺序匹配输入串。
根据以上分析,不难看出,非确定的自上而下分析法即是带回溯的自上而下分析法, 实际上是一种穷举的试探方法,其分析效率极低,代价很高,在实用的编译程序中是不常用的。我们通常使用确定的自上而下分析法进行语法分析。
但确定的自上而下分析法对语言的文法有一定的限制条件,那就是要求描述语言的文法是无左递归的和无回溯的。
4.2.2 文法的左递归性和回溯的消除
1.文法左递归的消除
当一个文法是左递归文法时,采用自上而下分析法会使分析过程进入无穷循环之中。 文法左递归是指文法中的某个非终结符A存在推导
用非终结符A去匹配输入串时,使当前句型的最左非终结符仍然为A。也就是说,在没有读进任何输入符号的情况下,又重新要求A去进行新的匹配。 于是,造成无穷循环。
对含直接左递归的规则进行等价变换,消除左递归
(1)引进一个新的非终结符,把含左递归的规则改写成右递归。设关于非终结符A的直接左递归的规则为A→ Aα | β
其中α 、β是任意的符号串, α不等于 ε , β不以A开头。对A的规则可改写成如下右递归形式:
A → βA'
A'→ αA' | ε
改写以后的形式和原来形式是等价的。也就是说,从A推出的符号串的集合是相同的。
(2) 消除间接左递归:
① 将所有的左递归转换为直接左递归
② 按照消除直接左递归的方式消除
2. 回溯的消除
在自上而下分析过程中,由于回溯,需要推翻前面的分析,包括已做的一大堆语义工作,重新去进行试探,这样大大降低了语法分析器的工作效率,因此,需要消除回溯。
我们分析发现引起回溯的原因是: 在文法中,当某个非终结符A有多个候选式时:
A → α1 | α2 | α3 |∙∙∙∙∙∙| αn
遇到用A去匹配当前输入符号a时,无法确定选用唯一的一个候选式,而只能逐一进行试探,从而引起回溯。具体表现在下面两种情况。
第一种情况: 文法中相同左部的规则,其右部左端第一个符号相同而引起回溯。
例 设有文法G[S]:
S→ aAb
A→ de | d
第二种情况: 文法中相同左部的规则,其中某一右部能推出ε串,例如, 文法G:
A→ Bx
B→ x |ε
其非终结符B有两个右部,第二个右部能推导出ε串且两个右部左端第一个符号不相同,但在分析符号串 W=x 时出现回溯。
综上所述,在自上而下分析过程中,为了避免回溯, 对描述语言的文法有一定的要求:
对文法的某个非终结符A,当它有多个侯选式时:
A → α1 | α2 | α3 |∙∙∙∙∙∙| αn
若用A匹配输入串时,能根据当前读到的输入符号a唯一地选择一条规则去匹备输入串。或者说,能唯一地选择一条规则进行推导。
这也就是说,在自上而下分析过程中,为了避免回溯,要求描述语言的文法是LL(1)文法。
LL(1)文法的判断条件
为了建立LL(1)文法的判断条件,需引进三个相关的集合:
- FIRST集
- FOLLOW集
- SELECT集
换句话说FOLLOW(A)是G的所有句型中紧接在A之后出现的终结符或 #。
这里我们用#作为输入串的结束符,例如,# 输入串 #。
LL(1)中的第一个L表明自上而下的分析是从左到右扫描输入串,第二个L表明分析过程中使用最左推导,1表示分析时每一步只需向前看一个符号即可决定所选用的规则,而且这种选择是准确无误的。
LL(1)文法的判定
综合上面的讨论,我们可知对LL(1)文法,若当前非终结符A面临输入符号a时,可根据a属于哪一个SELECT集,唯一地选择一条相应规则去准确地匹配输入符号a。也就是说,当描述语言的文法是LL(1)文法时,可对其进行确定的自上而下的分析。
4.2.3 某些非LL(1)文法到LL(1)文法的改写方法
前面已经指出,构造确定的自上而下分析程序要求对给定语言的文法必须是LL(1)文法,但是,并不是每个语言都有LL(1)文法。
由 LL(1)文法定义可知, 若文法中含有左递归或含有公共左因子,则该文法不是 LL(1) 文法,因此,对某些非LL(1)文法而言, 可通过消除左递归和反复提取公共左因子对文法进行等价变换,可能将其改造为 LL(1)文法。 消除文法左递归的方法见4.2.2。