LR(0)分析方法

基本概念

项目 item

项目是对文法中产生式的扩展，通过在产生式右部添加\(\cdot\)的方法来表示语法分析器在分析过程中的某个状态。

例子：

对于产生式\(A\rightarrow \alpha X\)，它产生以下几个项：

\[ \begin{align} A&\rightarrow \cdot \alpha X &(1)\\ A&\rightarrow \alpha \cdot X &(2)\\ A&\rightarrow \alpha X \cdot &(3)\\ \end{align} \]

其中，

  • 式\((1)\)的点号右侧是一个终结符，意味着在当前状态下，分析器期待从输入流中读入符号\(\alpha\)，因此它被定义为一个移入项。

  • 式\((2)\)中点号右侧是一个非终结符，此时分析器期待后面的输入归约得到非终结符\(X\)，因此它被定义为一个待约项。

  • 式\((3)\)的点号位于整个产生式的结尾，此时意味着分析器将进行归约操作，将\(\alpha X\)归约为\(A\)，因此它被定义为一个归约项。

增广文法 augmented grammar

为了得到唯一的终止产生式，定义一个文法\(G\)的增广文法\(G^{\prime}\)：

对于文法\(G\)的开始符号\(S\)，将产生式\(S^{\prime}\rightarrow S\)添加到\(G\)中，就得到了文法\(G^{\prime}\)。

这样，当分析器进入状态\(S^{\prime}\rightarrow S\cdot\)时，如果输入流已经读完，就表示进入了接受状态。

\(\text{CLOSURE}\)函数

\(\text{CLOSURE}\)函数将一个项目集合映射到另一个项目集合，它的输入是项目集合\(I\)，输出是该项目集合的闭包\(\text{CLOSURE}(I)\)。它的意义在于将一些在状态上等价的项聚集起来形成一个状态，而不是对于文法的每一个项作为一个状态，避免语法分析器的状态数过多。定义\(\text{CLOSURE}(I)\)：

  1. 初始，\(\text{CLOSURE}(I) = \phi\)
  2. \(\text{CLOSURE}(I) = \text{CLOSURE}(I)\cup I\)
  3. 如果\(A\rightarrow \alpha \cdot B \beta \in \text{CLOSURE}(I)\)，并且\(\exists B\rightarrow \cdot \gamma \notin \text{CLOSURE}(I)\)，那么\(\text{CLOSURE}(I) = \text{CLOSURE}(I)\cup B\rightarrow \cdot \gamma\)

不断重复\((3)\)直到没有新的项能添加到\(\text{CLOSURE}(I)\)中。上面各式的含义是：

  • \((2)\)的含义是所有\(I\)中的项都在\(I\)的闭包中

  • \((3)\)的含义是如果\(\text{CLOSURE}(I)\)中某个项的点号的右侧是一个非终结符，那么以该非终结符为左部且点号在右部最左侧的项也在\(\text{CLOSURE}(I)\)中。进一步也就是说如果此时分析器期待对非终结符\(B\)的归约，那么它也同样期待着由\(B\)产生的那些符号，因为只有那些符号才能归约成\(B\)。

\(\text{GOTO}\)函数

\(\text{GOTO}\)函数也将一个项目集合映射到另一个项目集合，它的输入是项目集合\(I\)和一个文法符号\(X\)，输出是该项目集合中所有项遇到文法符号\(X\)后所有后继项的闭包。

后继项：对于项\(A\rightarrow X\cdot YZ\)而言，它的后继项就是将点号移动到项右部的下一个文法符号，即\(A\rightarrow XY\cdot Z\)。

它的意义是求出分析器状态机中的所有状态转移。定义\(\text{GOTO}\)函数：

\(\text{GOTO}(I, X) = \text{CLOSURE}(\{A\rightarrow \alpha X\cdot \beta \ |\ \forall A\rightarrow \alpha \cdot X \beta \in I \})\)

规范\(\text{LR}(0)\)项集族 canonical LR(0) collection

所谓项集族，指的是项目集合的集合，也就是说项集族中每一个元素都是一个项目的集合。利用\(\text{CLOSURE}\)函数和\(\text{GOTO}\)函数，可以构造出一个文法的规范\(\text{LR}(0)\)项集族。定义规范\(\text{LR}(0)\)项集族：

\(C = \{I_{0}\}\cup \{I\ |\ \exists J\in C, X\in V_{N}\cup V_{T}, I = \text{GOTO}(J, X)\}\)

上面表达式的含义是：

  • \(C\)中包含了项\(S^{\prime}\rightarrow \cdot S\)的闭包。

  • 对\(C\)中的每一个项目集合\(I\)和文法中每一个符号\(X\)，如果\(\text{GOTO}(I, X)\)不在\(C\)中，则将其添加到\(C\)中。

\(\text{LR}(0)\)分析器

\(\text{LR}(0)\)分析表的结构

\(\text{LR}(0)\)分析表是一个二维表格，它的行数等于文法\(G\)的规范\(\text{LR}(0)\)项集族中元素个数，列数等于\(G\)中文法符号的个数。分析表中的每一个单元表示在某个状态下遇到某个文法符号时，下一步需要进行的操作。整个分析表被划分为\(\text{ACTION}\)和\(\text{GOTO}\)两个区域，落入对应区域的单元分别表示遇到终结符和非终结符时所进行的操作。

对于\(\text{ACTION}\)：

  • 如果为\(s_{i}\)，则表示移入（shift）操作，分析器将输入指针指向的符号移入符号栈，然后将状态\(S_{i}\)移入状态栈。

  • 如果为\(r_{i}\)，则表示归约（reduce）操作，分析器将使用第\(i\)个产生式对符号栈顶的句柄进行归约操作。

对于\(\text{GOTO}\)，单元格中所有的元素都是数字，\(j = \text{GOTO}[S_{i}, X]\)表示状态\(S_{i}\)遇到栈顶为非终结符\(X\)时将状态\(S_{j}\)入栈。

\(\text{LR}(0)\)分析器的结构

\(\text{LR}(0)\)分析器包含4个主要部分：

  • 输入缓冲

  • 符号和状态栈

  • \(\text{LR}(0)\)分析表

  • 驱动程序

它的运行中的格局是：

  1. 初始格局为：

\[\begin{align} &S_{0} \\ &\$ &a_{1}a_{2}\cdots a_{n}\$\\ \end{align}\]

其中\(S_{0}\)表示初始状态，对应\(S^{\prime}\rightarrow \cdot S\)的项目集闭包。

  1. 假设运行时的一个格局是：

\[\begin{align} &S_{0}S_{1}S_{2}\cdots S_{m} \\ &\$ X_{1}X_{2}\cdots X_{m} &a_{i}a_{i + 1}\cdots a_{n}\$\\ \end{align}\]

  • 若\(\text{ACTION}[S_{m}, a_{i}] = s_{x}\)，则进行移入操作，格局变为： \[\begin{align} &S_{0}S_{1}S_{2}\cdots S_{m}S_{x} \\ &\$ X_{1}X_{2}\cdots X_{m}a_{i} &a_{i + 1}\cdots a_{n}\$\\ \end{align}\]

  • 若\(\text{ACTION}[S_{m}, a_{i}] = r_{x}\)，则进行归约操作，使用第\(x\)个产生式\(A\rightarrow X_{m - (k - 1)}\cdots X_{m}\)，格局变为： \[\begin{align} &S_{0}S_{1}S_{2}\cdots S_{m - k} \\ &\$ X_{1}X_{2}\cdots X_{m - k}A &a_{i}a_{i + 1}\cdots a_{n}\$\\ \end{align}\]

而后查找\(\text{GOTO}\)表，若\(\text{GOTO}[S_{m - k}, A] = y\)，则进行状态转移，格局变为：

\[\begin{align} &S_{0}S_{1}S_{2}\cdots S_{m - k}S_{y} \\ &\$ X_{1}X_{2}\cdots X_{m - k}A &a_{i}a_{i + 1}\cdots a_{n}\$\\ \end{align}\]

  • 若\(\text{ACTION}[S_{m}, a_{i}] = \text{acc}\)，则分析成功。
  • 若\(\text{ACTION}[S_{m}, a_{i}] = \text{err}\)，则分析失败。

构造\(\text{LR}(0)\)分析表

构造\(\text{LR}(0)\)分析表的方法是：

  1. 首先求文法\(G\)的\(\text{LR}(0)\)项集族\(C\)

  2. 对于\(C\)中的每一个项目集\(I\)：

    1. 如果\(\text{GOTO}(I, \alpha) = I^{\prime}\)，则\(\text{ACTION}[I, \alpha] = S_{I^{\prime}}\)

    2. 如果\(\text{GOTO}(I, A) = I^{\prime}\)，则\(\text{GOTO}[I, A] = I^{\prime}\)

    3. 如果\(I\)中有归约项，则\(\forall \alpha, \text{ACTION}[I, \alpha] = r_{x}\)，其中\(x\)为归约项对应产生式的编号