3-LR(0)语法分析

一、LR语法分析器模型

image.png

二、LR语法分析算法

输入：一个输入串w和一个LR语法分析表

输出：如果w在L(G)中，输出w的自底向上的语法分析过程中的归约步骤；否则给出错误提示

方法：最初，语法分析器栈中的内容为初试状态S0，输入缓冲区的内容为w $。然后，执行语法分析程序。

分析实例

image.png

LR(0)的自动机
image.png

分析表
image.png

分析过程
image.png

三、LR分析算法的特点

image.png

定义

LR文法：我们能为之构造出所有条目都唯一的LR分析表。

直观上说，只要存在这样一个从左到右扫描的移入-归约语法分析器，它总是能够在某文法的最右句型的句柄出现在栈顶时识别出这个句柄，那么这个文法就是LR的。

image.png

特点集合

  • 栈中的文法符号总是形成一个可行前缀

  • 分析表的转移函数本质上是识别可行前缀的DFA

  • 栈顶的状态符号包含了确定句柄所需要的一切信息

  • 是已知的最一般的无回溯的移进——归约方法

  • 能分析的文法类是预测分析法能分析的文法类的真超集

  • 能及时发现语法错误

  • 手工构造分析表的工作量太大

image.png

四、LR分析方法和LL分析方法的比较

LR文法 vs LL文法

  • LR(K)文法:向前看k个输入符号能够知道一个产生式的右部所能推导出的所有符号串，进而识别出这个产生式右部的出现。

  • LL(K)文法：看到了产生式右部推出的前k个符号后能够识别出用于归约的产生式。

  • LR文法比LL文法描述的语言更多。

image.png

image.png

image.png

image.png

五、id* id + id的分析

image.png

分析过程详解
状态栈 符号栈 输入 动作
$0 $ id * id + id $ s5
$0 5 $ id * id + id $ r6 F ->id
$ 0 3 $ F * id + id $ r4 T ->F
$ 0 2 $ T * id + id $ S7
$ 0 2 7 $ T * id + id $ S5
$ 0 2 7 5 $ T * id + id $ R6 F->id
$ 0 2 7 10 $ T * F + id $ R3 T->T * F
$ 0 2 $ T + id $ R2 E->T
$ 0 1 $ E + id $ S6
$ 0 1 6 $ E + id $ S5
$ 0 1 6 5 $ E + id $ R6 F->id
$ 0 1 6 3 $ E + F $ R4 T->F
$ 0 1 6 9 $ E + T $ R1 E->E+T
$ 0 1 $ E $ acc
符号栈归约的时候，减少几个，状态栈就弹出几个元素