ANTLR 入门篇 1

本文最后更新于 2021年4月4日 晚上

入门 ANTLR 系列文章第 1 篇: 环境搭建和总体介绍.

系列文章的主要目的是:

  1. 介绍 Language Application 的实现原理.
  2. 介绍 ANTLR 工具的使用.
  3. 看懂/实现简单的 OC to Swift Translator.

开发环境设置

  1. 保证本机上安装有 JDK, 版本不低于 1.8.

  2. 在官网下载 ANTLR 的 jar 包后, 放到 /usr/local/lib/ 目录下, 并且在 .zshrc(或 .bashrc) 中添加如下内容:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # 根据自己的实际情况添加 JAVA_HOME, 由于我安装的是 JDK 12, 所以添加的 12 的 Home
    export JAVA_HOME=/Library/Java/JavaVirtualMachines/jdk-12.0.1.jdk/Contents/Home
    # 将 antlr 的 jar 包加入到 CLASSPATH 中
    export CLASSPATH=".:/usr/local/lib/antlr-4.8-complete.jar:$CLASSPATH"

    # antlr4 主程序
    alias antlr4='java -jar /usr/local/lib/antlr-4.8-complete.jar'
    # antlr4 测试程序, 用于后续语法文件的测试
    alias grun='java org.antlr.v4.runtime.misc.TestRig'

  3. 开始开发.

ANTLR 基础

ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files.

ANTLR 用于生成 Language Applications 核心支持功能, 包括 lexer 和 parser.(只需定义 Grammar 文件(.g4), 再通过命令行生成相关文件, 并支持多种语言 Target, 包括 Java, C#, Swift, Python 等)

术语和定义

  • Language: 由一组合法的 sentence 组成, sentence 由 phrase 组成, phrase 由 subphrase 和 vocabulary symbol 组成.

  • Interpreter(解释器): 如果一个应用是用来”计算”或”执行” sentence 的, 我们就说它是 interpreter. 比如计算器, 配置文件读取器, python 解释器等.

  • Translator(翻译器): 如果应用是把 sentence 从一门语言转换为另外一门, 则称这个应用是 translator. 比如 Java to C# 转换器, 或者是编译器(compiler)等.

  • Lexer: 用于将字符流进行预处理, 生成 token 流.

  • Parser(或称 syntax analyzer): 指用于识别 language 的程序, 因为 Language APP 正常工作的前提是它们可以识别所针对语言的所有合法 sentence, phrase, subphrase.

  • ANTLR Grammar: 用于指定语言的 syntax 的一系列 rule 文本. syntax 就是语言的规则, 即语法. ANTLR 即用来自动生成另外一个程序的程序, 比如生成 parser 程序和 lexer 程序. (Grammer 语法又称为 ANTLR meta-language)

github 上有很多 grammar 实现文件.

语言识别过程

Lexers process characters and pass tokens to the parser, which in turn checks syntax and creates a parse tree.

By operating off parse trees, multiple applications that need to recognize the same language can reuse a single parser.

所以语言的 parsing (语言识别)过程可以分成两个阶段:

  1. 字符流的 token 化阶段: 将 char 组合为 word 或 symbol(或称 token, 即具有语法意义的符号), 这个过程称为 lexical analysis 或 tokenizing, 执行这一过程的程序称为 lexer.
  2. 生成 parse tree 阶段: 将第一阶段生成的 token 送入 parser, 用于识别 sentence 的结构. 结果是生成一个 parse tree. 这个阶段的输出的 parse tree 可以在后续处理过程中重用.

连接 lexer 和 parser 的”管道” 就是 TokenStream.

主要学习内容

  1. 学会如何定义 grammer rule.
  2. 理解语法的二义性问题, 以及 ANTLR 中是如何处理的.
  3. 学习如何通过 Parse tree 构建 Language Application.

下面通过一个入门项目看 ANTLR 的整体功能.

入门项目: 数组转换

下面介绍一个入门 Tranlator 项目: 将普通 JAVA 数组转换为 Unicode 字符串.

定义 grammar 并生成核心功能文件

  1. 写 grammar 文件, 文件名为 ArrayInit.g4:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // Grammar 文件必须以 grammar header 开头, 且名称必须和文件名匹配.
    grammar ArrayInit;

    // grammar rule 定义, 这个 rule 的名字是 init
    init : '{' value (',' value)* '}' ;

    // 另外一个 grammar rule 定义, 名为 value
    value : init | INT ;

    // parser rules start with lowercase letters, lexer rules with uppercase

    // 定义名为 INT 的 lexical token rule, 表示一个或多个数字.
    INT : [0-9]+ ;
    // 定义空白符号 token rule, 遇到空白符号就扔掉
    WS : [ \t\r\n]+ -> skip ;

  2. 执行如下命令生成核心功能文件:

    1
    antlr4 ArrayInit.g4

    默认生成的是以 Java 实现的 lexer/parser, 可以通过 -Dlanguage 指定语言, 包括 C#/Swift 等, 详见官方文档.

    其中:

    • ArrayInitParser.java: 包含 parser 类的定义, 用于识别特定的语法, 这里是我们定义的数组.
    • ArrayInitLexer.java: 包含 lexer 的定义.
    • ArrayInit.tokens: token 列表
    • ArrayInitListener.java, ArrayInitBaseListener.java: 提供对外的接口, 这样我们可以在其中实现转换.

  3. 执行测试: grun ArrayInit init -tokens, 回车后在第一行输入 {99, 3, 451}, 然后使用 ctrl+D 输入 EOF, 此时输出:

    1
    2
    3
    4
    5
    6
    7
    8
    [@0,0:0='{',<'{'>,1:0]
    [@1,1:2='99',<INT>,1:1]
    [@2,3:3=',',<','>,1:3]
    [@3,5:5='3',<INT>,1:5]
    [@4,6:6=',',<','>,1:6]
    [@5,8:10='451',<INT>,1:8]
    [@6,11:11='}',<'}'>,1:11]
    [@7,13:12='<EOF>',<EOF>,2:0]

    可以看到, 所有的 token 都被正确识别了.

    再使用 grun ArrayInit init -tree 生成 parse tree(结尾同样是 EOF):

    1
    (init { (value 99) , (value 3) , (value 451) })

    -tree 参数表示使用 LISP 形式的 text 输出 parse tree.

    此外还可以使用 -gui 参数输出可视化的 parse tree, 比如输入嵌套数组: {1,{2,3},4}:

    其中树根是刚才定义的 init 规则, 在大括号中包含三个 value, 其中第二个 value 又是一个 init 规则匹配的值, 其中有两个 value 包含在大括号中.

下面我们将这些文件先集成到一个工程中, 并验证是否可以正常执行.

简单集成

写如下 Java 文件, 名为 Test.java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// import ANTLR's runtime libraries
import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.*;

public class Test {
    public static void main(String[] args) throws Exception {
        // 1. 创建一个 CharStream 从标准输入中读取数据
        ANTLRInputStream input = new ANTLRInputStream(System.in);

        // 2. 创建一个用于处理输入字符流的 lexer.
        ArrayInitLexer lexer = new ArrayInitLexer(input);

        // 3. 创建一个 token buffer, 用于接收 lexer 生成的 token.
        CommonTokenStream tokens = new CommonTokenStream(lexer);

        // 4. 创建一个从 token buffer 中取 tokens 并进行处理的 parser
        ArrayInitParser parser = new ArrayInitParser(tokens);

        // 5. 从 init rule 开始处理(之前在 grammar 中定义的 rule)
        ParseTree tree = parser.init();

        // 输出以字符串形式表示的结果 parse tree
        System.out.println(tree.toStringTree(parser));
    }
}

使用 javac ArrayInit*.java Test.java 编译后, 使用 java Test 运行, 输入 {1, 2, 然后 EOF, 正常报错, 输入 {1, 2, 3}, 正常输入结果.

实现数组转换 Translator

本步骤的目标是将 java 中类似 {1, 2, 3} 这样的数组转换为 unicode 字符串表示, 比如 “\u0063\u0003\u01c3”.

要进行转换, 就需要从 parse tree 中获取数据. ANTLR 中提供了两种对 parse tree 的遍历方式:

  • 使用 Listener 自动遍历
  • 使用 Visitor 手动遍历

目前我们选择第一种方式, 即 Listener 方式遍历, Listener 默认进行的是深度优先遍历(可以将 parse tree 看作是一个有向无循环图).

首先针对一个 {99, 3, 451} 这样的输入, 我们可以有如下转换对照表:

转换前 转换后
{ "
} "
整数数字 对应的 Unicode字符串(以 \u 开头, 后面跟 4 位 16 进制数)

首先实现一个 ShortToUnicodeString 类, 它是 Listener, 在其中我们可以进行实际的转换操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/// 执行 Array 转换为字符串的 listener.
public class ShortToUnicodeString extends ArrayInitBaseListener {

    /// 在 init rule 的入口 将 { 转换为 " 打印出来
    @Override
    public void enterInit(ArrayInitParser.InitContext ctx) {
        System.out.print('"');
    }

    /// 在 init rule 的出口将 } 转换为 " 打印出来
    @Override
    public void exitInit(ArrayInitParser.InitContext ctx) {
        System.out.print('"');
    }

    /// 在 value 规则的入口将数值转换为 4 位 16 进制表示
    @Override
    public void enterValue(ArrayInitParser.ValueContext ctx) {
        // 这里假设没有嵌套数组的情况, 可以直接在当前 context 中获取数值
        int value = Integer.valueOf(ctx.INT().getText());
        System.out.printf("\\u%04x", value);
    }
}

新建一个 Translate.java 文件, 在其中写 main 函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.*;

public class Translate {
    public static void main(String[] args) throws Exception {
        // 1. 创建一个 CharStream 从标准输入中读取数据
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        // 2. 创建一个用于处理输入字符流的 lexer.
        ArrayInitLexer lexer = new ArrayInitLexer(input);
        // 3. 创建一个 token buffer, 用于接收 lexer 生成的 token.
        CommonTokenStream tokens = new CommonTokenStream(lexer); 
        // create a parser that feeds off the tokens buffer
        // 4. 创建一个从 token buffer 中取 tokens 并进行处理的 parser
        ArrayInitParser parser = new ArrayInitParser(tokens);
        // 从 init 规则开始处理
        ParseTree tree = parser.init(); 

        // 使用内置的 ParseTreeWalker 遍历 parse tree
        ParseTreeWalker walker = new ParseTreeWalker();

        // 传入自定义的 listener, 以及 parse tree, 这样在遍历的时候 listener 就可以得到通知了
        walker.walk(new ShortToUnicodeString(), tree);

        // 在末尾打印一个回车
        System.out.println();
    }
}

执行 javac ArrayInit*.java Translate.java 编译, 然后 java Translate 运行. 当输入 {1, 2, 345}, 结果输出 "\u0001\u0002\u0159", 符合预期.

生成其他语言下的 Target: 以 C# 和 Swift 为例

上面都是生成 Java 下的实现, 不过实际官方提供了多种语言的生成支持, 只需要指定 -Dlanguage 参数即可.

Swift Target

1
antlr4 -Dlanguage=Swift MyGrammar.g4

有个坑:

Grammar 中不能使用 init 等 Swift 关键字来命名规则, 否则生成会出错.

Swift 需要依赖 Antlr4 Framework, 需要克隆 github 上的 antlr 仓库到本地才能生成包含这个库的工程, 在克隆的 antlr 仓库根目录下执行如下操作:

  1. brew install maven 安装 maven(如果没有).
  2. 在 antlr 仓库的根目录执行 mvn install, 如果要忽略测试, 可以使用 mvn install -DskipTests.
  3. 再到 仓库根目录/runtime/Swift 目录下执行 python boot.py --gen-xcodeproj 即可生成相应工程.

将生成的工程拖入到新建的 Xcode 工程中即可. 此外, 由于生成的 Antlr4 Framework 是动态链接的, 如果想要把你的命令行应用打包为单一可执行文件, 需要把 Antlr4 Framework 工程的 Mach-O 类型修改为 static.

Swift 的 main 文件中, 可以通过 CommandLine.arguments 获取传入的参数.

C# Target

  1. 创建一个 dotnet 新工程, 可以是命令行程序:

    1
    dotnet new console -o 程序目录

  2. 在程序目录中新建一个文件夹, 用于存放语法文件, 进入该目录后, 通过下述命令生成 ANTLR 相关代码:

    1
    antlr4 -Dlanguage=CSharp <Grammar文件名>.g4

  3. 引入下面这个包:

    1
    dotnet add package Antlr4.Runtime.Standard --version 4.8.0

  4. 开始开发.

其他语言的支持也可以参考官方文档.

两种 parse tree 遍历接口

ANTLR 中提供了如下两种针对 parse tree 的遍历方法, 一种是 Listener, 一种是 Visitor.

Listener

ANTLR runtime (任意语言)中提供了一个接口 ParseTreeWalker, 用于在遍历 parse tree 时调用 Listener 中的相关方法. 编写语言应用时, 可以创建 ParseTreeWalker 接口的自定义实现.

使用 Listener 的好处是一切都是自动的, 默认进行深度优先遍历, 不用编写针对 parse tree 的自定义 walker.

Visitor

如果需要控制遍历, 显式调用方法来遍历 children, 则需要使用 Visitor 模式, 这样的方式下, 遍历就需要进行手动控制而非自动进行了. 如果要生成 Visitor 基础接口, 可以使用 -visitor 选项.

可以实现自定义的 Visitor, 然后调用 visit() 方法进行遍历.

总结

至此, ANTLR 的基本概念已经有了一个总体了解, 并且也进行了开发环境的搭建和简单例子的实现.

后面我们再通过几个更复杂的例子来展示 ANTLR 的功能全貌, 并了解如何实现一个语言程序(Language Application), 详见下一篇文章.

ANTLR 入门篇 1
https://blog.rayy.top/2020/06/21/2020-06-21-antlr-c1-to-c4/
作者
貘鸣
发布于
2020年6月21日
许可协议