Bonky
Neither believe nor reject anything, because any other person has rejected or believed it. Heaven has given you a mind for judging truth and error, Use it.
By Thomas Jefferson

编译原理 – 语法分析之自底向上的语法分析

自底向上的语法分析

从分析树的底部 (叶节点) 向顶部 (根节点) 方向构造分析树。(可以理解为从终结符推导出开始符号E)

一般使用的方法为:移入-归约分析 (Shift-Reduce Parsing)

移入-归约分析

一般流程如下:

  1. 初始的时候栈为空,剩余输入为原串
  2. 然后将剩余输入出栈一个字符,加入到栈中。
  3. 当栈中出现与文法的右部相同的产生式,然后归约为产生式左部,一直到无法再进行归约为止,否则则继续执行步骤 2
  4. 直到归约为只有开始符号,这说明这满足语法。

下面是一个例子:

存在的问题:

在最左归约中,句柄就是最左直接短语。

对于上面这种问题,对于句子的语法树有直接短语一定属于产生式的右部,而产生式的右部不一定是是最左直接短语,所以上面那种归约是错误的。

LR 分析法

LR文法是最大的,可以构造出相应移入- 归约语法分析器的文法类。L代表对输入进行从左到右的扫描,R代表反向构造出一个最右推导序列。

LR(k) 代表需要向前查看 k 个输入符号的LR分析,如果没有 “(k)”,默认为 k=1 。

基本原理

自底向上分析的关键是如何正确地识别句柄,句柄的识别用状态来表示。

分析表的结构

计算方法如下:(以 bab 为例)

一开始状态栈只有0,然后取出第一个字符为b,状态 0 碰到 b 执行 s4,即将状态 4 压入栈,然后将 b 压入符号栈。(读取字符)

然后因为状态 4 碰到 b 回执行 r3,即利用第三个产生式进行归约,此时 b 出栈,然后 B 在进行入符号栈,然后状态 4 会出栈。(归约)

现在,状态栈为[0],符号栈为[B],状态 0 遇上 B 回跳转到2,即状态 2 入栈。(归约后,根据当前状态跳转),然后是状态2碰上 a 执行 s3,状态3 碰上 b 执行 s4,然后再归约 r3 。。。直到归约到开始符号。

当然,这有个问题,如何构建 LR 分析表呢?对于不同的文法,我们有不同的方法:LR(0)分析,SLR分析,LR(1)分析,LALR分析

LR(0) 文法

右部某位置标有圆点的产生式称为相应文法的一个LR(0) 项目

后继项目:A→α· Xβ的后继项目是A→αX·β

上图是文法所有的项目,其中有一些项目是等价的。比如对于 (0),(1)就是与其等价的,因为下一个是 S 和 下一个是 v 是等价的(根据产生式2)。同样地,(3),(7),(11)是等价的。

可以把等价的项目组成一个项目集,称为项目集闭包 (Closure of Item Sets),每个项目集闭包对应着自动机的一个状态。

增广文法

如果G 是一个以S为开始符号的文法,则G的增广文法 G’ 就 是在G中加上新开始符号S’ 和产生式S’ → S而得到的文法

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边,从而使得分析器只有一个接受状态

自动机

基本思路:先把起始的项目集求出来,然后根据点向后移动一位得到下一步的一个项目,其中边是点前面的那个符号(就是刚刚经过的),然后根据所求的项目,得到他的项目集闭包。根据转换关系,我们可以得到 LR(0) 分析表(终结符写在 action 行,而非终结符写在 goto 表)。

算法实现

CLOSURE( ):计算给定项目集I的闭包

GOTO ( ):返回项目集I对应于文法符号X的后继项目集闭包

分析过程算法如下:

移进/归约冲突

上面是转换图,我们可以看到 I2 的 E→T· 是一个归约项目,而 T→T·*F 是一个移进项目,得到的分析表回有问题(不知道是移进还是归约)

归约/归约冲突

对于上图,存在着归约/归约冲突,如 I2 你不知道是归约成 B 或者是 T。

所以我们可以得出结论:不是所有CFG都能用LR(0)方法进行分析,也就是说,CFG不总是LR(0)文法

SLR文法

SLR文法就是为了解决上面这种情况,即消除移进/归约冲突和归约/归约冲突。因为 LR(0) 文法是没有上下文的,SLR(1)(或称作 SLR)考虑了上下文的关系,即利用 FOLLOW 集进行分析。

SLR分析法的基本思想

分析表的构造方法

和 LR(0) 文法类似,唯一不同的是对于归约项目的处理。在 LR(0) 文法中,对所有元素进行归约操作,而 SLR 文法中,仅仅对 FOLLOW 集里面的元素进行归约操作。

如果给定文法的SLR分析表中不存在有冲突的动作, 那么该文法称为SLR文法

SLR 分析中的冲突

对于 I2,第一个式子遇到等号要求递进,第二个式子要求归约(因为等号在 FOLLOW 集中)。

LR(1)分析

SLR 只是简单地考察下一个输入符号 b 是否属于与归约项目 A→α 相关联的FOLLOW(A),但 b∈FOLLOW(A) 只是归约α的一个必要条件,而非充分条件。

对于产生式 A→α 的归约,在不同的使用位置, A 会要求不同的后继符号。如下图,对于左边这个 R 他的后继为 = ,而右边这个 R 他的后继为 #

所以我们可以知道,在特定位置,A的后继符集合是FOLLOW(A)的子集。上面形如 R→L·,= 的项叫做一个 LR(1) 项,其中 = 为后面必须紧跟的终结符,称为该项的展望符。对于非归约项,展望符是没有作用的。只有下一项等于展望符的时候才能归约。

当 β 为空的时候时,此时 b=a 叫继承的后继符, 否则叫自生的后继符。

例子:

首先我们得到 S′→·S,#,由于 S 后面为空,所以后面的我们就直接继承为:S→·L=R, # S→·R, # 。然后继续,根据 S→·L=R, # 中的 L 我们有:L→·*R, = L→·id, =,因为 L 的后面不为空,所以呢,应该是为 =,然后以此类推。

构造表的时候,只有满足为展望符的时候才能归约。

一个概念:如果除展望符外,两个 LR(1)项目集是相同的, 则称这两个LR(1)项目集是同心的

LR(1) 分析表构造算法

同样地,唯一的不同在于归约项目的不同处理,LR(1) 只对在展望集里面的进行归约。

LR(1) 的算法的缺点就是,他的状态实在是太多了,很多时候很难用于实践。

LALR分析法

实际上就是对没有动作冲突的项目进行合并,即两个同心的项目集可以合并(只要第一分量相同即可)。

然后根据合并后得到的项集族构造语法分析表。如果分析表中没有语法分析动作冲突,给定的文法就称为LALR (1) 文法,就可以根据该分析表进行语法分析

但可能会产生产生归约-归约冲突,下面是一个例子:

合并之后,遇上 d 既可以归约为 A 也可以归约为 B。

同时 LALR 算法还会推迟错误发现的时间,因为可能会作多余的归约动作, 但绝不会作错误的移进操作。

特点

  • 形式上与LR(1)相同,大小上与LR(0)/SLR相当

  • 分析能力介于SLR和LR(1)二者之间:SLR<LALR(1)<LR(1)

  • 合并后的展望符集合仍为FOLLOW集的子集

LR分析中的错误处理

  • 恐慌模式错误恢复:丢弃0个或多个输入符号,直到发现一个可能合法的符号为止,然后继续进行正常的语法分析

  • 短语层次错误恢复:检查LR分析表中的每一个报错条目,并根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误然后构造出适当的恢复过程

Share

You may also like...

发表评论

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