LR分析器在线视频

大家好

在上一节我们对

算符优先分析法的讨论当中

我们发现

由于算符优先分析法

去掉了单非终结符之间的归约

尽管在分析的过程当中

当决定是否为句柄的时候

会采取一些检查措施

但是仍难以完全避免

从错误的句子当中得到正确的归约

此外

通常一个适用语言它的文法

也很难满足

算符优先文法它的条件

因而呢致使算符优先文法

它仅适用于表达式的语法分析

今天我们来介绍

文法限制少

适用范围比较广

分析速度快

报错准确的LR分析法

LR(k)当中的L

表示的是从左到右扫描所给定的输入串

R表示的是以相反的方向构造

该输入串的最右推导

也就是规范推导

k表示为了做出分析的决定

需要向前看的输入符号的个数

k通常取0或1

LR分析法适用于

一大类的上下文无关文法

大多数用上下文无关文法描述的

高级语言它的语法成分

都可以用LR分析器来识别

LR分析采用的是移进归约分析

是严格的规范归约

它根据当前的分析栈当中的

符号串和向右顺序查

看输入串K(K≥0)个符号

就可以唯一的确定

分析的动作是移进还是归约

刚才我们也说了LR分析是规范的归约

它的关键问题就是寻找句柄

那么LR方法

它的基本思想是这样子的

在规范归约的过程当中

一方面要记住

已经移进的和归约出的整个字符串

也就是说要记住历史

另一方面呢就是能够根据

所用的产生式

推测未来可能会碰到的输入符号

也就是说能够对未来进行展望

这样当一串貌似句柄的字符串

出现在分析栈栈顶的时候

我们希望能够根据历史和展望

以及现实的输入符号这三部分的内容

来决定出现在栈顶的这一串符号

是否就是我们要找的句柄

那么如何记载历史和展望呢

根据LR分析的思想如果将历史

也就是已经移进或者规约的符号串

和展望也就是

推测未来可能

遇见到的这些符号抽象为状态

那么初态就可以抽象为

栈的初始符号是#

终态可以抽象为句柄的识别状态

将实际遇见的文法符号

也就是现实可以抽象为弧

那么LR分析器实际上呢

就是一个带有先进后出栈的

确定的有穷状态自动机了

这里的分析栈呢

是将状态栈和符号栈合在一起

来记录分析的历史和展望的

我们来看一下

状态栈当中的Si

它记录的是分析过程当中的

每一步的历史和展望的内容

那么文法符号Xi

存放的就是分析的过程当中

移进VT和归约VN的符号

初始的状态栈当中是S0

符号栈当中是#

我们现在看到的就是LR分析器

它的逻辑结构

那么LR分析法也

也是一种表驱动的分析法

有一个分析栈

一个总控程序和一个分析表

对于所有的LR分析器来说

它的总控程序都是相同的

但是文法不同

分析表就不同了

LR分析表呢其实是LR分析器它的核心

比较特殊的地方大家可以看到

就是分析栈是状态栈和

文法符号栈和二为一

那么分析表呢有动作表和状态转移表

LR分析表呢是LR分析法它的关键

这里有四种构造方法

当然构造分析表的方法不同

导致的是它的分析能力和实现的效率不同

但是共同的特点就是他们拥有

相同的逻辑结构和相同的驱动程序

我们来看一下LR分析表它的结构

它是由ACTION表和GOTO表

那么两个部分组成的

表当中大家所看到的S1 S2…Sn

是我们分析器的各个状态

那么ACTION表下面的列

是文法的全部终结符号

以及右侧符或者说也叫做输入的结束符#

GOTO表下的列是文法的非终结符号

ACTION表当中Si行aj列

表示的是当分析状态栈的栈顶是Si的时候

那么输入的符号为aj

这个时候应该执行哪一种动作

GOTO表当中Si行Xj列

表示的是当前的状态是Si下面

如果符号栈的栈顶为

非终结符Xj的时候

那么应该移入状态栈的状态号是哪一个

结合我们刚才所看到的LR分析表

我们来分析一下LR分析器它的工作过程

当状态栈的栈顶是Sm的时候

现行输入的符号为ai

那么总控程序就根据Sm和ai去查

LR(0)它的分析表

假设

我们看到的ACTION子表当中的Sm行

ai这一列是Sj

此时S j表示的是

状态j和输入符a分别进栈

这就是移进操作

下面我们来看规约操作

规约前栈的状态是Sm

当前的输入的符号是ai

那么总控程序就根据Sm和ai

去查LR(0)分析表

如果说这个时候表当中的

Sm行ai这一列是r j

此时r j

表示的是按照第j条产生式来进行规约

假设第j个产生式是这样子的

那么大家可以看到它的右部的长度是r

那么规约的第一步分别从

状态栈和符号栈的栈顶

自顶向下弹出r个符号和状态

同时将A压入到符号栈

规约的第二步

当前状态栈的栈顶是Sm-r

那么再以Sm-r和A去查goto表

那么假设goto表当中的Sm-r这一行

A这一列是Sk

那么就把Sk这个状态

压入到状态栈当中去

现在的分析栈的栈顶就变成了SK和A

当某个状态Sm下面

输入的符号是#我们去查表

action子表当中

Sm这一行#这一列是acc也就是accept

表示得是当前的输入符号串分析成功

可以终止分析器的工作

此时我们发现

符号栈一般只剩下

文法的开始符号和#

当某个状态Sm下输入的符号是ai

我们去查分析表action[Sm ai]=error

error表示的是出错

也可以用空白来代替

那么表示的是当前的输入符号串

当中有语法的错误

可以调用相应的出错处理程序

大家看到这是

表达式文法的LR分析表

构造的方法我们后面再去讨论

现在我们要使用LR分析表

来对这个句子i*i+i进行语法分析

初始状态S0和符号#

当前读取的是i

根据S0和i查LR(0)分析表

Action子表是S5

那么状态S5和符号i入栈

读头后移读取*

根据S5和*查LR(0)的

action子表是r6

S5和i出栈

i按照6号产生式

规约为F入栈

根据S0和F去查LR(0)的

goto子表是3

那么就将3号状态入状态栈

根据S3和*

去查LR(0)的action子表是r4

那么S3和F就出栈

F规约为T再入栈

根据S0和T

去查LR(0)的goto子表是2

那么就S2入栈

根据S2和*

去查LR(0)分析表是S7

那么就将状态7和*入栈

输入带字上面的读头后移指向i

根据S7和i

去查LR(0)分析表是S5

状态5和i入栈

输入带读头后移指向+

在根据S5和+

去查LR(0)分析表是r6

那么S5和i就出栈

i规约为F之后呢入符号栈

再根据S7和F

去查LR(0)的goto子表是10

那么就将S10入状态栈

再根据S10和+

去查LR(0)的action子表是r3

那么此时呢s10 s7和s2

三个状态以及T*F三个符号

同时出栈

T*F按照3号产生式

规约为T再次入栈

根据S0和T

去查LR(0)的goto子表是2

那么就将S2入栈

根据S2和+

去查LR(0)的action子表是r2

S2呢和T就出栈

T根据2号产生式

规约为E再次入栈

根据S0和E

去查LR(0)的goto子表是1

那么就将S1入栈

根据S1和+

去查LR(0)的action子表是S6

将状态6和+入栈

读头后移读取到i

根据S6和i

去查LR(0)的action子表是S5

那么就将状态5和i入栈

读头继续后移指向#

根据S5和#

去查LR(0)的action子表是r6

那么状态5和符号i同时出栈

i根据6号产生式规约为F再次入栈

根据S6和F查LR(0)的goto子表是3

那么就将S3入栈

根据S3和#

去查LR(0)的action子表是r4

那么S3和F呢就出栈

F根据4号产生式规约为T再次入栈

根据S6和T

去查LR(0)的goto子表是9

那么就将S9入栈

根据S9和#

去查LR(0)的action子表是r1

那么此时S9 S6 S1三个状态

以及符号E + T三个符号同时出栈

E+T根据1号产生式

规约为E再次入栈

根据S0和E

去查LR(0)的goto子表是1

那么就将S1入栈

再根据S1和

当前读头下面读取的#号

去查LR(0)的action子表是acc

那么表示句子的分析就结束

这个句子就是可以被接受的

也就是说这个句子是正确的

这节课呢我们从LR分析法

它的本质说起

剖析了LR分析器它的结构

并且结合非常重要的LR分析表

为大家展示了

LR分析器它是怎样工作的

这个工作过程当中会采用哪些动作

这节课呢就到这里

谢谢大家