语法解析及Antlr

stat()、assign()、expr()等方法调用所形成的调用栈能与语法分析树的内部节点一一对应。match()的调用对应树的叶子，而assign()方法直接顺序读取输入字符，而不用做任何选择。相比之下，stat()方法要复杂一些，因为在解析时，它需要向前看一些字符才能确认走哪个代码分支，有时甚至要读取完所有输入才能得出预测结果。

**2.1.2 ALL(*)解析器**

ANTLR从4.0开始生成的是ALL(*)解析器，其中A是自适应（Adaptive）的意思。对传统的LL(*)解析器有很大的改进，ANTLR是目前唯一可以生成ALL(*)解析器的工具。

2.2 语法解析树

在ANTLR4中已经不再提供生成AST的功能（在ANTLR3中可以通过Options指定output=AST来生成AST），而是生成了分析树（Parse Tree）。

2.3 使用方法

2.3.1 使用流程

http://www.antlr.org/

自定义文法--->词法分析器（Lexical）------>语法分析器(Parse)—→Grammer

draw.io evaluation version

Lexical

文法文件

Parse

处理后的文件

输入

g4文件

Parse

输出

antlr

自定义词法分析器 (g4后缀)文件
用工具生成Java文件
继承xxBaseVisitor类实现自己的Visitor

在整个Antlr的使用过程中，最重要的就是编写规则文件。

规则文件的编写：

Grammer文件：

grammar Cal;

prog: stat+; //一个程序由至少一条语句组成

/*为了以后的运算的方便性，我们需要给每一步规则打上标签，标签以”#”开头，出现在每一条规则的右边。打上标签后，antlr会为每一个规则都生成一个事件；在没有标签的情况下，每个规则会生成一个Context以及一个事件。如下述语句，如果没有标签，那么只会生成一个StatContext和一个visitStat方法。 */

stat: ID '=' expr ';' #Assign //变量赋值语句

| 'print' '(' expr ')' ';' #printExpr //输出语句

;

expr: expr op=('*'|'/') expr #MulDiv //表达式可以是表达式之间乘除

| expr op=('+'|'-') expr #AddSub //表达式可以是表达式之间加减

| NUM #NUM //表达式可以是一个数字

| ID #ID //表达式可以是一个变脸

| '(' expr ')' #parens //表达式可以被括号括起来

;

MUL:'*';

DIV:'/';

ADD:'+';

SUB:'-';

ID: [a-zA-Z][a-zA-Z0-9]*; //变量可以是数字和字母，但必须以字母开头

//负数必须要用"()"括起来

NUM: [0-9]+ //正整数

| '(' '-' [0-9]+ ')' //负整数

| [0-9]+'.'[0-9]+ //正浮点数

| '(' '-' [0-9]+'.'[0-9]+ ')' //负浮点数

;

WS: [ \t\r\n] -> skip; //跳过空格、制表符、回车、换行

生成命令：

编辑完 Antlr 文件后，我们在安装有 Antlr plugin 的 Intellij 上，可以通过右键语法规则对语法规则进行测试，并可以在配置生成中间代码的包名、路径等选项后，直接生成中间代码。

生成的文件说明：

Hello.tokens和HelloLexver.tokens为文法中用到的各种符号做了数字化编号,对于我们定义的每个 token，ANTLR 分配了一个 token 类型码并将这些值保存在 ArrayInit.tokens。因为这个文件的存在，当我们将较大规模的语法分割为各种小型的语法表达时，ANTLR 能够使同种 token 的类型码保持一致。
HelloLexer.java 包含专用的词法分析程序（lexer）类的定义
HelloParse.java 包含了专用于 ArrayInit 语法的解析器（parser）类的定义。
HelloVisitor 和 HelloBaseVisitor 分别是语法解析树的vistor的接口和类，用于遍历整个语法树。一般情况下，我们通过继承 HelloBaseVisitor 来实现自己对于语法树遍历的处理。
HelloListener和HelloBaseListener是用listen方式来遍历树的解析方法。

HelloParse说明：

ANTLR为每个子规则创建一个同名函数，因此可以方便地取到其子规则的context。即每个规则对应一个Context。

Context对象包含以下内容：

语法分析时生成

起始Token，终止Token
children：可以得到子语法规则中的内容。
异常信息：可以得到解析失败的信息。

查看语法解析树：

3 Listener 和 Visitor 机制

在ANTLR 4以前，有两种开发方式：一是将目标语言的代码直接硬编码到语法定义文件中，在生成分析器时会插入这些代码到生成文件中，这也是大多数语法分析器生成工具的做法。

在上边的语法判定与通道的例子中，就有将Java代码硬编码到语法定义的情况。将目标代码和语法定义耦合在了一起，当需要生成不同目标语言的分析器时，就需要维护多份语法定义文件，

‘增加了维护成本，同时在编写复杂逻辑时，由于IDE没有对目标语言的支持，开发和测试都很幸苦。另一种方式是让ANTLR生成语法分析树，然后写程序遍历语法树，对语法树的遍历是一个很复杂的工作。

ANTLR 4开始会生成监听器（Listener）与访问者（Visitor），将语法定义与目标代码完全的解耦。监听器可以被动的接受语法分析树遍历的事件，对于每一个语法节点，

都会生成进入enterSomeNodeName与退出exitSomeNodeName两个方法。访问者机制生成对语法节点的访问方法visitSomeNodeName，在访问方法中需要手动调用visit方法来对子节点进行遍历，

使用访问者模式可以控制语法树的遍历，略过某些的分枝。ANTLR默认只生成监听器，生成访问者类需要在生成时添加-visitor选项。

Visitor和Listener是antlr提供的两种树遍历机制。Listener是默认的机制，可以被antlr提供的遍历器对象调用；如果要用Visitor机制，在生成识别器时就需要显式说明

antlr4 -no-listener -visitor Calc.g4，并且必须显示的调用visitor方法遍历它们的子节点，在一个节点的子节点上如果忘记调用visit方法，就意味着那些子数没有得到访问

核心区别：两者各有优劣，Listener模式适合全局查找，默认是深度优先遍历，而Visitor模式适合指定某个节点作遍历。

listener默认是遍历每个节点，对于每个节点都有enter和exit事件。对于visitor则是需要自己手动用写代码去进行指定节点遍历。

3.1 Listener模式

示例如下

public class WlgsParseListener extends MerakDslBaseListener{
    private ParseTreeProperty<String> property = new ParseTreeProperty<>();

    @Override
    public void exitArithmeticBinary(MerakDslParser.ArithmeticBinaryContext ctx) {
        MerakDslParser.ExpressionContext right = ctx.right;
        MerakDslParser.ExpressionContext left = ctx.left;
        String formula = left.getText() +  ctx.operator.getText() + right.getText();
        property.put(ctx,formula);
        super.exitArithmeticBinary(ctx);
    }
}

Listener模式的exitXX方法的返回值都是空，在遍历过程所有有临时数据需要保存，可以存近一个自定义数据结构中或者使用antrl的ParseTreeProperty中或者自定义一个数据结果保存都是OK的。

3.2 Visitor模式

从上面可以看出，即使我们不使用super调用父类的同名方法，也不调用自定义baseListener中的其他方法，其实listen也是可以完成遍历的。因此listener是被动进行遍历的。

visitor不一样，是手动进行遍历，必须手动使用visit调用其他的visitor方法，或者使用super，父类中该方法是调用所有的子类visitor。

从以下源码可以看出，super.visitXX都是一样的，都是visit 参数Context的 Children。

@Override public T visitAssignment(MerakDslParser.AssignmentContext ctx) { return visitChildren(ctx); }
	/**
	 * {@inheritDoc}
	 *
	 * <p>The default implementation returns the result of calling
	 * {@link #visitChildren} on {@code ctx}.</p>
	 */
	@Override public T visitCaseWhen(MerakDslParser.CaseWhenContext ctx) { return visitChildren(ctx); }
	/**

整体流程就是，

visitProg(){

super.visitProg(ctx)  //visit children就是所有的stat.accept(visitor)
  stat.accept(visitor) ==> visitor.visitStat()
  visitStat(ctx){super.visitStat} // visitStat的child
  以此类推。。
}

Q:如果Prog下有多个stat，那么用super visit所有的children的结果如何合并为一个结果(该结果是visitStat的返回值)。

A: visitChildren源码可以看出，多个child的结果是，后续的结果会覆盖前面的结果，也就是visitProg的返回值就是最后一个visitStat的结果。

    public T visitChildren(RuleNode node) {
        T result = this.defaultResult();
        int n = node.getChildCount();

        for(int i = 0; i < n && this.shouldVisitNextChild(node, result); ++i) {
            ParseTree c = node.getChild(i);
            T childResult = c.accept(this);
            result = this.aggregateResult(result, childResult);
        }

        return result;
    }

比如对于(3*4)/2 ；方法visitParens，如果方法实现是使用super.visitParens，则会返回")"。 Parens的children数组元素有三个，（、exp、)；最后的“)”会覆盖前面两个。这个时候我们自定义visit的作用就体现出来了,一般对于四则运算的visitParens我们会重写如下

visit(ctx.expression());

重写的visitParens中，我们就手动指定了节点的访问。因此可以认为visitor模式就是主动遍历的模式。

接下来还需要明确下 Context的层级结构，比如

3.3 相关问题释疑

1 语法文件中的#意味着什么？和生成的Context结构如何对应？

#号的含义在上文语法文件说明部分已经解释了，没有#规则名对应一个Context，有#能以更细的分支来管理规则，#后面的别名对应着一个Context，也对应着一个访问方法。

2 大部分时候都是有children，到底什么节点下有children？

目前这个Expression的children下面没有数组，而是left 和right的属性。

因此猜测，凡是有 left = xx;有这种描述语句的时候都是没有数组的。这个时候不能使用 super.xxx进行遍历

3.9 实践问题

其他细节：因为字符串和null用+号拼接的时候，就相当于字符串 + “null”因此可能会出现 (null)的现象。有两种办法，一种在遍历括号节点的时候加判断，或者解析公式之前就加个校验，保证不出出现这种问题，

天璇V3Manager工程物理公式解析就是前端控件进行了校验，保证了不会出现这个问题。

if (ctx.expression() != null){ 
  return visitExpression(ctx.expression());             
} else{ 
  return Double.parseDouble(ctx.INT().getText());             
}

使用 Maven

Antlr4 提供了 Maven Plugin，可以通过配置来进行编译。语法文件 g4 放置在 src/main/antlr4 目录下即可，配置依赖的 antlr4 和 plugin 即可。生成 visitor 在 plugin 配置 visitor 参数为 true 即可。

注意：antlr4 的库版本要与 plugin 版本对应，antlr4 对生成文件用的版本与库本身的版本会进行对照，不匹配会报错。

...
<properties>
    <antlr4.version>4.7.2</antlr4.version>
</properties>

<dependencies>
    <dependency>
        <groupId>org.antlr</groupId>
        <artifactId>antlr4</artifactId>
        <version>${antlr4.version}</version>
    </dependency>
</dependencies>
...
<build>
    <plugins>
        <plugin>
            <groupId>org.antlr</groupId>
            <artifactId>antlr4-maven-plugin</artifactId>
            <version>${antlr4.version}</version>
            <configuration>
                <visitor>true</visitor>
            </configuration>
            <executions>
                <execution>
                    <id>antlr</id>
                    <goals>
                        <goal>antlr4</goal>
                    </goals>
                </execution>
            </executions>
        </plugin>
    </plugins>
</build>
...

4 规则命中策略

规则这么多，也许一个表达式能够命中多个规则分支，最终命中哪个是什么策略决定的。以下进行说明。

【TODO】

5 antlr的应用

一般的处理对象有：

SQL语句
算数表达式
编程语言的源文件

可以看出来其实编写grammar文件的过程其实就是对某种场景的抽象，定义一些基础的元素，然后Parse能够针对输入生成某种输入的树结构，然后遍历这种树结构，在遍历的过程中可以做一些处理，比如翻译。

note：

[各种语言的antlr解析] https://blog.csdn.net/xiyue_ruoxi/article/details/38925091

关于SQL的antlr解析

5.1 在Twitter中的应用

将查询参数解析成一个语法解析树

5.2 大数据产品中的应用

antlr在hibernate、presto以及SparkSQL中都是使用了的。

antlr在presto及SparkSQL中作用是相似的，都是就是生成了生成一个SQL语法解析树（一个未处理的逻辑执行计划）。

后续是对逻辑执行计划是进行了优化的。

也就是说presto和spark是从SQL到逻辑执行计划；天璇的逻辑执行计划是从查询参数构建出来，也就是手动完成了antlr的过程。

9 参考资料

[官网看 antlr 4 reference手册，权威必看] http://www.antlr.org/
[进阶] https://liangshuang.name/2017/08/20/antlr/
[基础] http://kyonhuang.top/ANTLR-learning-notes-1/
[visitor] https://dohkoos.gitbooks.io/antlr4-short-course/content/calculator-visitor.html
https://toutiao.io/posts/2a6f21/preview
[使用语法错误异常做补全] https://www.liangshuang.name/2017/08/20/antlr/
[各种语法文件] https://github.com/antlr/grammars-v4

语法解析及Antlr

1 语法解析

1.1 语法解析器

1.1.1 执行流程

1.1.2 语法树好处

1.1.3 解析方法LL与LR

1.1.4 抽象语法树（AST）

1.2 语法规则文件

2 Antlr

2.1 解析方法

2.1.1 递归下降语法分析器