C# 中的 LALR 解析表生成
4.84/5 (14投票s)
使用 C# 生成 LALR 解析表。
引言
基于表生成解析器提供了快速灵活的解析器构建的可能性。本文描述了一种构建 LR（从左到右自底向上）解析器的解析表的方法，称为 LALR 解析器或前瞻-LR 解析器。
背景
LR 解析器由一个解析表和一个堆栈组成。此类解析器通过从左到右检查输入标记串并执行以下操作之一来识别输入标记串：
- 将标记移入堆栈
- 将堆栈上的几个标记进行归约，用语法产生式左侧的标记替换堆栈上相应的右侧标记，该产生式必须存在于堆栈上
- “接受”输入字符串
- 产生错误
LALR 算法生成一个解析器表，该表使用前瞻的概念来决定给定状态下的可能归约。该算法通过转换和语法产生式检查进入和离开每个状态的产生式，并确定表示在状态中的每个产生式，在产生式之后可能出现哪些标记。
使用代码
我发布的代码创建了一个解析表，并将解析表格式化输出到控制台。
using System;
using CodeProject.Syntax.LALR;
namespace TestProject
{
class MainClass
{
public static void Main (string[] args)
{
//
// the following program produces a parse table for the following grammar
// for infix expressions, and appropriately applies operator precedence of
// the + - * / operators, otherwise evaluating the leftmost operations first
//
// S' -> e
// e -> i
// e -> ( e )
// e -> e * e
// e -> e / e
// e -> e + e
// e -> e - e
//
//
Grammar grammar = new Grammar();
grammar.Tokens = new string[]{"S'", "e", "+", "-", "*", "/", "i", "(", ")"};
grammar.PrecedenceGroups = new PrecedenceGroup[]
{
new PrecedenceGroup
{
Derivation = Derivation.None,
Productions = new Production[]
{
//S' -> e
new Production{
Left = 0,
Right = new int[]{1}
},
//e -> i
new Production{
Left = 1,
Right = new int[]{6}
},
//e -> ( e )
new Production{
Left = 1,
Right = new int[]{7, 1, 8}
}
}
},
new PrecedenceGroup
{
Derivation = Derivation.LeftMost,
Productions = new Production[]
{
//e -> e * e
new Production{
Left = 1,
Right = new int[]{1, 4, 1}
},
//e -> e / e
new Production{
Left = 1,
Right = new int[]{1, 5, 1}
},
}
},
new PrecedenceGroup
{
//productions are left associative and bind less tightly than * or /
Derivation = Derivation.LeftMost,
Productions = new Production[]
{
//e -> e + e
new Production{
Left = 1,
Right = new int[]{1, 2, 1}
},
//e -> e - e
new Production{
Left = 1,
Right = new int[]{1, 3, 1}
}
}
}
};
// generate the parse table
Parser parser = new Parser(grammar);
// write the parse table to the screen
Debug.DumpParseTable(parser);
}
}
}
并产生以下输出
+---+---+---+---+---+---+---+---+---+---+---+
|###| $ |S' | e | + | - | * | / | i | ( | ) |
|---+---+---+---+---+---+---+---+---+---+---+
| 0| | |S 1| | | | |S 2|S 3| |
+---+---+---+---+---+---+---+---+---+---+---+
| 1|R 0| | |S 4|S 5|S 6|S 7| | | |
+---+---+---+---+---+---+---+---+---+---+---+
| 2|R 1| | |R 1|R 1|R 1|R 1| | |R 1|
+---+---+---+---+---+---+---+---+---+---+---+
| 3| | |S 8| | | | |S 2|S 3| |
+---+---+---+---+---+---+---+---+---+---+---+
| 4| | |S 9| | | | |S 2|S 3| |
+---+---+---+---+---+---+---+---+---+---+---+
| 5| | |S10| | | | |S 2|S 3| |
+---+---+---+---+---+---+---+---+---+---+---+
| 6| | |S11| | | | |S 2|S 3| |
+---+---+---+---+---+---+---+---+---+---+---+
| 7| | |S12| | | | |S 2|S 3| |
+---+---+---+---+---+---+---+---+---+---+---+
| 8| | | |S 4|S 5|S 6|S 7| | |S13|
+---+---+---+---+---+---+---+---+---+---+---+
| 9|R 5| | |R 5|R 5|S 6|S 7| | |R 5|
+---+---+---+---+---+---+---+---+---+---+---+
| 10|R 6| | |R 6|R 6|S 6|S 7| | |R 6|
+---+---+---+---+---+---+---+---+---+---+---+
| 11|R 3| | |R 3|R 3|R 3|R 3| | |R 3|
+---+---+---+---+---+---+---+---+---+---+---+
| 12|R 4| | |R 4|R 4|R 4|R 4| | |R 4|
+---+---+---+---+---+---+---+---+---+---+---+
| 13|R 2| | |R 2|R 2|R 2|R 2| | |R 2|
+---+---+---+---+---+---+---+---+---+---+---+
解析器类
Parser 类封装了 LALR 表构建算法，但也公开了几个对语法分析和调试有用的方法和属性。
解析器 - 构造函数
使用以下方法和其他支持方法分析语法，生成解析表。
GenerateLR0Items
通过从状态 S' -> .X 开始，生成解析器的 LR(0) 状态，其中 X 是语法的开始符号。必须将产生式 S' -> X 显式传递给上面的构造函数。
LR(0) 项由项集 {S' -> .X} 组成，以及所有可以通过替换 `.` 之后的第一个符号（在本例中为 X）与任何以 X 作为右侧的产生式的左侧而可达的状态。此操作称为 LR(0) 项的闭包。在上面的语法中，状态 0 由以下项集组成。
S' -> . e
e -> . i
e -> . ( e )
e -> . e * e
e -> . e / e
e -> . e + e
e -> . e - e
然后，我们找到语法中任何标记 X 的状态 Goto(X)，并找到状态 0 的后继状态。这是通过包含每个带有 `.` 右侧的 X 的项，并将它们放入新状态，然后计算该新状态的闭包来完成的。对于所呈现语法中的标记 e，新状态，即状态 '1'，具有以下 LR(0) 项
S' -> e .
e -> e . * e
e -> e . / e
e -> e . + e
e -> e . - e
该方法重复此过程，直到没有新状态为止。
ComputeFirstSets
此方法计算语法中任何标记之后可能出现的终结符集合。标记 e 的 first 集为 {i, (}。此构建使得稍后能够计算 LALR 状态。
CalculateLookAheads
从上面的 GenerateLR0Items 计算每个 LR0 项的前瞻项。状态中产生式末尾的前瞻项告诉解析器执行归约是安全的。例如，上面状态 2 在标记 ) 上可以通过产生式 e -> i 进行归约，从而用非终结符 e 替换堆栈上的 i。解析器知道它可以这样做，因为 LALR 状态 2 包含产生式 e -> i 和前瞻标记 ) 的 LALR 项 e -> i. , )。
GenerateParseTable
此方法构造解析表的动作。它通过合并每个状态的 Goto 动作和前一个方法生成的归约所允许的归约动作来做到这一点。如果在任何状态下 Goto 或归约之间存在冲突，算法会尝试通过选择更高优先级组的规则来解决。如果没有明确的获胜者，那么算法会检查规则是应该产生最左边还是最右边的推导。最左边的推导将倾向于归约，而最右边的推导将倾向于 Goto。如果仍然没有明确的获胜者，算法将宣布 Reduce-Reduce 或 Shift-Reduce 冲突错误。
Debug 类
示例代码中的 Debug 类包含几个可能有助于调试语法或解析器的有用方法。
DumpParseTable
将格式化的解析表写入控制台。
DumpLR0State
将 LR(0) 状态写入控制台。例如，以下代码段将上面状态 0 写入控制台。
Debug.DumpLR0State(parser, parser.LR0States[0]);
DumpLALRState
将 LALR 状态（包括前瞻）写入控制台。以下代码段将生成解析器状态 0 中的 LALR 项写入控制台。
Debug.DumpLR1State(parser, parser.LALRStates[0]);
参考文献
  |
该项目代码实现了 Aho、Sethi 和 Ullman 在《编译原理、技术和工具》（1986）这本“龙书”中描述的 LALR 算法。 |
功能待办
我打算在后续更新中实现以下功能。
- 生成一个 C# 类型，用于解析输入语法
- 从文件解析输入语法
- 通过 ComponentModel/Reflection 调用执行语法归约规则的类型/方法
- 用不同语言生成解析器
历史
- 2011-09-07：初始实现，生成解析表。
- 2015-06-03：添加了资源链接