0 二 C# 语法分析器LR 语法分析 _生活百科

系列导航

（一）语法分析介绍
（二）LR(0) 语法分析
（三）LALR 语法分析
（四）二义性文法
（五）错误恢复
（六）构造语法分析器

首先，需要介绍下 LALR 语法分析的基?。篖R(0) 语法分析。
还是以之前的算式文法为例：

$E \to E + T$$E \to T$$T \to T * F$$T \to F$$F \to id$$F \to (E)$

先来看一下 $(id+id)$ 是如何被 LR(0) 语法分析执行的。这里使用 $\$$ 这个特殊符号来标记输入的结束。
栈输入动作$(id_1+id_2)\$$移入$($$id_1+id_2)\$$移入$(id_1$$+id_2)\$$按照 $F \to id$ 归约$(F$$+id_2)\$$按照 $T \to F$ 归约$(T$$+id_2)\$$按照 $E \to T$ 归约$(E$$+id_2)\$$移入$(E+$$id_2)\$$移入$(E+id_2$$)\$$按照 $F \to id$$(E+F$$)\$$按照 $T \to F$$(E+T$$)\$$按照 $E \to E + T$$(E$$)\$$移入$(E)$$\$$按照 $F \to (E)$ 归约$F$$\$$按照 $T \to F$ 归约$T$$\$$按照 $E \to T$ 归约$E$$\$$接受可以看到，LR(0) 语法分析会不断将输入的符号移入到栈中，如果栈里的符号是某个产生式的右部，就会弹出栈内符号并归约为其头部，再将头部符号入栈，直到找到起始非终结符，接受并完成语法分析。
每次都去比较栈里的符号和所有产生式，也可以完成语法分析，但显然这样太过低效，实际使用中会构造出 LR(0) 自动机，利用 LR 语法分析表来提高匹配效率。
一、项和 LR(0) 自动机LR(0) 语法分析器会通过维护一些状态，来表明我们在语法分析过程中所处的位置，从而决定现在需要移入还是归约。
LR(0) 使用“项”（item）来表示现在已经看到了产生式的哪些部分。项是由产生式再加上一个位于它的右部中某处的点组成的。例如产生式 $A \to XYZ$ 产生了四个项：
$$\begin{matrix}A \to \cdot \ XYZ \\A \to X \cdot YZ \\A \to XY \cdot Z \\A \to XYZ\\cdot \ \\\end{matrix}$$
例如，项 $A \to \cdot \ XYZ$ 表示我们希望在接下来的输入中看到一个从 $XYZ$ 推导得到的串。项 $A \to X \cdot YZ$ 表示我们刚刚在输入中看到了一个可以由 $X$ 推导得到的串，并且我们希望接下来看到一个能从 $YZ$ 推导的串。项 $A \to XYZ\\cdot \ $ 表示我们已经看到了产生式体 $XYZ$，已经是时候把 $XYZ$ 归约为 $A$ 了。
LR(0) 语法分析器的状态，就是这样的项的集合（或者称为“项集”），因此可以用于决定现在需要移入还是归约。这些状态的集合（或者称为“项集族”）就可以构造出 LR(0) 自动机，自动机的状态就对应一个项集。
二、构造 LR(0) 自动机为了构造 LR(0) 自动机，首先定义一个