Bottom-Up Parsing

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

在解析的任何阶段，部分完结的解析树表明解析的状况。扫描器回来的每个token都由一个叶子节点表明。叶子节点上方的节点编码了解析器现已推导出的一切知识。解析器沿着部分完结的解析树向上作业；内部节点对应于解析器正在构建的derivation中的当时语句方式。

自底向上解析器重复一个简略的进程。它在输入字符流的右鸿沟不断寻觅有用的handle $⟨A→,k⟩\left \langle A \rightarrow \beta ,k \right \rangle$ ，此刻用A代替了k点呈现的。整个进程不断重复直到:(1)它将当时鸿沟化解到表明语法器大局符号的单个节点。(2)它找不到handle。第一种状况下，解析器发现了一个diveration;假如它也耗费了输入字符流中的一切字符(即下一个单词是eof)，则解析成功。第二种状况下，解析器无法对输入字符流构建一个完整的diveration，所以需求抛出过错信息。

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

在自底向上解析进程中，为了使解析进程正确高效，diveration和parse之间的关系扮演着关键人物。自底向上解析从终究的语句向大局符号作业，diveration相反，从大局符号动身，不断推导直到终究的语句。能够看出，parse和diveration在执行进程上是相反地。一个diveration：

Goal=0→1→2→…→n−1→n=sentenceGoal=\gamma_0\rightarrow\gamma_1\rightarrow\gamma_2\rightarrow…\rightarrow\gamma_{n-1}\rightarrow\gamma_n=sentence

自底向上解析器在发现 $i→i+1\gamma_{i}\rightarrow\gamma_{i+1}$ 之前，先发现 $i−1→i\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→a.BcA\rightarrow a.Bc$ 结构的项，咱们称之为item。在 $.$ 左边的部分表明当时现已辨认的字符串，称为item的前缀，在 $.$ 右边的部分表明将要被辨认的字符串，称为item的后缀。

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

transition ：搬运是状况之间的有向边，关于 $A→a.BcA\rightarrow a.Bc$ 来说，咱们向右走一步，构成 $A→aB.cA\rightarrow aB.c$ ，关于包括这两个item的状况s1,s2，对应的搬运表明为 $s1→Bs2s_1\rightarrow^{B} s_2$

在DFA中，有开端状况，有停止状况，咱们说：假如一个state包括的item具有方式 $A→.aBcA\rightarrow .aBc$ ，这个状况便是开端状况，假如item具有方式 $A→aBc.A\rightarrow aBc.$ 这个状况是停止的；但是看出停止状况中或许包括LR解析算法中寻觅的handle！中间状况中item的方式天然便是 $A→a.BcA\rightarrow a.Bc$ ，这些状况加上transition就构成了LR算法需求的DFA。构建DFA的关键在于：

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

核算后继项集是生成项集的进程，核算闭包是完善项集的进程。这两种操作不断循环，直到一切的项集不再改动，此刻咱们就得到了一个从开始状况动身，于停止状况完毕的DFA了。

核算状况的闭包

规矩

1.假如 $A→.BA\rightarrow\alpha.B\omega$ 是状况s的一个item，将一切具有 $B→.B\rightarrow.\gamma$ 方式的item加到s中。

2.直到s不再改动

生成后继状况

规矩

1.假如状况s中的item为 $A→.xA\rightarrow\alpha.x\omega$ ,生成后继状况s1，将item $A→x.A\rightarrow\alpha x.\omega$ 增加到s1中。核算后继状况的闭包: $s1←closure(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$

查找下一状况 $Snext←goto[Stop,t]S_{next}\leftarrow goto[S_{top},t]$

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

5.假如 $action[Stop]为reduceA→action[S_{top}]为reduce A\rightarrow \omega$ :

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

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

查找下一状况 $Snext←goto[Stop,A]S_{next}\leftarrow goto[S_{top},A]$

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

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

回来True

7.其他状况回来过错e

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

输入序列为 $i d - i d - (i d - i d);$ 图中高亮的production表明当时进行规约所选用的规矩。

LR(0)局限

LR(0)无法处理语法抵触，这儿有两种抵触：

shift-reduce抵触，同一状况中即有reduce item，同时也有shift item。
reduce-reduce抵触，同一状况中包括不同地reduce item。

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