Week 4 - Parser 1¶

我们在前面一章知道了编译器前端的大致组成部分，并且学习了词法分析器的相关内容，我们接下来将学习语法分析器（Parser）相关的内容。首先，我们要有一个大致的印象，语法分析器到底是用来干嘛的。语法分析器会接收词法分析器传进来的词法符号流 (Token Stream)，然后按照预先设定好的语法规则将一连串的词法符号解析成有结构的语法树（如果无法解析成功，就意味着输入程序不符合语法规则，存在语法错误），以便后续的分析。

什么是 Parser

Parser 接受来自 Lexer 的 Token Stream，并把它转化成一个树。

这个树叫作 Parse Tree，"转化" 的规则就是 语法 "Grammar"。

Recap: Context-Free Grammar (CFG)¶

我们用上下文无关文法 (Context-Free Grammar) 来描述语法规则（请注意，在形式语言和编译技术的上下文中，语法和文法两个词是同一个意思）。

CFG 是一种用以描述结构化语言语法的形式语言。它和我们上一章说的正则表达式类似（都是形式语言）：正则表达式是用来描述 词法规则 的语言（程序中的词法单元应该长什么样子），上下文无关文法是用来描述更高一级的 语法规则 的（具有合法结构的程序应该长什么样子）。ANTLR 在描述语法规则的时候用的就是上下文无关文法。

为什么说 CFG 比 Regular Expression 更高级

CFG 能够描述 Regular Expression 所不能描述的一些情形，例如递归、嵌套结构。经典的例子为：成对括号 ()。

解析 CFG 表示的语言（我们称之为上下文无关语言）一般使用的是 Pushdown Automaton (下推自动机)，它比解析 Regular Expression 表示的正则语言所使用的 Finite Automaton 多了一个栈，所以它能有效处理递归嵌套等结构。

实际上，Finite Automaton 是 Pushdown Automaton 的一个子集, 感兴趣的可以看：Wikipedia - Automata theory。

CFG 有两个重要的组成部分： 终结符(Terminal) 和 非终结符(Nonterminal)。

简单来说，Terminal 是 Lexer 直接"递上来"的东西，是上下文无关文法中的最基础单元，它没有办法再被分割；而 Nonterminal 则是 "Parser 通过分析 Lexer 传递的词法符号流合成出来" 的东西。Parser 所遵从的 "合成规则" 即是 Productions (产生式)，它描述了如何从 Terminals/Nonterminals 合成一个 Nonterminal。或者，反过来说，一条产生式描述一个 Nonterminal 能够产生哪些 Terminals/Nonterminals（所以这些合成规则被叫做“产生”式）。

Recap: Productions

在理论课上，我们使用如下格式来描述一个 Production: head -> body。

其中，head 一定是 Nonterminal；body 包含 0 或更多个 Nonterminal/Terminal。

在 ANTLR 中定义 CFG¶

我们可以开始在 ANTLR 中定义语法：

grammar Calc1;

expr    : expr ADD expr
        | expr SUB expr
        | factor
        ;

factor  : INT
        ;

INT : [0-9]+ ;
ADD : '+' ;
SUB : '-' ;

WS  : [ \t\r\n]+ -> skip ;

在 ANTLR 中，我们习惯将 Terminal 称为 Token，将 Nonterminal 称为 Rule。

它们都遵循一个相同的格式：名字、冒号、其内容规则、最后以分号结束；一个 Token/Rule 可以拥有许多条具体的规则。

在 ANTLR 中，我们用首字母是否大小写来区分 Token 和 Rule，前者要求首字母必须大写，后者要求首字母必须小写。额外的，ANTLR 不要求 Parser Rules 一定先于/后于 Lexer Rules，它们可以混合在一起。

上述的 Calc1 语法定义包括：

由大写字母开头 的 4 种 Terminals
由小写字母开头 的 2 种 Nonterminals
4 条 Productions，ANTLR 称之为 Parser Rule

Parser Rule¶

一条最基本的 Parser Rule 长这样：

factor : INT ;

格式为：ruleName : Alternatives ;。

一个 Nonterminal 可以有多条 Productions，它们使用 | 分隔，使用 ; 标记结束：

expr    : expr ADD expr
        | expr SUB expr
        | factor
        ;

Rule Elements¶

在每条 Alternative 中，可以包含 Token (大写字母开头)、rule (小写字母开头)、或者是 'literal'

在 Parser Rule 中，我们可以直接使用字符串常量。ANTLR 会自动创建一条 Lexer Rule 并引用它（你可以在 .tokens 文件中看到它）。

例如，我们可以省略 ADD: '+'，而直接在 Parser Rule 中写改字符串常量 '+' ：

expr    : expr '+' expr
        | expr '-' expr
        ;

Subrules¶

一条 Alternative 里面可以包含一个 Alternative block，这种情况称之为 Subrules。Subrules 就类似于单独创建了一条匿名的 Rule。

Subrules 有四种语法，非常类似正则表达式：

(x | y | z) : 匹配任意 Alternative 一次。
(x | y | z)? : 匹配任意 Alternative 一次或零次。
(x | y | z)* : 匹配任意 Alternative 零次或更多次。
(x | y | z)+ : 匹配任意 Alternative 一次或更多次。

Subrule 示例：`(...)*` 零次或更多次¶

例如下面这条规则定义：

expr: NUMBER ('+' NUMBER)*;

这里的 ('+' NUMBER)* 就是一个 Subrule。它表示 ' + ' NUMBER 这个整体可以连续出现 0 次或更多次。

✅ 匹配示例¶

7
- (匹配 0 次 ('+' NUMBER))
7 + 2
- (匹配 1 次)
7 + 2 + 5
- (匹配 2 次)
7 + 2 + 5 + 8
- (匹配 3 次)

❌ 不匹配示例¶

+ 2
- (因为规则必须以 NUMBER 开头)
7 +
- (因为 + 后面缺少 NUMBER)

使用 ANTLR Parser¶

我们如何使用ANTLR生成的语法分析器呢，我们可以简单回顾一下 Week 1 - Intro 给出的示例程序的这几行：

    // 把要解析的字符串喂给 ANTLR
    CharStream input = CharStreams.fromString("1 + 2");
    // 词法分析器
    Calc1Lexer lexer = new Calc1Lexer(input);
    // Token 流
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    // 语法分析器
    Calc1Parser parser = new Calc1Parser(tokens);
    // 从规则 'expression' 开始解析
    ParseTree tree = parser.expr();
    // 把树打印出来看看
    System.out.println(tree.toStringTree(parser));

我们在新建 Calc1Parser 对象时，把前面的 CommonTokenStream 给传进去；然后调用 parser.expr() 方法，这表示令 Parser 从 Token Stream 中为我们 构建一棵根节点为 expr 的 ParseTree。

ANTLR 创建出来的 Parser 会给每一个 Parser Rule 都生成一个对应的方法，方法名称就是对应的语法规则的名称。调用这个方法表示就从这条语法规则作为根节点开始解析。

Start Rule 和 EOF¶

我们将第一次调用 ANTLR 时指定的 Rule 称为 Start Rule，即 ParseTree tree = parser.expr() 中的 expr。expr 这个 Nonterminal 也是我们希望构建的 Parse Tree 的根节点。但是请注意：Start Rule 并不会消耗掉 TokenStream 中所有的 Token，它只会消耗掉构建这颗 Parse Tree 所需要的所有 Token。

这就是为什么我们运行上述程序的时候会报错：line 1:5 no viable alternative at input '<EOF>'：因为 Parser 在消耗完所有 Token 后，Token Stream 中还剩下一个特殊的 Token <EOF>，它表示 Token Stream 的结束；Parser 发现没有任何一条 Rule 适用于 <EOF> 这个 Token，所以会提示以上的报错。

通常来说，我们希望 Parser 完整地处理整个源文件，这时候我们就可以定义一个更高级的 Start Rule，并包含 <EOF> 这个 Token：

root: expr <EOF>;

expr : ...

然后，在 Java 中使用 ParseTree tree = parser.root(); 解析完整个 TokenStream.

如何快速的查看一颗语法树¶

如果我们想要快速的查看一串字符能不能被解析为正确的语法树，可以先照着上一章的教程令 Antlr 先将那一大堆文件给生成出来，再进入我们的g4文件当中，选中我们要检查的语法规则，然后右击，在出现的菜单中选择 Test Rule (规则名) (如下图所示)

接着在下面出现的输入框中输入待测试的字符串，你就可以看到语法树了。

练习¶

你需要扩展我们上述提到的 Calc1 语法，使其除了加减运算之外，还能支持乘除运算，以及小括号，同时自己写一个小程序测试一下下面这个输出。

(1 + 2 * 2 / 3)