编译器中间件开发 .NET C#

有歧义？让 NLT 为您解析

greenoldman

4.83/5 (4投票s)

2013 年 11 月 6 日

MIT

8分钟阅读

21223

.Net 世界的词法分析器+语法分析器套件

介绍

当您只需要使用正则表达式就能处理字符串/文本时，这很好（而且速度很快），但当您有更复杂的任务要处理时，拥有更强大的工具——词法分析器和语法分析器——就会派上用场。已经有一些用 C# 编写的解析器了，但我认为老派的 YACC 式解析器的位置还没有被填补。嗯，直到现在。

背景

下面我将描述的“Naive Language Tools”套件实际上是我将 COOL 框架移植到 C# 的一个副产品。

大约一年半前，我报名参加了 Alex Aiken 教授的“编译器”课程（强烈推荐），因为我一直对编译器是如何工作的以及如何编写一个编译器感到好奇。整个课程比我想象的还要充实，我想贡献一些我自己的东西（可以说是一种回报）——当时课程团队提供了 C++ 和 Java 框架，为什么不为我最喜欢的 C# 制作一个框架呢？

只有一个问题——在我编写 C# 框架的时候，我找不到一个可靠的、类似 YACC/CUP 的 C# 解析器（与这些工具的相似性是必须的，以便让学生们可以在一个框架切换到另一个框架）。

好吧，管他呢，我刚上完课，我写了自己的 COOL 编译器，我也应该能够写一个词法分析器和一个语法分析器。事实确实如此——NLT 就是这样诞生的。最初，它具有构建 COOL 编译器所需的功能，但随着时间的推移，我添加了越来越多的功能。

词法分析器获得了基本的上下文扫描功能，语法分析器成为了一个 LALR(k) 分支解析器，而且由于我将 NLT 用于我自己的目的，它每天都在变得越来越完善。好吧，好吧，更像是每周。

让我们来看一些实际操作

本文的代码已包含在 NLT 包的“05. 模式和分支”示例中。

请允许我介绍一个相当疯狂的计算器，以展示 NLT 如何处理语言歧义。让我们构建一个带有加法和减法的常规计算器，但还增加了位移（“a < b”、“a > b”）和位索引（“a<b>”——它给出“a”的第 b 位）。

运算符的优先级和结合性——从最低优先级到最高优先级

加法和减法——从左到右，
位移——从左到右，
位索引。

词法分析器——切分输入

您可以直接在 C# 代码中定义所有动作，也可以将它们写成 NLT 语法，然后让 NLT 生成器创建词法分析器和语法分析器。为了易读性，我们在这里采用后一种方法。

让我们从无聊的东西开始

lexer LexerFactory;
token SymbolEnum;
states StatesEnum
  *INIT
end

这里定义了词法分析器工厂的类名，以及标记和状态的类型（枚举）。因为我们的计算器非常基础，我们只需要一种状态（星号表示它是默认状态）。

输入切分如下进行

scanning // start of lexer rules
  "+" -> PLUS;
  "-" -> MINUS;
  "<" -> LANGLE;
  ">" -> RANGLE;

我们使用字符串模式匹配文本并返回一个终结符（大写用于区分非终结符和特殊标记——“Error”）。接下来，我们使用正则表达式模式来捕获数字。

  // regex as pattern
  /[0-9]+/ -> NUM, Convert.ToInt32($text);

“$text”是伪变量之一。默认情况下，匹配的文本被赋值给标记的值，但最好在这里而不是稍后在解析器中转换文本为数字。

我们必须添加一点清理工作

  " "     { };    // ignore spaces
  /./  -> Error;  // “anything else” rule
  %EOF -> EOF;
end // end of lexer rules

由于无法使用字符串或正则表达式模式匹配文件结束（EOF），因此有特殊的条目“%EOF”。右边的 EOF 是一个预定义的终结符。

语法分析器——找出结构

开始

我们又从无聊的东西开始

parser ParserFactory;
types
  NUM int;
  expr Tuple<int,string>;
end

“type”部分允许我们定义所有符号的类型——这样我们就无需在解析器动作中进行变量转换。这里我们定义 NUM 终结符为“int”，并将表达式定义为一个值对。

我们希望在这里保持简单——正如任何计算器一样，我们希望得到计算结果，因此第一个元素是“int”，但由于解析将是所有乐趣所在，我们添加了一个对解析布局（扁平解析树）的跟踪——单个“string”作为第二个元素就足够了。

一切准备就绪后，我们终于可以处理解析产生了

parsing // start of parser rules
comp -> e:expr { e };

在 NLT 中，第一个产生式的左手边（LHS）符号被识别为起始符号，并且只能出现一次。这里我们基本上说整个计算就是一个表达式。

expr -> e1:expr MINUS e2:expr
        { pair(e1.Item1 - e2.Item1, "("+e1.Item2+" - "+e2.Item2+")") }
      | e1:expr PLUS e2:expr 
        { pair(e1.Item1 + e2.Item1, "("+e1.Item2+" + "+e2.Item2+")") }
      | e1:expr LANGLE e2:expr
        { pair(e1.Item1 << e2.Item1, "("+e1.Item2+" < "+e2.Item2+")") }
      | e1:expr RANGLE e2:expr
        { pair(e1.Item1 >> e2.Item1, "("+e1.Item2+" > "+e2.Item2+")") }
      | e1:expr LANGLE e2:expr RANGLE 
        { pair((e1.Item1 & (1 << e2.Item1)) >> e2.Item1, "("+e1.Item2+"["+e2.Item2+"])") }
      | n:NUM 
        { pair(n, n) }
      ;
end // end of parser rules

从上到下，我们将表达式定义为表达式的减法、加法、位移或位索引。最后一个规则说明表达式也是一个单独的数字。

够了吗？当我们运行 NLT 生成器（使用“refresh”脚本）处理这个语法时，我们会很快发现我们遗漏了一些东西——NLT 报告以以下内容开始：

Reduce/shift conflict on symbol MINUS. Affected items: 3.1, 3.0
3.0)  expr := expr MINUS expr .
3.1)  expr := expr . MINUS expr

实际报告的信息更丰富一些。

这意味着，根据给定的规则，NLT 解析器无法决定“1-2-3”应该如何解析——它应该被读取为“(1-2)-3”还是“1-(2-3)”？PLUS 符号也面临同样的问题。

为了解决这个问题，我们添加了优先级部分

precedence
  op left MINUS PLUS;
end

这是“运算符”符号的简单优先级规则——这里是 MINUS 和 PLUS——它们告诉我们从左到右结合运算符（换句话说，产生式应该按 (3.0) 的方式进行归约）。

再次运行生成器

Reduce/shift conflict on symbol LANGLE. Affected items: 3.3, 3.5, 3.0
3.0)  expr := expr MINUS expr .
3.3)  expr := expr . LANGLE expr
3.5)  expr := expr . LANGLE expr RANGLE

这很简单——我们已经说过，加法和减法具有最低优先级。所以，只需添加第二条优先级规则即可。

op left LANGLE RANGLE;

我们使用“left”（左结合）是因为我们希望 xANGLEs 也具有从左到右的结合性。
生活是美好的，这次没有冲突，所以我们可以运行我们的解析器来尝试一些计算：

$ 1-2-3 
The outcome: -4
The parse layout: ((1 - 2) - 3)

$ 1<2<3
The outcome: 32
The parse layout: ((1 < 2) < 3)

让我们检查一下位索引：

$ 1<2>
There were errors while parsing.

更宏大的图景

除了上述错误之外，NLT 还添加了一条评论说：

No action defined at node 10 for input "EOF" with stack "expr RANGLE".

这个抱怨是有道理的——解析器在看到“1<2”后，（我们指示它那样做）将其归约为一个表达式，然后它不知道如何处理悬空的右尖括号。看来 NLT 之前就警告过我们，但我们阅读的冲突报告部分太少了。

罪魁祸首在这里

Reduce/shift conflict on symbol LANGLE. Affected items: 7.3, 7.5, 7.0
7.0)  expr := expr LANGLE expr .
7.3)  expr := expr . LANGLE expr
7.5)  expr := expr . LANGLE expr RANGLE

这个冲突转化为以下场景——我们有“1 < 2 < ...”并且我们必须决定“1<2”是否可以构成一个有效表达式，或者我们应该等待更多输入。从 (7.0) 对比 (7.3) 来看，我们会说“归约”（左结合），但然后——从 (7.0) 对比 (7.5) 来看，我们会说“移位”（位索引具有更高的优先级）。我们无法（合理地）确定。

死胡同？不——为什么不尝试两种方式看看结果呢？

因为现在我们删除了这一行

op left LANGLE RANGLE;

首先，我们必须定义 LANGLE/RANGLE，其优先级高于 PLUS 或 MINUS。

precedence
  op left MINUS PLUS;
  rs shift LANGLE expr(PLUS MINUS) expr;
  rs shift RANGLE expr(PLUS MINUS) expr;
end

顺序**是**优先级，而且由于我们想精确地解决 xANGLE 与 PLUS/MINUS 的问题，我们必须给出更精确的定义。这两个添加的行意味着：

在归约/移位冲突时
执行移位
如果传入符号是 LANGLE（最后一行是 RANGLE）
并且即将被归约的表达式包含 PLUS 或 MINUS 运算符
并且它与即将被移位的表达式冲突。

好的，所以我们知道如何精确地选择冲突以赋予它们确切的顺序。第二部分是类似的：

rs try LANGLE expr(LANGLE RANGLE) expr;
rs try RANGLE expr(LANGLE RANGLE) expr;

只有在这里我们“尝试”（分支）。因为我们依赖输入，对于这种情况

$ 7<2
The outcome: 28
The parse layout: (7 < 2)

$ 7<2>
The outcome: 1
The parse layout: (7[2])

它奏效了。但有时却不然。

$ 7<2>1
There were errors while parsing.
Ambiguous parsing.

歧义再次困扰

发生了什么？通过添加“try”指令，我们并没有真正解决歧义，而是将解决方案从语法推到了输入。结果是我们得到了两个而不是一个解析树。一些语言在输入时带有约束，但这不是我们的情况——我们必须手动添加约束。

考虑最后一个例子——“7<2>1”。它可以被解析为“(7<2)>1”或（错误地）解析为“7<(2>1)”。用约束的术语来说，这意味着我们不希望在右分支中看到位移。

之前我们有这样的位移规则

e1:expr LANGLE e2:expr
e1:expr RANGLE e2:expr

添加约束后

e1:expr LANGLE e2:expr #LANGLE #RANGLE 
e1:expr RANGLE e2:expr #LANGLE #RANGLE

使用井号（#）我们禁止给定的运算符出现在给定的位置（这里是：右表达式）。由于“operator”术语对 NLT 来说是未知的（它本身不是一个符号——尽管它可以重用相同的名称），我们必须标记（装饰）表达式。

e1:expr ^LANGLE e2:expr #LANGLE #RANGLE 
e1:expr ^RANGLE e2:expr #LANGLE #RANGLE

重音符（^）表示“将此符号用作运算符/装饰”。

以类似的方式，我们遍历位索引的两个表达式——“expr<expr>”——最终得到

expr -> e1:expr MINUS e2:expr 
        { pair(e1.Item1 - e2.Item1, "("+e1.Item2+" - "+e2.Item2+")") }
      | e1:expr PLUS e2:expr 
        { pair(e1.Item1 + e2.Item1, "("+e1.Item2+" + "+e2.Item2+")") }
      | e1:expr ^LANGLE e2:expr #LANGLE #RANGLE 
        { pair(e1.Item1 << e2.Item1, "("+e1.Item2+" < "+e2.Item2+")") }
      | e1:expr ^RANGLE e2:expr #LANGLE #RANGLE 
        { pair(e1.Item1 >> e2.Item1, "("+e1.Item2+" > "+e2.Item2+")") }
      | e1:expr #LANGLE #RANGLE LANGLE e2:expr #LANGLE RANGLE 
        { pair((e1.Item1 & (1 << e2.Item1)) >> e2.Item1, "("+e1.Item2+"["+e2.Item2+"])") }
      | n:NUM 
        { pair(n, n) }
      ;

运行它，然后

$ 1<2>3
The outcome: 0
The parse layout: ((1 < 2) > 3)

$ 1<7<2>
The outcome: 2
The parse layout: (1 < (7[2]))

完成！

在您的项目中使用 NLT

你看到了什么你喜欢的吗？我不能保证 NLT 是你解析问题的万能药，它更像是一个实验项目（我根据需要添加功能），但可以试试——也许它能满足你的需求。我很乐意看到。

为什么要重复造轮子？

我是否搜索得足够多？我这样说——即使我错过了市面上一些非常扎实的、类似 YACC 的 C# 解析器（我会感到惊讶），我也学到了很多。我不仅可以使用这些工具，而且对它们的内部工作原理（从词法分析器内部开始）有了很好的了解，所以这并不是浪费时间。现在唯一缺失的一块是构建我**自己**的编译器，但那是另一个故事了…

参考文献

Coursera Alex Aiken 教授的“编译器”在线课程，
Dick Grune 和 Ceriel J.H. Jacobs 的“Parsing Techniques”（1990），
Alfred V. Aho 和 Jeffrey D. Ullman 的“The Theory of Parsing, Translation, and Compiling (vol.1)”（1972）。

资源

http://skila.pl/ — 部分与 NLT 开发相关的博客，
https://sourceforge.net/projects/naivelangtools/ — NLT 仓库。