LR剖析器
上下文无关文法 语法分析器 |
|---|
| · LL剖析器 |
| · 算符优先分析器 |
| · LR剖析器 |
| · SLR剖析器 |
| · LALR剖析器 |
LR剖析器是一种由下而上（bottom-up）的上下文无关语法剖析器。LR意指由左（Left）至右处理输入字串，并以最右边优先衍生（Right derivation）的推导顺序（相对于LL剖析器）建构语法树。能以此方式剖析的语法称为LR语法。而在LR(k)这样的名称中，k代表的是剖析时所需前瞻符号（lookahead symbol）的数量，也就是除了目前处理到的输入符号之外，还得再向右参照几个符号之意；省略 （k）时即视为LR(1)，而非LR(0)。
由于LR剖析器尝试由剖析树的叶节点开始，向上一层层透过文法规则的化简，最后规约回到树的根部（起始符号），所以它是一种由下而上的剖析方法。许多程式语言使用LR(1)描述文法，因此许多编译器都使用LR剖析器分析原始码的文法结构[来源请求]。LR剖析的优点如下：
- 众多的程式语言都可以用某种LR剖析器（或其变形）分析文法。（C++是个著名的例外）
- LR剖析器可以很有效率的建置。
- 对所有“由左而右”扫描原始码的剖析器而言，LR剖析器可以在最短的时间内侦测到文法错误（这是指文法无法描述的字串）。
然而LR剖析器很难以人工的方式设计，一般使用“剖析产生器（parser generator）”或“编译器的编译器（compiler-compiler，产生编译器的工具）”来建构它。LR剖析器可根据剖析表（parsing table）的建构方式，分类为“简单LR剖析器（SLR, Simple LR parser）”、“前瞻LR剖析器（LALR, Look-ahead LR parser）”以及“正统LR剖析器 (Canonical LR parser)”。这些解析器都可以处理大量的文法规则，其中LALR剖析器较SLR剖析器强大，而正统LR剖析器又比LALR剖析器能处理更多的文法。著名的Yacc即是用来产生LALR剖析器的工具。
LR剖析器的结构
以表格为主（table-based）由下而上的剖析器可用图一描述其结构，它包含：
- 一个输入缓冲区，输入的原始码储存于此，剖析将由第一个符号开始依序向后扫描。
- 一座堆叠，储存过去的状态与化简中的符号。
- 一张状态转移表（goto table），决定状态的移转规则。
- 一张动作表（action table），决定目前的状态碰到输入符号时应采取的文法规则，输入符号指的是终端符号（Terminals）与非终端符号（Non-terminals）。
剖析演算法
LR剖析过程如下：
- 将结尾字元$与起始状态0依序压入空堆叠，之后的状态与符号会被压入堆叠的顶端。
- 根据目前的状态以及输入的终端符号，到动作表中找到对应动作：
- 移位（shift）sn:
- 将目前的终端符号由输入缓冲区中移出并压入堆叠
- 再将状态n压入堆叠并成为最新的状态
- 化简（reduce）rm:
- 考虑第m条文法规则，假设该文法的右边（right-hand side）有X个符号，则将2X个元素从堆叠中弹出
- 此时过去的某个状态会回到堆叠顶端
- 在状态转移表中查找此状态遇到文法左边（left-hand side）的符号时的状态转移
- 将文法左手边的符号压入堆叠
- 将查找到的新状态压入堆叠
- 接受，输入字串解析完成。
- 无对应动作，此情形即为文法错误。
- 移位（shift）sn:
- 重复步骤二直到输入的字串被接受或侦测到文法错误。
范例
考虑以下文法：
- (1) E → E * B
- (2) E → E + B
- (3) E → B
- (4) B → 0
- (5) B → 1
待剖析的输入字串是：
- 1 + 1
动作表与状态转移表
LR(0)剖析器使用的表格如下：
| 动作 | 状态转移 | ||||||
| 状态 | * | + | 0 | 1 | $ | E | B |
| 0 | s1 | s2 | 3 | 4 | |||
| 1 | r4 | r4 | r4 | r4 | r4 | ||
| 2 | r5 | r5 | r5 | r5 | r5 | ||
| 3 | s5 | s6 | acc | ||||
| 4 | r3 | r3 | r3 | r3 | r3 | ||
| 5 | s1 | s2 | 7 | ||||
| 6 | s1 | s2 | 8 | ||||
| 7 | r1 | r1 | r1 | r1 | r1 | ||
| 8 | r2 | r2 | r2 | r2 | r2 | ||
动作表用以表示目前状态遇到终端符号（包含结尾字元$）的对应动作，栏位中可能有三种动作：
- 移位，记为'shift' 'n'，表示下个状态是n
- 化简，记为'reduce' 'm'，表示使用第m条文法规则化简堆叠中的内容。
- 接受，记为'accept'，表示剖析正确的完成，输入的字串被文法所定义的语言接受·
状态转移表用以表示简化后的状态遇到非终端符号时的转移规则。
剖析过程
下表是剖析过程中的各步骤，堆叠的顶端在最右边，状态的转移与堆叠的化简都以上表为依据，而特殊字元'$'也被加到输入串的尾端表示结尾。
| 目前的状态 | 堆叠 | 输入 | 将采取的动作 |
|---|---|---|---|
| 0 | $ 0 | 1+1$ | Shift 2 |
| 2 | $ 0 '1' 2 | +1$ | Reduce 5 |
| 4 | $ 0 B 4 | +1$ | Reduce 3 |
| 3 | $ 0 E 3 | +1$ | Shift 6 |
| 6 | $ 0 E 3 + 6 | 1$ | Shift 2 |
| 2 | $ 0 E 3 + 6 '1' 2 | $ | Reduce 5 |
| 8 | $ 0 E 3 + 6 B 8 | $ | Reduce 2 |
| 3 | $ 0 E 3 | $ | Accept |
范例说明
剖析起始时堆叠会包含元素$与0：
- [$ 0]
剖析器首先从输入缓冲区看到符号'1'，根据动作表当状态0碰到终端符号'1'时采用移位动作s2，即是将'1'从输入缓冲区中移出并推入堆叠，再将新的状态2也推入堆叠，这时堆叠会变成：
- [$ 0 '1' 2]
（为避免终端符号与状态混淆，故堆叠中的终端符号都加上单引号区别）
接著看到的终端符号是 '+'，根据动作表无论状态2碰到任何终端符号，都执行r5动作（以第五条文法规则B → 1化简堆叠内容）。此化简的动作表示剖析器已经在堆叠中认出第五条文法规则的右手边部分，因此可以用该规则的左手边符号B取代。因为第五条文法的右边有一个符号，因此我们将两个元素（1 × 2 = 2）自堆叠弹出，此时会回到状态0，再推入符号B，并查找转移表中状态0遇到非终端符号B后的新状态。新的状态是4，完成此步骤后的堆叠是：
- [$ 0 B 4]
由于上一个终端符号 '+'尚未被处理，因此仍保留在输入缓冲区中。依据动作表，在状态4碰到 '+'时做r3化简。根据第三条文法E → B，我们将4与B从堆叠弹出，回到状态0。接著压入E，根据状态转移表，当状态0遇到非终端符号E时需转移至状态3，因此将3压入堆叠：
- [$ 0 E 3]
继续尚未处理的符号 '+'，当状态3遇到 '+'时的对应动作是s6，将 '+'从输入中移出并压入堆叠，再将新的状态6也压入堆叠：
- [$ 0 E 3 '+' 6]
下一个符号是'1'，在状态6看到'1'时的动作是s2，将'1'从输入中移出并压入堆叠，再将新的状态2也压入堆叠：
- [$ 0 E 3 '+' 6 '1' 2]
最后看到的输入符号是$，状态2遇到$时的动作是r5，以第五条文法规则化简堆叠内容。此化简动作与第二步骤相似，堆叠弹出两个元素后回到状态6，这时再压入符号B后会进入状态8（根据状态转移表），因此也将8压入堆叠：
- [$ 0 E 3 '+' 6 B 8]
在状态8看到符号$时剖析器会继续化简，根据动作表执行r2化简动作，采用第二条文法规则E → E + B简化堆叠。由于该规则的右手边有三个符号，故从堆叠中弹出六个元素。这时回到状态0，将规则左边的符号E推入堆叠后，进入新状态3（根据状态转移表），将之压入后堆叠为：
- [$ 0 E 3]
最后在状态3看到符号$，对应的动作是acc，表示剖析顺利完成。
建构LR(0)剖析表
LR(0)项目（Items）
建构剖析表的过程须使用LR(0)项目（以下简称为“项目”），这些项目是在文法规则的右手边插入一个特殊的符号“·”所产生。例如文法E → E + B有下列四个对应的项目：
- E →·E + B
- E → E· + B
- E → E + ·B
- E → E + B·
若文法规则的形式是A → ε，则对应的唯一项目是：
- A →·
建立项目的用意是要决定剖析器的状态，例如E → E· + B的意义是“剖析器已经在输入的符号中认出E的部分，目前正等著看到一个 '+'符号与接续的B的部份”。
结论：LR(0)项目是由文法规则所产生
项目集合
在一般的情形中，剖析器不能预知未来要用哪一条文法规则来化简堆叠内容，因此很难以单一个项目决定状态。例如以下文法：
- E → E + B
- E → E * B
当剖析器认出堆叠中的E部分时，它无法预测未来会继续看到 '+'或'*'，因此这时的状态须以两个项目表示：
- E → E· + B
- E → E·* B
故我们使用项目的集合{ E → E· + B, E → E·* B }来表示“剖析器认出E并期待 + B或* B”的状态。
结论：LR(0)项目可以形成集合并描述剖析过程的状态
项目集合的封闭集
如前段叙述，剖析器总是期待在下个输入中看到项目中的'·'之后的符号。如果'·'之后的符号是非终端符号，则应加入该符号所推演出的文法规则，如此才能正确的描述状态。例如规则：
- E → E + B
- B → 0
- B → 1
当我们来到状态E → E + ·B时，剖析器期待看到非终端符号B，而B又可推演为终端符号0与1。因此这时的状态应表示为：
- E → E + ·B
- B →·0
- B →·1
即是“已辨认出E +部分，目前期待看到B，而B也就是'0'与'1'”之意。此现象可以描述为：
- 若项目集合中包含A → x·By形式的项目，其中B为非终端符号，则对所有的文法规则B → w而言，B →·w也会被加入项目集合中。
每个项目集合都应该以此规则扩充，将潜在的项目加到集合中直到所有在·之后的非终端符号都处理过。如此所产生的新集合称作该项目集合的“封闭集”，符号的表示为closure(I) ，其中I表示原项目集合。剖析过程中的各种状态即是由这些封闭集所构成。
结论：项目的封闭集才能完整的描述剖析过程的状态
扩充文法
在决定状态间的转移前，我们必须先加入一条扩充文法：
- (0) S → E
其中S是新的起始符号（start symbol）而E是原先的起始符号。这一做法是为了使剖析器能有一个唯一的起始状态，例如考虑以下文法：
- (1) E → E * B
- (2) E → E + B
- (3) E → B
- (4) B → 0
- (5) B → 1
有三条规则从起始符号开始，剖析器不得不选择一条作为起始状态。加入扩充文法后，我们使用下列规则来决定项目集合与状态：
- （0）S → E
- (1) E → E * B
- (2) E → E + B
- (3) E → B
- (4) B → 0
- (5) B → 1
可见起始状态唯一确定。
结论：建构剖析表前必须先加入扩充文法
寻找可到达的集合与之间的转移
建构剖析表的第一步是找出封闭集合之间的转移。封闭集可以视为自动机中的状态，而状态间的转移则由终端符号与非终端符号决定。起始状态是由扩充的第0条文法规则对应的项目所形成的封闭集：
- Item set 0
- S →·E
- E →·E * B
- E →·E + B
- E →·B
- B →·0
- B →·1
集合中的第一个项目是该集合的核心，透过集合的封闭规则，我们加入其他项目补足集合使其封闭。这组封闭集合是第一个状态（I0），现在我们要找出这组状态可能的转移情形。