Bottom-Up Parsing

自底向上的解析器从叶子节点开始构建解析树，并向其根部工作。解析器为扫描器返回的每个token构建一个叶节点。这些叶子构成了解析树的下边缘。为了构建一个derivation，解析器在叶子节点上方添加非终结符的层，这个结构由语法和部分完成的解析树的下层所决定。

在解析的任何阶段，部分完成的解析树表示解析的状态。扫描器返回的每个token都由一个叶子节点表示。叶子节点上方的节点编码了解析器已经推导出的所有知识。解析器沿着部分完成的解析树向上工作；内部节点对应于解析器正在构建的derivation中的当前句子形式。

自底向上解析器重复一个简单的过程。它在输入字符流的右边界不断寻找有效的handle $\left \langle A \rightarrow \beta ,k \right \rangle$ ，此时用A代替了k点出现的β。整个过程不断重复直到:(1)它将当前边界化解到表示语法器全局符号的单个节点。(2)它找不到handle。第一种情况下，解析器发现了一个diveration;如果它也消耗了输入字符流中的所有字符(即下一个单词是eof)，则解析成功。第二种情况下，解析器无法对输入字符流构建一个完整的diveration，所以需要抛出错误信息。

$Handle : \left \langle A \rightarrow \beta ,k \right \rangle$ ，在解析的第k个位置，子串 $\beta$ 可以替换为A，并且作为解析的下一步是合法的diveration,通常 $k=|\beta|$

在自底向上解析过程中，为了使解析过程正确高效，diveration和parse之间的关系扮演着关键角色。自底向上解析从最后的句子向全局符号工作，diveration相反，从全局符号出发，不断推导直到最后的句子。可以看出，parse和diveration在执行步骤上是相反地。一个diveration：

Goal=\gamma_0\rightarrow\gamma_1\rightarrow\gamma_2\rightarrow…\rightarrow\gamma_{n-1}\rightarrow\gamma_n=sentence

自底向上解析器在发现 $\gamma_{i}\rightarrow\gamma_{i+1}$ 之前，先发现 $\gamma_{i-1}\rightarrow\gamma_i$ ，构建解析树的过程严格遵循这个规则。

算术表达式小游戏

为了更好地向读者解释自底向上解析的原理，我们先来放松一下，玩一个小游戏：

游戏目标：玩家需要通过收集卡片和构建算术表达式来挑战自己的数学能力。

游戏规则：

游戏中有两个玩家，玩家A和玩家B，他们分别位于传送带的两端。
玩家B拥有一组卡片，每张卡片上都有一个数字或一个运算符。
玩家A的任务是从玩家B的卡片中选择一张卡片，并将其放入一个箱子中。
玩家A可以选择Shift操作，将所选卡片放入箱子中；或者选择Reduce操作，从箱子中取出足够的卡片来构建一个算术表达式，并将结果放回箱子中。
如果玩家选择Reduce操作时，箱子中没有足够的卡片来构建一个算术表达式，则提示错误。
玩家A需要构建一个合法的算术表达式，并将其解决。
当玩家A成功构建并解决一个算术表达式时，游戏结束并宣布玩家A为胜利者。
如果玩家A构建的算术表达式不合法，则游戏结束并宣布玩家B为胜利者。
玩家A和玩家B轮流进行操作，直到游戏结束。

游戏道具：

卡片：卡片上有数字和运算符，玩家A可以选择其中一张卡片。
箱子：用来存储卡片和构建的算术表达式，玩家A可以选择Shift或Reduce操作来管理箱子中的内容。

游戏流程：

游戏开始时，玩家A和玩家B分别位于传送带的两端。
玩家B从卡片组中选择一张卡片，并将其放在传送带上。
玩家A选择Shift或Reduce操作，将所选卡片放入箱子中或从箱子中取出卡片来构建算术表达式。
如果玩家A构建的算术表达式合法，则继续进行游戏；否则游戏结束，玩家B获胜。
游戏继续进行，直到玩家A构建并解决一个合法的算术表达式，游戏结束，玩家A获胜。

游戏示意图如下：

假设B手中的卡片序列为 $5+2*3$ ，A为了赢得比赛，应该怎么做呢？

选择Shift，将卡片“5”放入桶中
选择Shift，将卡片“+”放入桶中
选择Shift，将卡片“2”放入桶中
选择Shift，将卡片“*”放入桶中
选择Shift，将卡片“3”放入桶中
选择Reduce，从桶中拿出上方的三张卡片：“2”，“*”，“3”，计算结果，并放入桶中，此时桶里的内容为“5”、“+”、“6”
选择Reduce，从桶中拿出上方的三张卡片：“5”，“+”，“6”，计算结果为11。此时桶中和B手上都没有卡片了，A报告最终结果11，赢得比赛。

对于A来说，要想赢得比赛，就需要根据桶中的内容做出合理正确地决策：Shift或者Reduce。看到这里，是不是感觉和Bottom-Up解析的目标相似？即寻找合理的Handle直到成功解析。Bottom-Up Parser也叫做Shift-Reduce Parser。下面介绍几种解析算法：LR(0)、LR(1)。

LR(0)

LR(0),顾名思义就是说我们在解析时，只使用当前已经有的知识，不会向前看一步。拿前面小游戏的例子说明的话，相当于我们只关注桶里的内容，不会观察传送带上的卡片。任何LR算法的前提都需要构建DFA，这里引入几个概念：

item ：在production基础上引入位置信息，形如 $A\rightarrow a.Bc$ 结构的项，我们称之为item。在 $.$ 左边的部分表示当前已经识别的字符串，称为item的前缀，在 $.$ 右边的部分表示将要被识别的字符串，称为item的后缀。

state ：state是item的集合，同一个state中item的前缀相同。

transition ：转移是状态之间的有向边，对于 $A\rightarrow a.Bc$ 来说，我们向右走一步，形成 $A\rightarrow aB.c$ ，对于包含这两个item的状态s1,s2，对应的转移表示为 $s_1\rightarrow^{B} s_2$

在DFA中，有开始状态，有终止状态，我们说：如果一个state包含的item具有形式 $A\rightarrow .aBc$ ，这个状态就是开始状态，如果item具有形式 $A\rightarrow aBc.$ 这个状态是终止的；可是看出终止状态中可能包含LR解析算法中寻找的handle！中间状态中item的形式自然就是 $A\rightarrow a.Bc$ ，这些状态加上transition就构成了LR算法需要的DFA。构建DFA的关键在于：

1.给定一个项集s0，对这个项集进行补全，使其包含所有具有公共前缀的item项，此时项集是完整的，这个过程叫做计算项集的闭包。
2.给定一个完整项集，给出这个项集的所有后继项集。

计算后继项集是生成项集的过程，计算闭包是完善项集的过程。这两种操作不断循环，直到所有的项集不再改变，此时我们就得到了一个从起始状态出发，于终止状态结束的DFA了。

计算状态的闭包

规则

1.如果 $A\rightarrow\alpha.B\omega$ 是状态s的一个item，将所有具有 $B\rightarrow.\gamma$ 形式的item加到s中。

2.直到s不再改变

生成后继状态

规则

1.如果状态s中的item为 $A\rightarrow\alpha.x\omega$ ,生成后继状态s1，将item $A\rightarrow\alpha x.\omega$ 添加到s1中。计算后继状态的闭包: $s_1\leftarrow closure(s_1)$

2.直到没有新的状态可以生成。

一个例子

语法：

S0 -> S

S  -> E;
E  -> E-T

E  -> T

T  -> (E)

T  -> id

对应的DFA：

解析表

给定DFA，我们将其转换为更方便的解析表，具体包括action表和go-to表。

action表将状态映射为解析时采取的动作：
对于所有非终止状态，动作为shift；对于所有终止状态而言，动作为reduce。

go-to表将所有<state,symbol>映射为后继状态

对于上面给出的语法，对应的解析表如下：

LR(0)解析算法

1.初始化，<None,0>压入栈S

2.栈不空时，重复下面的步骤：

3.读取栈顶元素状态 $S_{top}$

4.如果 $action[S_{top}]为shift$ ：

从输入流中读取下一字符 $t$

查找下一状态 $S_{next}\leftarrow goto[S_{top},t]$

将 $<t,S_{next}>$ 压入栈S中

5.如果 $action[S_{top}]为reduce A\rightarrow \omega$ :

从栈顶弹出 $|\omega|$ 个元素

读取栈顶元素状态 $S_{top}$

查找下一状态 $S_{next}\leftarrow goto[S_{top},A]$

将 $<A,S_{next}>$ 压入栈S中

6.如果 $action[S_{top}]为accept$ :

返回True

7.其他情况返回错误e

解析过程用下面的动图演示：

输入序列为 $id-id-(id-id);$ 图中高亮的production表示当前进行规约所采用的规则。

LR(0)局限

LR(0)无法解决语法冲突，这里有两种冲突：

shift-reduce冲突，同一状态中即有reduce item，同时也有shift item。
reduce-reduce冲突，同一状态中包含不同地reduce item。

此时同一状态s可以进行的动作不是唯一的，解析算法无法找出正确的解析路径。在面对冲突时，LR(0)只利用了当前已有的上文左手信息，所以无法解决冲突。如果我们可以像LL算法那样，朝前看几步，就可以解决这些问题，LR(1)算法就是为此而设计的，下面介绍LR(1)算法。

LR(1)

前面已经介绍了，LR(0)在面对冲突时，无法从当前已有的信息中做出正确抉择，我们可以将语法结构中的右手信息进行编码，加入到LR(0)的item中，这样就能够解决冲突：

LR(1) item: $[A\rightarrow a.Bc;l]$ ，这里l表示lookahead字符，对当前语法结构的右手信息进行了编码。

如果LR(0)状态为N个，其中语法结构字符个数为k，那么LR(1)状态指数膨胀，最多有 $N*2^{k}$ 个。

计算状态的闭包

规则

1.如果 $A\rightarrow\alpha.B\omega[t]$ 是状态s的一个item，将所有具有 $B\rightarrow.\gamma[t]$ 形式的item加到s中，其中 $t\in FIRST(\omega t)$

2.直到s不再改变

生成后继状态

规则

1.如果状态s中的item为 $A\rightarrow\alpha.x\omega[t]$ ,生成后继状态s1，将item $A\rightarrow\alpha x.\omega[t]$ 添加到s1中。计算后继状态的闭包: $s_1\leftarrow closure(s_1)$

2.直到没有新的状态可以生成。

一个例子

语法：

S0 -> S

S  -> E
E  -> E-T

E  -> T

T  -> (E)

T  -> id

和上一个语法相比，这个语法只是简单地把分号去掉了，但却引入了shift-reduce冲突，对应的LR(0),LR(1)自动机如下图所示：

LR(0)自动机.png

LR(1)自动机.png

解析表

action表将<state,lookahead>映射为解析时采取的动作：
对于所有非终止状态，动作为shift；对于所有终止状态而言，动作为reduce。其中lookahead为终止字符。

go-to表将所有<state,symbol>映射为后继状态,其中symbol为非终止字符

对于上面给出的语法，对应的解析表如下：

sk表示shift to state k，rj表示reduceing using production j。

LR(1)解析算法

1.初始化，<None,0>压入栈S

2.栈不空时，重复下面的步骤：

3.读取栈顶元素状态 $S_{top} 、输入流当前字符t$

4.如果 $action[S_{top},t]为shift\,\,k$ ：

从输入流中读取下一字符 $t$

查找下一状态 $S_{next}\leftarrow k$

将 $<t,S_{next}>$ 压入栈S中

5.如果 $action[S_{top},t]为reduce A\rightarrow \omega$ :

从栈顶弹出 $|\omega|$ 个元素

读取栈顶元素状态 $S_{top}$

查找下一状态 $S_{next}\leftarrow goto[S_{top},A]$

将 $<A,S_{next}>$ 压入栈S中

6.如果 $action[S_{top},t]为accept$ :

返回True

7.其他情况返回错误e

解析过程用下面的动图演示：

输入序列为 $id-id-(id-id)$ 图中高亮的production表示当前进行规约所采用的规则。

总结

本篇从原理出发，详细介绍了自底向上的常用算法原理，给出了构建LR算法必须的自动机、解析表构建流程，并结合例子说明了LR(0)与LR(1)算法的区别联系，值得一提的是：LR(1)生成的状态是指数增长地，这在实际应用上对存储空间上是巨大的挑战，即便使用压缩算法对表进行压缩，依然不可忍受。所以通常采用SLR与LALR算法对LR(0)与LR(1)进行折中考虑。SLR算法将follow集合引入LR(0)项，只有当lookahead字符存在于reduce项的follow set中时，才进行reduce。LALR思想则是对于LR(1)的item，如果除了lookahead不同，其余都相同，则这些item可以进行合并，最终merge过后的状态个数等同于LR(0)的状态，因此也叫lookahead 1 LR(0)。

文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。

THE END