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 有四种语法，非常类似正则表达式：

1. (x | y | z) : 匹配任意 Alternative 一次。
2. (x | y | z)? : 匹配任意 Alternative 一次或零次。
3. (x | y | z)* : 匹配任意 Alternative 零次或更多次。
4. (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.

快速查看语法树

大家应该已经对下面这个命令非常熟悉了：

make

毕竟从前面的 Lab 开始，我们就一直在用它生成 Lexer 和 Parser。

但 make 本身其实并不会什么 ANTLR 魔法。它只是按照项目根目录中的 Makefile，帮我们执行一些已经写好的命令。

make 到底做了什么？

我们一直在使用的 Makefile 中，真正负责生成 ANTLR 代码的核心其实是：

Makefile

java -jar $(ANTLR_JAR) \
    -visitor \
    -o $(OUTPUT_DIR)/$(basename $<) \
    -package generated.$(basename $<) \
    $<

其中，我们已经指定了 ANTLR 的位置：

ANTLR_JAR := libs/antlr-4.13.2-complete.jar

所以，对于一个名为 Calc1.g4 的 Grammar，上面的 Makefile 规则最终执行的其实就是类似这样的命令：

java -jar libs/antlr-4.13.2-complete.jar \
    -visitor \
    -o src/main/java/generated/Calc1 \
    -package generated.Calc1 \
    Calc1.g4

所以，make 其实只是一个很勤快的「命令代跑员」

它负责找到我们的 .g4 文件，然后帮我们调用：

antlr-4.13.2-complete.jar

来生成对应的 Java Lexer、Parser 和 Visitor。

真正干活的，其实一直都是 ANTLR。

---

其实我们之前已经打印过语法树了

在前面的 Week 1 - Intro 中，我们已经使用过下面这行代码来查看 Parser 生成的 Parse Tree：

System.out.println(tree.toStringTree(parser));

其中，tree 是从某条 Parser Rule 开始解析后得到的 ParseTree，而：

tree.toStringTree(parser)

会将这棵 Parse Tree 转换成一种便于在终端中查看的括号表示形式。

例如，对于输入：

1 + 2

可能得到类似下面的输出：

(expr (expr 1) + (expr 2))

回顾一下，当时为了得到这棵树，我们实际上需要自己完成整个解析流程：

Input
  ↓
CharStream
  ↓
Lexer
  ↓
Token Stream
  ↓
Parser
  ↓
ParseTree
  ↓
toStringTree(...)

也就是说，我们之前是在 Main.java 中手动创建 Lexer、Token Stream 和 Parser，最后再把得到的 Parse Tree 打印出来。

而 antlr-4.13.2-complete.jar 中其实已经帮我们准备好了一个现成的测试工具：

org.antlr.v4.gui.TestRig

它可以帮我们快速完成类似的工作。

TestRig 并没有什么神秘的地方

我们之前是在 Main.java 中自己创建 Lexer、Token Stream 和 Parser，然后调用：

tree.toStringTree(parser)

而 TestRig 只是把这套测试流程提前帮我们写好了。

所以如果只是想快速看看 Grammar 把一段输入解析成了什么结构，就没有必要每次都专门修改 Main.java。

---

使用 -tree 快速查看 Parse Tree

假设我们现在有一个：

Calc1.g4

它生成的 Java package 为：

generated.Calc1

并且我们希望从下面这条 Parser Rule 开始解析：

expr
    : ...
    ;

首先像往常一样运行：

make

并完成 Java 源码的编译。

随后可以直接执行：

echo '1 + 2 * 3' | \
java -cp "bin:libs/antlr-4.13.2-complete.jar" \
    org.antlr.v4.gui.TestRig \
    generated.Calc1.Calc1 \
    expr \
    -tree

ANTLR 会直接在终端中打印 Parse Tree，例如：

(expr (expr 1) + (expr 2) * (expr 3))

具体输出的树结构取决于你所编写的 Grammar。

虽然这种形式看起来不像我们平时画在纸上的树，但括号本身就在表达节点之间的层次关系。

例如，可以把：

(expr (expr 1) + (expr (expr 2) * (expr 3)))

稍微展开来看：

(expr
    (expr 1)
    +
    (expr
        (expr 2)
        *
        (expr 3)
    )
)

这样就比较容易观察各个节点之间的父子关系了。

---

这条命令到底是什么意思？

看起来很长，但真正需要关注的其实只有几个部分：

参数	含义
bin:libs/antlr-4.13.2-complete.jar	Java 运行时搜索 .class 文件和 ANTLR 相关类的位置
org.antlr.v4.gui.TestRig	ANTLR 自带的 Grammar 测试工具
generated.Calc1.Calc1	要使用的 Grammar
expr	从哪一条 Parser Rule 开始解析
-tree	在终端中打印 Parse Tree

其中最经常需要修改的其实就是：

generated.Calc1.Calc1
expr

例如，如果你的 Grammar 为：

grammar SPL;

生成的 Java package 为：

generated.SPL

并且入口 Parser Rule 为：

compUnit
    : ...
    ;

那么就可以使用：

echo '...' | \
java -cp "bin:libs/antlr-4.13.2-complete.jar" \
    org.antlr.v4.gui.TestRig \
    generated.SPL.SPL \
    compUnit \
    -tree

调 Parser 时，多看看树

当你不确定自己的 Grammar 是否按照预期工作时，-tree 往往是一个非常方便的调试手段。

特别是遇到下面这些情况时：

• 一段输入到底有没有被正确解析；
• 某条 Parser Rule 最终匹配成了什么结构；
• 运算符的优先级和结合性是否符合预期；
• 为什么一个表达式的解析结果和自己想象的不一样；
• 修改 Grammar 前后的 Parse Tree 有什么变化。

与其盯着 .g4 文件反复脑补，不如直接看看 ANTLR 实际生成的 Parse Tree。

---

如果想看真正“画出来”的语法树

TestRig 还提供了：

-gui

选项，可以使用图形界面的方式直接查看 Parse Tree。

例如：

echo '1 + 2 * 3' | \
java -cp "bin:libs/antlr-4.13.2-complete.jar" \
    org.antlr.v4.gui.TestRig \
    generated.Calc1.Calc1 \
    expr \
    -gui

如果图形环境配置正确，ANTLR 会弹出一个窗口，将 Parse Tree 直接画出来。

不过，我们通常是通过 SSH 或 VS Code Remote-SSH 连接到虚拟机进行开发的。

此时 ANTLR 实际运行在远程虚拟机中，而远程终端默认情况下不一定具备可用的图形显示环境，因此 -gui 可能无法直接弹出窗口。

感兴趣的话，可以自己探索一下

远程 Linux 环境并不是完全不能显示 GUI。

如果感兴趣，可以进一步了解：

• X11 Forwarding
• DISPLAY 环境变量
• 远程 Linux 图形程序如何将窗口显示到本地计算机

这些内容并不是本课程的要求，也不会影响 Project 的完成。

在本课程中，直接使用：

-tree

就已经足够完成日常的 Parser 调试工作。

---

但是，首先你得有一棵树

-tree 和 -gui 展示的都是 Parse Tree，因此首先需要有 Parser。

如果你的 .g4 文件是：

lexer grammar ExampleLexer;

也就是说目前只有 Lexer，那么它只能产生 Token Stream，并不会产生 Parse Tree。

没有 Parser，自然也就没有语法树可以看。

练习

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

(1 + 2 * 2 / 3)