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分析过程如下：

  1. 将结尾字符$与起始状态0依序压入空堆栈，之后的状态与符号会被压入堆栈的顶端。
  2. 根据目前的状态以及输入的终端符号，到动作表中找到对应动作：
    • 移位（shift）sn:
      • 将目前的终端符号由输入缓冲器中移出并压入堆栈
      • 再将状态n压入堆栈并成为最新的状态
    • 化简（reduce）rm:
      • 考虑第m条文法规则，假设该文法的右边（right-hand side）有X个符号，则将2X个元素从堆栈中弹出
      • 此时过去的某个状态会回到堆栈顶端
      • 在状态转移表中查找此状态遇到文法左边（left-hand side）的符号时的状态转移
      • 将文法左手边的符号压入堆栈
      • 将查找到的新状态压入堆栈
    • 接受，输入字符串解析完成。
    • 无对应动作，此情形即为文法错误。
  3. 重复步骤二直到输入的字符串被接受或侦测到文法错误。

示例

考虑以下文法：

(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），现在我们要找出这组状态可能的转移情形。

参考资料