antlr词法和语法分析

1. antlr介绍

Antlr4是一款强大的语法生成器工具,可用于读取、处理、执行和翻译结构化的文本或二进制文件。基本上是当前Java语言中使用最为广泛的语法生成器工具。

  • Twitter搜索使用antlr进行语法分析每天处理超过20亿次查询

  • Hadoop生态系统中的Hive、pig、数据仓库和分析系统所使用的语言都用到了antlr

  • Lex Machina将antlr用于分析法律文本

  • Oracle公司在sql开发者IDE和奇艺工具使用了Antlr

  • Hibernate对象-关系映射框架使用Antlr来处理HQL语言

1.1 基本概念

语法分析器parser是用来识别语言的程序,本身包含两个部分:词法分析器lexer和语法分析器parser。词法分析阶段主要解决的关键词以及各种标识符,例如INT、ID等;语法分析主要是基于词法分析的结果,构造一棵语法分析树。大致流程如下图所示:

因此,为了让词法分析和语法分析能够正常工作,在使用Antlr4的适合,需要定义语法grammar,这部分就是Antlr元语言。

  • lexer: 词法分析器,就是讲一个句子多个字符组装分成多个单词的规则

  • parser:语法分析器,对粉刺后的整个句子进行解析,可以对每个分词单元做出自定义的处理,从而实现自己的语法分析功能

g4文件:

g4文件是antlr生成词法解析规则和语法解析规则的基础。该文件是我们自己定义的,文件名后缀要是.g4。大致结构如下

1
2
3
4
5
6
7
8

grammar
comment(同java //)
options
import
tokens
@actionName
rule 我们需要关注的主要是grammar与rule

grammar:

grammar是规则文件的头,需要和文件名保持一致。当antlr生成词法语法解析的规则代码是,类型是根据grammar的名字来的

rule:

rule是antlr生成词法语法解析的接触,包括了lexer和parser,每条规则都是key:value的形式,以分号结尾

示例代码::

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
grammar Dsl;    //定义规则文件grammar
@header { //一种action,定义生成的词法语法解析文件的头,当使用java的时候,生成的类需要包名,可以在这里统一定义
package antlr;
}

//parsers
sta:(sql ender)*; //定义sta规则,里面包含了*(0个以上)个 sql ender组合规则
ender:';'; //定义ender规则,是一个分号
sql //定义sql规则,sql规则有两条分支:select/load
: SELECT ~(';')* as tableName //select语法规则,以lexer SELECT开头, 以as tableName 结尾,其中as 和tableName分别是两个parser
| LOAD format '.' path as tableName //load语法规则,大致就是 load json.'path' as table1,load语法里面含有format,path, as,tableName四种规则
; //sql规则结束符
as: AS; //定义as规则,其内容指向AS这个lexer
tableName: identifier; //tableName 规则,指向identifier规则
format: identifier; //format规则,也指向identifier规则
path: quotedIdentifier; //path,指向quotedIdentifier
identifier: IDENTIFIER | quotedIdentifier; //identifier,指向lexer IDENTIFIER 或者parser quotedIdentifier
quotedIdentifier: BACKQUOTED_IDENTIFIER; //quotedIdentifier,指向lexer BACKQUOTED_IDENTIFIER

//lexers antlr将某个句子进行分词的时候,分词单元就是如下的lexer
//keywords 定义一些关键字的lexer,忽略大小写
AS: [Aa][Ss];
LOAD: [Ll][Oo][Aa][Dd];
SELECT: [Ss][Ee][Ll][Ee][Cc][Tt];

//base 定义一些基础的lexer,
fragment DIGIT:[0-9]; //匹配数字
fragment LETTER:[a-zA-Z]; //匹配字母
STRING //匹配带引号的文本
: '\'' ( ~('\''|'\\') | ('\\' .) )* '\''
| '"' ( ~('"'|'\\') | ('\\' .) )* '"'
;
IDENTIFIER //匹配只含有数字字母和下划线的文本
: (LETTER | DIGIT | '_')+
;
BACKQUOTED_IDENTIFIER //匹配被``包裹的文本
: '`' ( ~'`' | '``' )* '`'
;

//--hiden 定义需要隐藏的文本,指向channel(HIDDEN)就会隐藏。这里的channel可以自定义,到时在后台获取不同的channel的数据进行不同的处理
SIMPLE_COMMENT: '--' ~[\r\n]* '\r'? '\n'? -> channel(HIDDEN); //忽略行注释
BRACKETED_EMPTY_COMMENT: '/**/' -> channel(HIDDEN); //忽略多行注释
BRACKETED_COMMENT : '/*' ~[+] .*? '*/' -> channel(HIDDEN) ; //忽略多行注释
WS: [ \r\n\t]+ -> channel(HIDDEN); //忽略空白符

// 匹配其他的不能使用上面的lexer进行分词的文本
UNRECOGNIZED: .;

1.2 使用流程

使用Antlr4变成的基本流程是固定的,通常分为以下3步:

  1. 基于需求按照Antlr4的规则编写自定义语法的语义规则,保存成以g4为后缀的文件
  1. 使用Antlr4工具处理g4文件,生成词法分析器、句法分析器代码、词典文件
  1. 编写代码继承Visitor类或者实现Listener接口,开发自己的业务逻辑代码

1.3 Listener和Visitor模式的区别

  • Listener模式

  • Visitor模式

  1. Listener模式通过Walker对象自定便利,不用考虑其语法树上下级关系。Visitor需要自定控制访问的子节点,如果遗漏了某个子节点,那么整个子节点就访问不到了
  1. Listener模式的方法没有返回值,Visitor模式可以设定任意返回值
  1. Listener模式的访问栈清晰明确,Visitor模式是方法调用栈,如果实现出错可能导致StackOverFlow

2. 代码工程

使用Springboot基于antlr实现计算器

  1. 引入依赖

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    <properties>
    <maven.compiler.source>8</maven.compiler.source>
    <maven.compiler.target>8</maven.compiler.target>
    <antlr4.version>4.9.1</antlr4.version>
    </properties>
    <dependencies>

    <dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-web</artifactId>
    </dependency>

    <dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-autoconfigure</artifactId>
    </dependency>
    <dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-test</artifactId>
    <scope>test</scope>
    </dependency>
    <dependency>
    <groupId>org.antlr</groupId>
    <artifactId>antlr4-runtime</artifactId>
    <version>${antlr4.version}</version>
    </dependency>

    </dependencies>
    <build>
    <!--生成词法和语法解析器-->
    <plugins>
    <plugin>
    <groupId>org.antlr</groupId>
    <artifactId>antlr4-maven-plugin</artifactId>
    <version>${antlr4.version}</version>
    <configuration>
    <sourceDirectory>src/main/java</sourceDirectory>
    <outputDirectory>src/main/java</outputDirectory>
    <arguments>
    <argument>-visitor</argument>
    <argument>-listener</argument>
    </arguments>
    </configuration>
    <executions>
    <execution>
    <goals>
    <goal>antlr4</goal>
    </goals>
    </execution>
    </executions>
    </plugin>
    </plugins>
    </build>

  2. 元语言LabeledExpr.g4

    Antlr4规则是基于正则表达式定义的,规则的理解是自顶向下的,每个分号结束的语句标识一个规则

    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
     grammar LabeledExpr; // 1. 语法定义名称,需要跟文件名保持一致

    prog: stat+ ; //2. 标识prog是一个或多个stat

    //3. 规则stat: 适配三种子规则:空行、表达式expr、负责表达式ID '=' expr。
    stat: expr NEWLINE # printExpr
    | ID '=' expr NEWLINE # assign
    | NEWLINE # blank
    ;

    //4. expr适配5种子规则:乘除法、加减法、整型、ID、括号表达式
    expr: expr op=('*'|'/') expr # MulDiv
    | expr op=('+'|'-') expr # AddSub
    | INT # int
    | ID # id
    | '(' expr ')' # parens
    ;
    //5. 定义的是组成复合规则的基础元素
    MUL : '*' ; // assigns token name to '*' used above in grammar
    DIV : '/' ;
    ADD : '+' ;
    SUB : '-' ;
    ID : [a-zA-Z]+ ; // match identifiers
    INT : [0-9]+ ; // 标识规则是0-9之间的一个或多个数字
    NEWLINE:'\r'? '\n' ; // return newlines to parser (is end-statement signal)
    WS : [ \t]+ -> skip ; // toss out whitespace
  3. 基于Visitor实现

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    import java.util.HashMap;
    import java.util.Map;

    public class EvalVisitor extends LabeledExprBaseVisitor<Integer> {
    // Store variables (for assignment)
    Map<String, Integer> memory = new HashMap<>();

    /** stat : expr NEWLINE */
    @Override
    public Integer visitPrintExpr(LabeledExprParser.PrintExprContext ctx) {
    Integer value = visit(ctx.expr()); // evaluate the expr child
    // System.out.println(value); // print the result
    return value; // return dummy value
    }

    /** stat : ID '=' expr NEWLINE */
    @Override
    public Integer visitAssign(LabeledExprParser.AssignContext ctx) {
    String id = ctx.ID().getText(); // id is left-hand side of '='
    int value = visit(ctx.expr()); // compute value of expression on right
    memory.put(id, value); // store it in our memory
    return value;
    }

    /** expr : expr op=('*'|'/') expr */
    @Override
    public Integer visitMulDiv(LabeledExprParser.MulDivContext ctx) {
    int left = visit(ctx.expr(0)); // get value of left subexpression
    int right = visit(ctx.expr(1)); // get value of right subexpression
    if (ctx.op.getType() == LabeledExprParser.MUL) return left * right;
    return left / right; // must be DIV
    }

    /** expr : expr op=('+'|'-') expr */
    @Override
    public Integer visitAddSub(LabeledExprParser.AddSubContext ctx) {
    int left = visit(ctx.expr(0)); // get value of left subexpression
    int right = visit(ctx.expr(1)); // get value of right subexpression
    if (ctx.op.getType() == LabeledExprParser.ADD) return left + right;
    return left - right; // must be SUB
    }

    /** expr : INT */
    @Override
    public Integer visitInt(LabeledExprParser.IntContext ctx) {
    return Integer.valueOf(ctx.INT().getText());
    }

    /** expr : ID */
    @Override
    public Integer visitId(LabeledExprParser.IdContext ctx) {
    String id = ctx.ID().getText();
    if (memory.containsKey(id)) return memory.get(id);
    return 0; // default value if the variable is not found
    }

    /** expr : '(' expr ')' */
    @Override
    public Integer visitParens(LabeledExprParser.ParensContext ctx) {
    return visit(ctx.expr()); // return child expr's value
    }

    /** stat : NEWLINE */
    @Override
    public Integer visitBlank(LabeledExprParser.BlankContext ctx) {
    return 0; // return dummy value
    }
    }

    测试代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    import org.antlr.v4.runtime.*;
    import org.antlr.v4.runtime.tree.ParseTree;

    import java.io.FileInputStream;
    import java.io.InputStream;

    public class CalcByVisit {
    public static void main(String[] args) throws Exception {
    ANTLRInputStream input = new ANTLRInputStream("1+2*3\n");
    LabeledExprLexer lexer = new LabeledExprLexer(input);
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    LabeledExprParser parser = new LabeledExprParser(tokens);
    ParseTree tree = parser.prog(); // parse

    EvalVisitor eval = new EvalVisitor();
    int result =eval.visit(tree);
    System.out.println(result);
    }
    }
  4. 基于listener实现

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    import org.antlr.v4.runtime.tree.ParseTreeProperty;
    import org.antlr.v4.runtime.tree.TerminalNode;

    import java.util.HashMap;
    import java.util.Map;

    public class EvalListener extends LabeledExprBaseListener {
    // Store variables (for assignment)
    private final Map<String, Integer> memory = new HashMap<>();
    // Store expression results
    private final ParseTreeProperty<Integer> values = new ParseTreeProperty<>();
    private int result=0;
    @Override
    public void exitPrintExpr(LabeledExprParser.PrintExprContext ctx) {
    int value = values.get(ctx.expr());
    //System.out.println(value);
    result=value;
    }
    public int getResult() {
    return result;
    }
    @Override
    public void exitAssign(LabeledExprParser.AssignContext ctx) {
    String id = ctx.ID().getText();
    int value = values.get(ctx.expr());
    memory.put(id, value);
    }

    @Override
    public void exitMulDiv(LabeledExprParser.MulDivContext ctx) {
    int left = values.get(ctx.expr(0));
    int right = values.get(ctx.expr(1));
    if (ctx.op.getType() == LabeledExprParser.MUL) {
    values.put(ctx, left * right);
    } else {
    values.put(ctx, left / right);
    }
    }

    @Override
    public void exitAddSub(LabeledExprParser.AddSubContext ctx) {
    int left = values.get(ctx.expr(0));
    int right = values.get(ctx.expr(1));
    if (ctx.op.getType() == LabeledExprParser.ADD) {
    values.put(ctx, left + right);
    } else {
    values.put(ctx, left - right);
    }

    }

    @Override
    public void exitInt(LabeledExprParser.IntContext ctx) {
    int value = Integer.parseInt(ctx.INT().getText());
    values.put(ctx, value);
    }

    @Override
    public void exitId(LabeledExprParser.IdContext ctx) {
    String id = ctx.ID().getText();
    if (memory.containsKey(id)) {
    values.put(ctx, memory.get(id));
    } else {
    values.put(ctx, 0); // default value if the variable is not found
    }
    }

    @Override
    public void exitParens(LabeledExprParser.ParensContext ctx) {
    values.put(ctx, values.get(ctx.expr()));
    }
    }

    测试代码:

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

    import java.io.FileInputStream;
    import java.io.IOException;
    import java.io.InputStream;

    public class CalcByListener {
    public static void main(String[] args) throws IOException {
    ANTLRInputStream input = new ANTLRInputStream("1+2*3\n");
    LabeledExprLexer lexer = new LabeledExprLexer(input);
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    LabeledExprParser parser = new LabeledExprParser(tokens);
    ParseTree tree = parser.prog(); // parse

    ParseTreeWalker walker = new ParseTreeWalker();
    EvalListener evalListener =new EvalListener();
    walker.walk(evalListener, tree);
    int result=evalListener.getResult();
    System.out.println(result);
    }
    }