antlr词法和语法分析

2024-06-23 03 SpringBoot antlr 0 评论阅读时长: 12(分)

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的形式,以分号结尾

示例代码：:

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步：

基于需求按照Antlr4的规则编写自定义语法的语义规则，保存成以g4为后缀的文件

使用Antlr4工具处理g4文件，生成词法分析器、句法分析器代码、词典文件

编写代码继承Visitor类或者实现Listener接口，开发自己的业务逻辑代码

1.3 Listener和Visitor模式的区别

Listener模式

Visitor模式

Listener模式通过Walker对象自定便利，不用考虑其语法树上下级关系。Visitor需要自定控制访问的子节点，如果遗漏了某个子节点，那么整个子节点就访问不到了

Listener模式的方法没有返回值，Visitor模式可以设定任意返回值

Listener模式的访问栈清晰明确，Visitor模式是方法调用栈，如果实现出错可能导致StackOverFlow

2. 代码工程

使用Springboot基于antlr实现计算器

引入依赖

<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>

元语言LabeledExpr.g4

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

 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

基于Visitor实现

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
    }
}

测试代码：

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);
  }
}

基于listener实现

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()));
    }
}

测试代码：

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);
    }
}

本文链接： http://xiaoyuge.work/spring-boot-antlr/index.html

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！本博客如有侵权，请联系删除！

小余哥xiaoyouge

分享一些技术教程与实践，以及日常踩坑记录。