LR分析器

编译原理的老师上课实在是太赶了...感觉自己落下了好多课程,也跟不上,不过今天发现国防科技大学的编译原理慕课说的很清楚,所以先跟着慕课来学习吧。

规范规约与句柄

规范规约的关键载与寻找句柄

LR分析器应该有能力在任何时候判断分析栈的顶部是否出现路句柄,如果出现了句柄,那么把分析栈顶部形成句柄的部分弹出,然后把归约后的符号压入。完成移进归约。

lr

根据这三类信息判断是否出现句柄以及下一步如何工作。

LR分析方法

LR分析方法把历史和展望抽象成了状态。所以由栈顶状态和现行输入符号可以确定每一步工作。

分析栈状态和符号一一对应。压入符号也要压入相应的状态,弹出也是。

分析程序使用分析栈,调用程序度如下一个单词,根据栈顶状态和面临的单词查询分析表,分析表会告知 Sm和现行单词的情况下应该怎么做(移进(移进之后需要压入的状态分析表也会告知)/归约(告诉使用哪一个产生式,压入归约后的符号也要压入对应的状态)) 分析表是LR分析器的核心,分析程序的操作则是固定的。

两个子表 ACTION和GOTO

ACTION[s,a] s为状态 a为终结符

GOTO[s,X] s为状态,X为非终结符 归约完之后压栈的时候,新压入的非终结符对应的状态是什么。

lr2

分析表中的符号含义

s5 s指的是shift(移入)

image-20201025193543062

如栈顶状态0遇见输入符号i,i移入符号栈后还要把状态5移进状态栈。

r4 r指的是归约,4代表用四号产生式归约

若产生式是A->β,β长度为r,则去除符号栈和状态栈的r个项(此时状态栈栈顶为Sm-r),并把新得到的A压入符号栈,并根据GOTO[Sm-r,A]得到对应的状态并压入。

image-20201025193932992

acc accept指的是栈顶符号是1 面临#(句子末尾)时,分析成功停止分析器工作

所有空着的格子都代表了错误,如果出现就报错。

LR分析过程

image-20201025194359648

状态栈和符号栈的右边,输入串左边代表栈顶。

分析过程

单独看归约部分。 注意归约的时候输入串ai没有变化

归约操作

举例如下:

分析示例

分析器总有一些性质:

  • 任何时候分析栈和扫描串拼接起来是一个规范句型(可规范推导得出)
  • 一旦栈顶出现句柄,马上会被归约

归约得到非终结符入栈后记得查GOTO表获得新的状态,还有就是出栈的时候,状态栈也要弹出相同数目的状态,移入符号到栈顶的时候可以在语法树里面添加节点,归约的时候语法树也会增长

第三步用了GOTO表,得到栈顶状态3 第四步用到了ACTION再次归约,然后GOTO表0 T 得到状态2

image-20201025200754799

image-20201025201244546

image-20201025201436382

这样就得到了语法树。

LR文法

如果一个文法能够构造出一个分析表,他的每个入口是唯一确定的(一个格子里面动作不超过一个),那么称之为LR文法。

如果一个文法能用一个每步最多向前检查k个输入符号的LR分析器进行分析,称之为LR(k)文法。刚才的分析,我们只看了栈顶状态和输入符号,所以k为1,即LR(1)文法。

LR文法不是二义的,LR包含于无二义文法(真包含)

S-> iCtS | iCtSeS

i: if

C: 条件表达式

t: then

S: 语句

我们的程序语言是非LR结构 ,构造出的分析表,一个格子里可能有多个动作(同时要移入与归约) 二义结构

但是我们依旧可以使用LR分析,可以把冲突项中拿掉归约,只留下移入,消除冲突。

image-20201025202844139

文章目录