Parse Generator

parsegen.tex

\input luaotfload.sty
\input luatypezh
\input zr/verb

\font\tenmib=cmmib10 \font\sevenmib=cmmib7 \font\fivemib=cmmib5

\baselineskip=14pt \everydisplay{\baselineskip=12pt\relax}
\verbatimindent=2em

% % %

\centerline{制作语法分析器生成器}

\beginsection 1. 概述

语法分析器 (parser) 从线性的输入中恢复出其具有层次的结构。
本文的目的是介绍怎样制作一个程序自动根据语法描述生成相应的语法分析器。

\beginsection 2. 上下文无关语法

计算机语言通常可以用上下文无关语法 (context-free grammar, CFG) 来描述。
上下文无关语法由一组产生式 (production) 构成。

产生式形如\footnote*{常见的约定是， $ABC\ldots$ 表示终结符， $abc\ldots$
表示非终结符， $XYZ$ 表示任意符号， $\alpha\beta\gamma\ldots$ 表示字符串。}
$$A \to \alpha$$
表示非终结符 $A$ 可以产生字符串 $\alpha$。
字符串是一系列的非终结符或终结符， 或空字符串 $\varepsilon$。

每个语法有一个起始符号， 符合该语法的字符串必须能够由起始符号%
通过一系列的推导产生。

考虑如下语法：
$$\eqalign{
S&\to \varepsilon\cr
S&\to S(S)\cr
}$$
它描述由配对的小括号构成的字符串。
字符串 $$()(()())$$ 可以这样导出：
$$\let\u=\underline
S \Rightarrow
\u{S(S)} \Rightarrow
\u{\u{S(S)}(\u{S(S)})} \Rightarrow
\u{\u{()}(\u{\u{S(S)}()})} \Rightarrow
\u{\u{()}(\u{\u{()}()})}
$$

\def\FIRST{\mathop{\it FIRST}}
\beginsection 2.1. FIRST 集合

对于非终结符 $A$， $\FIRST(A)$ 是 $A$ 可以导出的字符串的第一个非终结符的集合。
如果 $A$ 可以导出 $\varepsilon$， 则也说 $\varepsilon \in \FIRST(A)$，
这是一种记法的便利。

对于上文的语法， $\FIRST(S)=\{\varepsilon, {(}\}$。

对于一般的字符串， 可以做类似的定义。
约定 $\FIRST(a)=\{a\}$ 以及 $\FIRST(\varepsilon)=\{\varepsilon\}$， 则
$$\FIRST(X\gamma)=\cases{
\FIRST(X)& if $\varepsilon \notin \FIRST(X)$,\cr
(\FIRST(X) \backslash \{\varepsilon\}) \cup
  \FIRST(\gamma)& if $\varepsilon \in \FIRST(X)$.\cr
}$$

计算非终结符的 $\FIRST$ 集合的方法是{\bf 迭代至不动点}：
\item {1.} 初始化所有非终结符的 $\FIRST$ 为空集。
\item {2.} 遍历所有产生式 $A\to\gamma$， 更新
$\FIRST(A)\gets \FIRST(A) \cup \FIRST(\gamma)$。
\item {3.} 重复第~2~步， 直到所有符号的 $\FIRST$ 集合都不再变化为止。

\beginsection 程序 2.1： 计算 FIRST 集合

根据上述算法， 编写计算 $\FIRST$ 集合的程序。
它的输入是一组产生式， 输出是每个非终结符的 $\FIRST$ 集合。

在这一步， 可以将输入直接编码在程序中， 暂时不考虑怎样解析输入的问题。
用一个整数表示符号。

例如， 用 1 表示 (， 用 2 表示 )， 用 3 表示 $S$，
那么上面例子中的语法可以用代码描述为

\verbatim
(3, [])
(3, [1, 3, 2])
\endverbatim

为了方便观察程序的输出， 可以另外存储一个从整数到符号名的映射， 例如

\verbatim
{1: "(", 2: ")", 3: "S"}
\endverbatim

程序的输出应该类似于：

\verbatim
S: <epsilon> (
\endverbatim

需要注意的地方：

\item{1.} 怎样区分终结和非终结符号？
\item{2.} 怎样表示 $\varepsilon$？
\item{3.} 怎样表示集合以便方便地进行遍历和计算并集？

程序编写完毕后可以用更加复杂的语法测试， 以便验证正确性。

\beginsection 3. 状态机生成

本节的目的是生成 LALR(1) 状态机。 LALR(1) 状态机和 LR(0) 状态机有相同的状态，
只不过多了前看集合 (lookahead set) 的概念。
因此， 这个工作可以分成两步进行： 生成 LR(0) 状态机和计算前看集合。

\beginsection 3.1. LR(0)状态机

对于某个产生式
$$A \to Y_1Y_2\ldots Y_n,$$
在右侧插入一个 $\cdot$ 来跟踪语法分析的状态， 这样得到的称作 LR(0) 项 (item)，
如：
$$\eqalign{
A \to \cdot Y_1Y_2\ldots Y_n\cr
A \to Y_1{\cdot}Y_2\ldots Y_n\cr
}$$
等等。 在程序中， 这个点可以用一个整数 （在产生式中的位置） 来记录。

LR(0) 状态机的每个状态是若干项的集合。 初始状态以附加项
$$S' \to \cdot S{\dashv}$$
作为核 (kernel)。 其中 $\dashv$ 是一个虚拟的终结符， 表示输入结束。
这样便于语法分析器在输入结束时判定是否接受这个输入。

根据核可以生成闭包 (closure)， 方法是{\bf 迭代至不动点}：
\item{1.} 遍历状态内的所有项， 如果 $\cdot$ 右侧是非终结符 $A$，
则把所有以 $A$ 为左侧的产生式加入到这个状态中， 且 $\cdot$ 位于右侧的左端。
\item{2.} 重复第~1~步， 直到状态中的项不再变化为止。

按照上述算法， 初始状态应为 （分号前是核）。
$$\{
S'\to \cdot S{\dashv};\;
S \to \cdot,\,
S \to \cdot S(S)
\}$$

理论上并不需要记录核以外的项， 但是记录它们可以避免重复上述迭代计算。
一种聪明的办法是只记录核以外的项的左侧符号， 因为同一符号的所有产生式%
都会出现在闭包中。

\def\States{{\it States}}
\def\Goto{\mathop{\it Goto}}
有了初始状态， 就可以逐步生成状态机中的所有状态。
用 $\States$ 表示所有状态的集合， 用 $Goto(Q, X) = Q'$ 表示在 $Q$~状态和
$X$~输入下跳转到 $Q'$~状态。
生成所有状态的方法， 本质上依然是{\bf 迭代至不动点}， 但是这里有一些特殊性，
那就是每个状态只需要处理一次：

\item{1.} 设置一个队列 $q\gets{Q_0}$， 其中 $Q_0$ 为初始状态。
初始化 $\States\gets\emptyset$。
\item{2.} 从 $q$ 中取出一个状态~$Q$。
\item{3.} 遍历所有符号~$X$ （除 $\dashv$）， 找出所有点的右侧是 $X$ 的项，
把这些项的点放到 $X$~的右侧， 构成一个新的核。
\item{4.} 由这个核确定闭包， 构成新的状态~$Q'$。 记录 $\Goto(Q, X)=Q'$。
\item{5.} 如果 $Q' \notin States$， 则更新 $States \gets States \cup \{Q'\}$。
\item{6.} 重复 2--6， 直到队列~$q$ 为空。

按照这个算法， 可以得到下述状态机：
$$\vbox{\tabskip=1em
\halign{\strut$Q_{#}$\hfil&$\{#\}$\hfil&$#$\hfil\cr
\noalign{\hrule\kern1pt}
\omit\strut &\omit \bf 项&\omit\bf Goto\cr
\noalign{\hrule\kern1pt}
0&S' \to \cdot S{\dashv};\;S \to \cdot,\> S \to \cdot S(S)&S\colon 1\cr
1&S' \to S{\cdot}{\dashv},\> S \to S{\cdot}S(S);&(\colon 2\cr
2&S \to S({\cdot}S);\; S \to \cdot,\> S \to \cdot S(S)&S\colon 3\cr
3&S \to S(S{\cdot}),\> S \to S{\cdot}(S);&(\colon 2,\, )\colon 4\cr
4&S \to S(S){\cdot};&\cr
\noalign{\hrule\kern1pt}
}}$$

\beginsection 程序 3.1： 状态机生成

编写程序生成指定语法的 LR(0) 状态机。
它的输入是一组产生式， 输出是状态机的各个状态以及 $\Goto$。

输出状态的时候， 可以输出其中所有项， 或者只输出核以及右侧为 $\varepsilon$
的项 （其他的项不是特别重要）。

上述算法有很多可以推敲的地方：
\item{1.} 第~3~步不一定要 “遍历所有符号”， 可以先把状态中的项按照 $\cdot$
右侧的符号分类， 然后分别处理。
\item{2.} 第~4~步可以不用先计算闭包， 就可以判断新的状态~$Q'$ 是否已知。
如果是， 则不用再次计算。
\item{3.} 实际上并不需要专门的数据结构存储队列~$q$。
一般 $\States$ 用线性表实现， 可以记录当前正在处理的状态~$Q$ 的位置，
在这个位置之前的状态都是处理过的状态 （已经出队的状态），
之后则是未处理的状态 （队列~$q$ 中的状态）。

\beginsection 3.2. 前看集合

\def\LA{\mathop{\it LA}}
LALR(1)前看集合的一种生成方法是{\bf 迭代至不动点}：

\item{1.} 初始化所有项的前看集合为空集；
\item{2.} 遍历所有状态~$Q$ 的所有形如 $A\to\alpha{\cdot}X\beta$ 的项~$I$，
$\LA(I)$ 是该项的前看集合；
\itemitem{a.} 如果 $X$ 是非终结符， 找到 $Q$ 中所有形如 $X\to\gamma$
的项~$I'$， 更新
$$\LA(I') \gets \cases{
\LA(I') \cup \bigl(\FIRST(\beta) \backslash \{\varepsilon\}\bigr) \cup \LA(I)&
if $\varepsilon \in \FIRST(\beta)$,\cr
LA(I') \cup \FIRST(\beta)& if $\varepsilon \notin \FIRST(\beta)$.
}$$
\itemitem{b.} 如果 $X\ne{\dashv}$，
在状态~$Q'=\Goto(Q,X)$ 中应有项~$I'=A\to\alpha X{\cdot}\beta$，
更新 $LA(I') \gets LA(I') \cup LA(I)$；
\item{3.} 重复第~2~步， 直到所有项的前看集合不再变化。

按照这个算法， 可以得到下述 LALR(1) 状态机：
$$\vbox{\tabskip=1em
\halign{\strut$Q_{#}$\hfil&$\{#\}$\hfil&$#$\hfil\cr
\noalign{\hrule\kern1pt}
\omit\strut &\omit \bf 项&\omit\bf Goto\cr
\noalign{\hrule\kern1pt}
0&S' \to \cdot S{\dashv};\;
  S \to \cdot\,\{\dashv,(\},\>
  S \to \cdot S(S)\,\{\dashv,(\}&S\colon 1\cr
1&S' \to S{\cdot}{\dashv},\>
  S \to S{\cdot}S(S)\,\{\dashv,(\};&(\colon 2\cr
2&S \to S({\cdot}S)\,\{\dashv,(,)\};\;
  S \to \cdot\,\{(,)\},\>
  S \to \cdot S(S)\,\{(,)\}&S\colon 3\cr
3&S \to S(S{\cdot})\,\{\dashv,(,)\},\>
  S \to S{\cdot}(S)\,\{(,)\};&(\colon 2,\, )\colon 4\cr
4&S \to S(S){\cdot}\,\{\dashv,(,)\};&\cr
\noalign{\hrule\kern1pt}
}}$$

\beginsection 程序 3.2： 前看集合生成

修改 LR(0) 状态机生成程序， 使其在生成状态机后计算各项的前看集合。
这样得到的便是 LALR(1) 状态机。

如果核以外的项只记录了左侧符号， 那么只需要对这个符号计算一次前看集合，
因为该状态内所有以它为左侧的项的前看集合都是一样的。

\beginsection 4. 分析器表

\def\Action{\mathop{\it Action}}

LR 分析器工作的时候维护一个状态机和一个栈。
在每个状态~$Q$ 中， 根据输入字符串的下一个符号~$x$ 执行动作 $\Action(Q, x)$。
有 4~种可能的动作：
\item{1.} Shift： 将 $x$ 入栈并从输入流中移除。
\item{2.} Reduce($A\to Y_1Y_2\ldots Y_n$)：
弹出栈顶的 $n$~个符号， 并将 $A$ 入栈。
\item{3.} Accept： 接受输入字符串。
\item{4.} Error： 拒绝输入字符串（报告语法错误）。

确定 $\Action$ 的办法是观察状态中的项。
\item{1.} 如果含有形如 $A\to \alpha\cdot$ 的项~$I$， 且 $x\in \LA(I)$，
则 $\Action(Q, x)={}$Reduce($A\to\gamma$)；
\item{2.} 如果含有形如 $A\to \alpha{\cdot}x\beta$ 的项，
则 $\Action(Q, x)={}$Shift；
\item{3.} 如果含有形如 $A\to \alpha{\cdot}{\dashv}$ 的项，
则 $\Action(Q, \dashv)={}$Accept；
\item{4.} 否则， $Action(Q, x)={}$Error。

如果同时满足 1 和 2， 则表示语法分析器无法区分这个状态下应当执行 Reduce
或 Shift 动作， 称为 Shift/Reduce 冲突。
如果有多个项满足 1， 则语法分析器无法区分应当选择哪一个产生式进行 Reduce，
称为 Reduce/Reduce 冲突。
一般来说， 含有这些冲突的语法超出了分析器的分析能力。

根据状态机可以得到所有的 $\Action$ 和 $\Goto$， 称为分析器表 (parser table)。
在文献中常把他们列在同一张表格中， 并且采用如下的记号约定：
\item{1.} $s_i$ 表示 $\Action={}$Shift, $\Goto=i$；
\item{2.} $g_i$ 表示 $\Goto=i$ （针对非终结符， 因为非终结符没有 $\Action$）；
\item{3.} $r_i$ 表示 $\Action={}$ Reduce(编号为 $i$ 的产生式)，
注意区分此处 $i$ 的含义和以上两者的区别；
\item{4.} {\it acc} 表示 $\Action={}$Accept；
\item{5.} 空白或者 {\it err} 表示 $\Action={}$Error。

对于上一节的状态机，相应的语法分析器表为
$$\vbox{\tabskip=1em
\halign{\strut$Q_{#}$\hfil&&$#$\hfil\cr
\noalign{\hrule\kern1pt}
\omit\strut&\dashv& (&)& S\cr
\noalign{\hrule\kern1pt}
0&r_1&r_1&&g_1\cr
1&\it acc&s_2\cr 
2&&r_1&r_1&g_3\cr
3&&s_2&s_4\cr
4&r_2&r_2&r_2\cr
\noalign{\hrule\kern1pt}
}}$$
各产生式的编号如下：
\item{(1)} $S\to \varepsilon$
\item{(2)} $S\to S(S)$

\beginsection 程序 4： 分析器表生成

编写程序生成分析器表。 在程序中， 这个表可以存储成二维数组。
每一个单元格用一个整数表示。 Shift 和 Reduce 的区别可以通过正负号区分，
Accept 和 Error 则可以用一些特殊值 （比如， $-10000$） 来表示。
这个表可以通过状态机生成， 但它包含的信息比状态机更少。
调试时， 通常打印每个状态的项， 以及各个输入符号下的动作。
现在可以编写这样的程序， 当提供以上语法时， 给出类似以下的输出：
$$\hbox{\hsize = .3\hsize
\valign{#\vfil\cr
\verbatim
State 0:
    $acc: . S $end
(1) S: .
$    reduce 1
(    reduce 1
)    reduce 1
S    goto 1

State 1:
    $acc: S. $end
    S: S. ( S )
$    accept
(    shift 2
\endverbatim\cr\noalign{\vrule}
\verbatim
State 2:
(1) S: .
    S: S (. S )
$    reduce 1
(    reduce 1
)    reduce 1
S    goto 3

State 3:
    S: S ( S. )
    S: S. ( S )
(    shift 2
)    shift 4
\endverbatim\cr\noalign{\vrule}
\verbatim
State 4:
(2) S: S ( S ).
$    reduce 2
(    reduce 2
)    reduce 2
\endverbatim\cr
}}$$
当生成的分析器表含有冲突时，报告这个冲突。

如果想实现更加丰富的功能，可以参考接下来的几节。

\beginsection 4.1. 冲突解决

有时给定的语法是有歧义 (ambiguous) 的， 这必将造成分析器表中的冲突。
但有时可以让生成器解决这些冲突。

\beginsection 4.1.1. 优先级和结合性

一种常见的情况是描述算术表达式， 语法
$$\eqalign{
E&\to n\cr
E&\to E+E\cr
E&\to E\times E\cr
}$$
生成的状态机其中一个状态是
$$\eqalign{
E&\to E+E{\cdot}\cr
E&\to E{\cdot}+E\cr
E&\to E{\cdot}\times E\cr
}$$
这里构成了Shift/Reduce 冲突。
当输入是 $E+E+E$ 时， 分析器无法确定应当按照
$\underline{E+E}+E$ 或是 $E+\underline{E+E}$ 的方式分析。

赋予终结符优先级 (precedence) 和结合性 (associativity)，
可以解决这类问题。 对于某个状态~$Q$ 和输入符号~$x$，
如果同时存在两个项 $I_S$ 和 $I_R$， 分别满足执行 Shift 和 Reduce 的条件，
则按照下述规则解决冲突：

\item{1.} 找到 $I_R$ 中的代表符号 $y$， 一般是产生式的最后一个终结符，
但也可以是用户指定的其他符号。 如果没有， 则无法解决冲突。
\item{2.} 如果 $x$ 和 $y$ 的优先级和结合性相同：
\itemitem{a.} 如果是左结合， 则 $\Action={}$Reduce；
\itemitem{b.} 如果是右结合， 则 $\Action={}$Shift；
\itemitem{c.} 如果是不可结合 (non-associative)， 则 $\Action={}$Error。
\item{3.} 如果 $x$ 的优先级大于 $y$ 的优先级，则 $\Action={}$Shift；
\item{4.} 如果 $x$ 的优先级小于 $y$ 的优先级，则 $\Action={}$Reduce；
\item{5.} 其他情况下无法解决冲突。

按照算术符号的一般定义， 上述冲突将采取 Reduce 动作，
因为 $+$ 和 $+$ 的优先级相同且是左结合。 当输入是 $E+E\times E$ 时，
因为 $\times$ 的优先级大于 $+$， 所以采取 Shift 动作。

\beginsection 4.1.2. 默认行为

当上节描述的方法无法解决冲突时， Shift/Reduce 通常采取 Shift。
一个著名的情况是悬挂 else 问题：
$$\eqalign{
S&\to {\bf if}\; E\; {\bf then}\; S{\cdot}\cr
S&\to {\bf if}\; E\; {\bf then}\; S{\cdot}\;{\bf else}\; S\cr
}$$
歧义在于，下面的语句有两种分析方法：
$$\displaylines{
\noalign{\vskip-\jot}
{\bf if}\; E\; {\bf then}\; \overbrace{{\bf if}\; E\; {\bf then}\; S \;
{\bf else}\; S}^{S}\cr
{\bf if}\; E\; {\bf then}\; \underbrace{{\bf if}\; E\; {\bf then}\; S}_{S}\;
{\bf else}\; S\cr
}$$
几乎所有程序设计语言都采取第一种解释， 也就是在这个冲突的情况下选择了 Shift。

语法分析器生成器在解决 Shift/Reduce 冲突时， 首先会考虑优先级和结合性。
如果能够解决， 那么就不必报告冲突。 否则， 默认采取 Shift， 并且报告冲突。
对于 Reduce/Reduce 冲突， 没有特别合理的解决办法。
语法分析器生成器一般会采用比较随意的解决办法， 例如选择较早出现的那个产生式。

\beginsection 4.2. 表格压缩

考虑一个简化的算术表达式语法：
$$\eqalignno{
E&\to n&(1)\cr
E&\to E+E&(2)\cr
E&\to E\times E&(3)\cr
E&\to (E)&(4)\cr
}$$
生成的状态机有 10~个状态， 而语法共有 7~个符号， 因此生成的分析器表有 70~项，
如下所示。
$$\def\ac{\it acc}\vbox{\tabskip=1em
\halign{\strut$Q_{#}$\hfil&&$#$\hfil\cr
\noalign{\hrule\kern1pt}
\omit\strut&\dashv&n&+&\times& (&)& E\cr
\noalign{\hrule\kern1pt}
0&   &s_2&   &   &s_3&   &g_1\cr
1&\ac&   &s_4&s_5&   &   &   \cr
2&r_1&   &r_1&r_1&   &r_1&   \cr
3&   &s_2&   &   &s_3&   &g_6\cr
4&   &s_2&   &   &s_3&   &g_7\cr
5&   &s_2&   &   &s_3&   &g_8\cr
6&   &   &s_4&s_5&   &s_9&   \cr
7&r_2&   &r_2&s_5&   &r_2&   \cr
8&r_3&   &r_3&r_3&   &r_3&   \cr
9&r_4&   &r_4&r_4&   &r_4&   \cr
\noalign{\hrule\kern1pt}
}}$$

实用的语法分析器生成器通常会压缩分析器表以节省存储空间。
对于终结符部分， 首先记下每一行出现频次最多的 Reduce 动作，
作为这个状态的默认动作， 存放在一维数组 Def 中。
$$\vbox{\tabskip=1em
\halign{\strut\bf#\hfil&&\hbox to1em{$#$\hss}\cr
\noalign{\hrule\kern1pt}
   &  0&  1&  2&  3&  4&  5&  6&  7&  8&  9\cr
\noalign{\hrule\kern1pt}
Def&   &   &r_1&   &   &   &   &r_2&r_3&r_4\cr
\noalign{\hrule\kern1pt}
}}$$
之后就可以在表中删除默认动作，剩下的部分为
$$\def\ac{\it acc}\vbox{\tabskip=1em
\halign{\strut$Q_{#}$\hfil&&$#$\hfil\cr
\noalign{\hrule\kern1pt}
\omit\strut&\dashv&n&+&\times& (&)\cr
\noalign{\hrule\kern1pt}
0&   &s_2&   &   &s_3&   \cr
1&\ac&   &s_4&s_5&   &   \cr
2&   &   &   &   &   &   \cr
3&   &s_2&   &   &s_3&   \cr
4&   &s_2&   &   &s_3&   \cr
5&   &s_2&   &   &s_3&   \cr
6&   &   &s_4&s_5&   &s_9\cr
7&   &   &   &s_5&   &   \cr
8&   &   &   &   &   &   \cr
9&   &   &   &   &   &   \cr
\noalign{\hrule\kern1pt}
}}$$

剩下的值可以存放在一个一维数组中。 通过给各行指定适当的偏移量，
非空的值不会互相重叠。 可以使用 first-fit 算法做表格压缩：
\item{1.} 设二维数组有 $n$~行 $m$~列。
分配足够长 （$n\times m$ 足够了） 的一维数组 $D$ 和 $C$，
以及长度为 $n$ 的一维数组 $P$。
\item{2.} 把二维数组的各行按照非空白项从少到多排序，
然后按顺序处理每一行 $L$， 设这行在排序前行号是 $i$。
\itemitem{a.} 如果这一行是空的， 无需处理；
\itemitem{b.} 如果这一行的内容和之前处理过的第 $i'$ 行的内容完全相同，
则令 $P[i]\gets P[i']$；
\itemitem{c.} 否则， 设第一个非空项的列号是 $j$。
令
$$P[i]\gets\min\left\{d\geq-j\mathbin{\bigg|}
{\forall k\in [0,n), P[k] \ne d \land{}\hfill\atop
\forall k\in [j,m), L[i]\hbox{ 为空} \lor D[d+k]\hbox{ 为空}}\right\}$$
（这里， 第一个条件防止两行使用一个偏移量，
第二个条件确保 $L$ 中的值且不和其他任何值重叠。）
对于所有非空的 $L[k]$， 令 $D[P[i]+k]\gets L[k]$, $C[P[i]+k]\gets k$。
\item{3.} 在 $D$ 中找到最后一个非空值的索引 $i$。
$D$ 和 $C$ 实际需要的长度是 $i+1$。

这样， 二维数组被压缩成 3~个一维数组， 一种可能的结果是如下所示。%
\footnote*{这里 $P$ 和 $D$/$C$ 一样长是巧合。}
$$\def\ac{\it acc}\vbox{\tabskip=1em
\halign{\strut$#$\hfil&&\hbox to1em{$#$\hss}\cr
\noalign{\hrule\kern1pt}
 &  0&  1&  2&  3&  4&  5&  6&  7&  8&  9\cr
\noalign{\hrule\kern1pt}
D&s_5&s_2&s_4&s_5&s_3&s_9&\ac&   &s_4&s_5\cr
C&  3&  1&  2&  3&  4&  5&  0&   &  2&  3\cr
P&  0&  6&   &  0&  0&  0&  0& -3&   &   \cr
\noalign{\hrule\kern1pt}
}}$$

$P$~数组中的空白项一般可以用超出合理范围的值代替， 例如 $D$~数组的实际长度。

从压缩后的表格中查询 $\Action(Q,x)$ 的办法是：
如果 $P[Q]$ 非空， $P[Q]+x$ 没有超出 $D$~数组的索引边界，
并且 $C[P[Q]+x]=x$， 则 $\Action(Q,x)=D[P[Q]+x]$；
否则， $\Action(Q,x)={\rm Def}[Q]$。

有几个需要注意的问题：

\item{1.} 采用默认动作的目的是进一步压缩分析器表。
它实际上修改了分析器表， 即把空白部分改写成了默认动作。
对于语法分析器而言， 这不会影响语法正确的输入的分析。
但是， 当遇到语法错误时， 语法分析器可能会先做若干次 Reduce，
之后才会报告错误。
\item{2.} 采用结合性解决冲突时， 不可结合的运算符会造成 $\Action={}$Error。
这里的 Error 不应被视作空白， 否则将被改写成默认的 Reduce，
失去了规定结合性的意义。

分析器表的非终结符部分 （只有 Goto 动作） 可以用相同的算法压缩。
实践中通常以列 （而不是行） 为单位， 把这部分的值放入一维数组中。
终结符和非终结符部分可以共用一个 $D$ 和 $C$， 但是需要一个额外的 $P'$~数组。

\beginsection 5. 驱动程序

驱动程序是语法分析器中和分析器表无关的部分， 配合不同的分析器表，
则构成不同语法的分析器。
语法分析器一次读取一个记号 (token)。 获取记号有两种常见的实现方法：

\item{1.} 拉模式 (pull mode)： 另有一个函数 （通常名为 \verb|getToken| 或
\verb|lex|）， 每调用一次返回一个记号。
语法分析器在一个大的循环中多次调用该函数。
\item{2.} 推模式 (push mode)： 对于每个输入记号， 调用一次语法分析器函数。
这个函数更新状态机和栈 （记录在函数外）。

读取记号之后， 按照 “分析器表” 一节的描述更新状态机和栈。
语法分析器的栈和状态机是互相关联的：

\item{1.} 在状态~$Q$， 符号~$X$ 入栈时， 实际入栈的是二元组 $(Q,X)$，
然后跳到 $\Goto(Q,X)$；
\item{2.} 二元组 $(Q,X)$ 出栈时， 回到状态 $Q$。

例如， 对于上一节的表达式语法， 输入为 $n+n\times n$ 时，
语法分析的过程如下表所示。%
\footnote\dag{每个符号左侧的下标是它入栈时的状态， 末尾的下标是当前状态。}
$$\tabskip=\centering
\halign to\displaywidth{\strut$#$\hfil&$#$\hfil&#\hfil\cr
\noalign{\hrule\kern1pt}
\omit\strut\bf 栈/状态\hfil&\omit\bf 输入流\hfil&\bf 动作\cr
\noalign{\hrule\kern1pt}
_0&           n{+}n{\times}n{\dashv}&Shift\cr
_0n_2&         {+}n{\times}n{\dashv}&Reduce($E\to n$)\cr
_0E_1&         {+}n{\times}n{\dashv}&Shift\cr
_0E_1{+_4}&       n{\times}n{\dashv}&Shift\cr
_0E_1{+_4}n_2&     {\times}n{\dashv}&Reduce($E\to n$)\cr
_0E_1{+_4}E_7&     {\times}n{\dashv}&Shift\cr
_0E_1{+_4}E_7{\times_5}&   n{\dashv}&Shift\cr
_0E_1{+_4}E_7{\times_5}n_2&  \dashv &Reduce($E\to n$)\cr
_0E_1{+_4}E_7{\times_5}E_1&  \dashv &Reduce($E\to E\times E$)\cr
_0E_1{+_4}E_7&               \dashv &Reduce($E\to E+E$)\cr
_0E_1&                       \dashv &Accept\cr
\noalign{\hrule\kern1pt}
}$$

\beginsection 5.1. 语义值和语义动作

实用的语法分析器除了接受合法输入和报告语法错误外，
还要对输入中的语义信息进行处理。 例如， 对于表达式 $1+2\times 3$， 有两个问题：

\item{1.} 这些数字在语法层面没有区别， 但它们的具体数值对于计算是不可缺少的。
\item{2.} 我们希望得到比 “输入合法” 更有用的输出， 例如求值结果或者抽象语法树。

对于问题~1， 一般输入的记号序列的每个记号都有语法符号和语义值两部分，
这两者有时也被称为 major 和 minor value。
数字~1 的语法符号是 $n$，而语义值是 1。
语法分析器在将符号入栈时， 应当同时入栈它的语义值。

对于强类型语言， 语义值必须能够表示多种类型。
例如某些语言可以将符号定义为和类型 (sum type)：

\verbatim
datatype Symbol = NUMBER of int | ID of string | SEMI
\endverbatim

\noindent 或者利用某些语言的联合 (union) 类型表示语义值：

\verbatim
union svalue {
    int number;
    string id;
};
\endverbatim

对于问题~2， 每个产生式可以附着一个语义动作 (semantic action)。
当 Reduce 动作执行的时候， 同时执行相对应的语义动作。

语义动作应当可以读写产生式的各个符号的语义值。
例如， 对于 $E\to E+E$， 语义动作可以是类似

\verbatim
lhs = ('+', rhs[0], rhs[2])
\endverbatim

\noindent 要实现这个效果， 语法分析器应当在执行语义动作前%
把从栈弹出的符号的语义值放入 \verb|rhs| 数组，
并在执行语义动作后把 \verb|lhs| 的值作为将要入栈的元素的语义值。

\beginsection 程序 5.1： 语法分析器

实现语法分析器， 分析器表和语义动作直接编码在程序中。
它的输入是记号序列， 无需显式的输出。 如果有语法错误则应当报告。

为了调试方便， 可以打印出 Shift 和 Reduce 动作以及执行该动作时%
状态机的状态和/或栈的内容。

如果想实现更加丰富的功能， 可以参考接下来的几节。

\beginsection 5.2. 一致状态

如果某个状态只有一种可能的动作 （一般来说， 是 Reduce），
则实际上不需要知道输入符号就可以执行这个动作。
如果进行了表格压缩， 则更有可能遇到这样的状态。
是否立即执行 Reduce 动作可能对某些意在用于交互式程序的语法有影响。
例如：
$$\eqalign{
\it input&\to \varepsilon\cr
\it input&\to\it input\; line\;\bf NL\cr
\it line&\to\ldots\cr
}$$
这类语法的目的是以行为单位读取输入。
当用户输入一行命令并换行时， 栈上有 $\it input\;line\;\bf NL$ 三个记号。
此时如果立即执行 Reduce， 对应的语义动作 （处理用户输入的行） 将被执行。
否则， 需要等待下一个符号被输入时才会执行 Reduce， 这可能并不是希望的效果。

\beginsection 5.3. 错误恢复

当遇到语法错误时， 语法分析器应当报告错误。
接下来， 它可以选择终止语法分析或者尝试从错误中恢复。
错误恢复比较困难， 生成的语法分析器通常不具备特别出色的错误恢复能力。

一种常见的做法利用一个特殊的 error 终结符。
语法设计者在编写语法时， 人为地提供一些产生式，
其中包括一个称为 error 的终结符。
当 $\Action(Q,x)={}$Error 时， 语法分析器报告语法错误，
然后依次弹出栈中的内容并回到之前的状态， 直到某个状态 $Q'$ 时，
$\Action(Q',{\rm error})={}$Shift。
（如果不存在这样的状态， 则错误无法恢复， 终止语法分析。）
这时， 语法分析器将执行这个 Shift 操作， 并进入错误恢复模式。

在错误恢复模式中， 如果 $\Action={}$Error， 则丢弃当前输入符号，
且不再报告语法错误。 如果成功地连续 Shift 了足够多的 （一般为 3~个）符号，
认为错误恢复成功， 退出错误恢复模式。

例如如下语法：
$$\eqalign{
S&\to E\; \bf ;\cr
S&\to {\rm error}\; \bf ;\cr
E&\to n\cr
E&\to E+E\cr
}$$

当输入 $n+;$ 时， 分号造成了语法错误， 这时正位于状态
$$E\to E+{\cdot E}$$
栈中的 $+$ 和 $E$ 将被弹出， error 被压入。
这时候分号可以被正确地 Shift。
产生式 $S\to {\rm error}\; \bf ;$ 的作用是帮助语法分析器从不合法的 $S$ 中恢复，
并能够丢弃分号之前的不合法的输入。

\beginsection 6. 输入输出

语法分析器生成器的输入是语法描述文件。 因此， 必须有一个输入端读取这个文件，
分析其中描述的语法， 确定所含有的终结和非终结符、 产生式、 起始符号和语义动作。

有趣的是， 这个前端本身就是一个语法分析器。
它可以用递归下降实现； 也可以由至此已经实现的语法分析器生成器生成，
这样便实现了自举 （bootstrapping）。

一般来说， 语法描述文件至少具有以下两个部分：

\item{1.} 定义部分。 这里可以声明终结符的优先级、 结合性，
各符号的语义值的类型， 等等。
\item{2.} 规则部分。 这里声明各产生式和对应的语义动作。

\smallskip
语法分析器生成器的输出是一个可运行的语法分析器。
因此， 必须有一个输出端向文件写入语法分析器的代码。
“驱动程序” 一节已经实现了一个可运行的语法分析器，
但是分析器表和语义动作是写死在代码里的。
输出端的工作是动态地生成一个语法分析器。

\beginsection 程序 6.1： 输入端

编写一个程序， 它的输入是一个文件，
输出是其中定义的终结和非终结符、 产生式、 起始符号和语义动作信息。

\beginsection 程序 6.2： 输出端

编写一个程序， 把分析器表和语义动作嵌入驱动程序并输出一个可用的语法分析器。
嵌入语义动作时应注意怎样提供一个机制允许语义动作访问产生式的符号。
例如， 用户可以定义一条规则

\verbatim
expr: expr '+' expr { $$ = $1 + $3 }
\endverbatim

\noindent 但输出的语法分析器的相应部分的代码可能是

\verbatim
lhs = rhs[0] + rhs[2]
\endverbatim

\noindent 等等。 还有一种实现办法是允许用户定义符号的别名。 上面的例子将写成

\verbatim
expr(A): expr(B) '+' expr(C) { A = B + C }
\endverbatim

\noindent 生成的代码则是等价的。

\beginsection 7. 组装

上面几节已经实现了语法分析器生成器的几个重要部分：

\item{1.} 输入端 （语法描述文件 $\to$ 终结和非终结符、 产生式、 起始符号、
语义动作）
\item{2.} $\FIRST$~集合计算 （产生式 $\to$ $\FIRST$~集合）
\item{3.} LR(0) 状态机生成 （产生式、 起始符号 $\to$ 状态机）
\item{4.} 前看集合生成 （状态机、 $\FIRST$~集合 $\to$ 前看集合）
\item{5.} 分析器表生成 （状态机、 前看集合 $\to$ 分析器表）
\item{6.} 输出端 （分析器表、 语义动作 $\to$ 语法分析器）

把上述各组件组装在一起， 就是一个可用的语法分析器生成器。


\bye