快速上手ANTLR

2021 年 12 月 10 日
筆記
antlr4

回顧前文：

下面通過兩個實例來快速上手ANTLR。

使用Listener轉換數組

完整源碼見：//github.com/bytesfly/antlr-demo/tree/main/array-init/src/main/java/com/github/bytesfly/arr

效果如下圖所示：

該程式能識別輸入的整數數組並將其轉化為JSON格式的字元串數組。

語法規則為ArrayInit.g4，如下：

/** Grammars always start with a grammar header. This grammar is called
 *  ArrayInit and must match the filename: ArrayInit.g4
 */
grammar ArrayInit;

@header {package com.github.bytesfly.arr.antlr;}

/** A rule called init that matches comma-separated values between {...}. */
init  : '{' value (',' value)* '}' ;  // must match at least one value

/** A value can be either a nested array/struct or a simple integer (INT) */
value : init
      | INT
      ;

// parser rules start with lowercase letters, lexer rules with uppercase
INT :   [0-9]+ ;             // Define token INT as one or more digits
WS  :   [ \t\r\n]+ -> skip ; // Define whitespace rule, toss it out

我們自定義IntToStringListener.java，如下：

public class IntToStringListener extends ArrayInitBaseListener {

    private final StringBuilder builder = new StringBuilder();

    /**
     * Translate { to [
     */
    @Override
    public void enterInit(ArrayInitParser.InitContext ctx) {
        builder.append('[');
    }

    /**
     * Translate } to ]
     */
    @Override
    public void exitInit(ArrayInitParser.InitContext ctx) {
        // 去除value節點後的逗號
        builder.setLength(builder.length() - 1);
        builder.append(']');

        if (ctx.parent != null) {
            // 嵌套結構需要追加逗號，與enterValue的處理保持一致
            builder.append(',');
        }
    }

    /**
     * Translate integers to strings with ""
     */
    @Override
    public void enterValue(ArrayInitParser.ValueContext ctx) {
        TerminalNode node = ctx.INT();
        if (node != null) {
            builder.append("\"").append(node.getText()).append("\",");
        }
    }

    public String getResult() {
        return builder.toString();
    }
}

最終的轉換程式為Translate.java，如下：

public class Translate {

    public static void main(String[] args) throws Exception {
        // 從鍵盤輸入
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {

            String s = sc.nextLine();

            // 從字元串讀取輸入數據
            CharStream input = CharStreams.fromString(s);

            // 新建一個詞法分析器
            ArrayInitLexer lexer = new ArrayInitLexer(input);

            // 新建一個詞法符號的緩衝區，用於存儲詞法分析器將生成的詞法符號
            CommonTokenStream tokens = new CommonTokenStream(lexer);

            // 新建一個語法分析器，處理詞法符號緩衝區中的內容
            ArrayInitParser parser = new ArrayInitParser(tokens);

            // 針對init規則，開始語法分析
            ParseTree tree = parser.init();

            // 新建一個通用的、能夠觸發回調函數的語法分析樹遍歷器
            ParseTreeWalker walker = new ParseTreeWalker();

            // 創建我們自定義的監聽器
            IntToStringListener listener = new IntToStringListener();

            // 遍歷語法分析過程中生成的語法分析樹，觸發回調
            walker.walk(listener, tree);

            // 列印轉換結果
            System.out.println(listener.getResult());
        }
    }
}

監聽器機制的優雅之處在於，不需要自己編寫任何遍歷語法分析樹的程式碼。事實上，我們甚至都不知道ANTLR運行庫是怎麼遍歷語法分析樹、怎麼調用我們的方法的。我們只知道，在語法規則對應的語句的開始和結束位置處，我們的監聽器方法可以得到通知。

當然如果想知道ANTLR運行庫是怎麼遍歷語法分析樹並不困難，見org.antlr.v4.runtime.tree.ParseTreeWalker#walk()：

public void walk(ParseTreeListener listener, ParseTree t) {
    if ( t instanceof ErrorNode) {
        listener.visitErrorNode((ErrorNode)t);
        return;
    }
    else if ( t instanceof TerminalNode) {
        listener.visitTerminal((TerminalNode)t);
        return;
    }
    RuleNode r = (RuleNode)t;
    enterRule(listener, r);
    int n = r.getChildCount();
    for (int i = 0; i<n; i++) {
        walk(listener, r.getChild(i));
    }
    exitRule(listener, r);
}

這段程式碼也非常容易懂，其實就是常規樹的遍歷，遍歷過程中反調自定義的IntToStringListener中的實現方法。

使用Visitor構建計算器

完整源碼見：//github.com/bytesfly/antlr-demo/tree/main/calculator/src/main/java/com/github/bytesfly/calculator

該程式能識別賦值語句並做加減乘除四則運算，效果大致如下。

輸入：

100
a = 1
b = 2
a+b*2
((2+3)*(6+1)-5) / 3

輸出：

100
5
10

語法規則為Expr.g4，如下：

grammar Expr;

@header {package com.github.bytesfly.calculator.antlr;}

/** The start rule; begin parsing here. */
prog:   stat+ ;

stat:   expr NEWLINE                # printExpr
    |   ID '=' expr NEWLINE         # assign
    |   NEWLINE                     # blank
    ;

expr:   expr op=('*'|'/') expr      # MulDiv
    |   expr op=('+'|'-') expr      # AddSub
    |   INT                         # int
    |   ID                          # id
    |   '(' expr ')'                # parens
    ;

MUL :   '*' ; // assigns token name to '*' used above in grammar
DIV :   '/' ;
ADD :   '+' ;
SUB :   '-' ;
ID  :   [a-zA-Z]+ ;      // match identifiers
INT :   [0-9]+ ;         // match integers
NEWLINE:'\r'? '\n' ;     // return newlines to parser (is end-statement signal)
WS  :   [ \t]+ -> skip ; // toss out whitespace

編寫一個用於處理計算邏輯的訪問器EvalVisitor.java，如下：

public class EvalVisitor extends ExprBaseVisitor<Integer> {

    /**
     * 存放變數名和變數值的對應關係
     */
    private final Map<String, Integer> memory = new HashMap<>();

    /**
     * ID '=' expr NEWLINE  # assign
     */
    @Override
    public Integer visitAssign(ExprParser.AssignContext ctx) {
        // 獲取變數名
        String id = ctx.ID().getText();
        // 計算表達式的值
        Integer value = visit(ctx.expr());
        // 暫存到map中
        memory.put(id, value);

        return value;
    }

    /**
     * expr NEWLINE  # printExpr
     */
    @Override
    public Integer visitPrintExpr(ExprParser.PrintExprContext ctx) {
        // 計算表達式的值
        Integer value = visit(ctx.expr());
        // 列印
        System.out.println(value);

        return 0;
    }

    /**
     * INT  # int
     */
    @Override
    public Integer visitInt(ExprParser.IntContext ctx) {
        return Integer.valueOf(ctx.INT().getText());
    }

    /**
     * ID  # id
     */
    @Override
    public Integer visitId(ExprParser.IdContext ctx) {
        String id = ctx.ID().getText();
        return memory.getOrDefault(id, 0);
    }

    /**
     * expr op=('*'|'/') expr  # MulDiv
     */
    @Override
    public Integer visitMulDiv(ExprParser.MulDivContext ctx) {
        // 計算左側子表達式的值
        Integer left = visit(ctx.expr(0));
        // 計算右側子表達式的值
        Integer right = visit(ctx.expr(1));

        // 根據不同的操作符做相應的運算
        if (ctx.op.getType() == ExprParser.MUL) {
            return left * right;
        } else {
            return left / right;
        }
    }

    /**
     * expr op=('+'|'-') expr  # AddSub
     */
    @Override
    public Integer visitAddSub(ExprParser.AddSubContext ctx) {
        // 計算左側子表達式的值
        Integer left = visit(ctx.expr(0));
        // 計算右側子表達式的值
        Integer right = visit(ctx.expr(1));

        // 根據不同的操作符做相應的運算
        if (ctx.op.getType() == ExprParser.ADD) {
            return left + right;
        } else {
            return left - right;
        }
    }

    /**
     * '(' expr ')'  # parens
     */
    @Override
    public Integer visitParens(ExprParser.ParensContext ctx) {
        // 返回子表達式的值
        return visit(ctx.expr());
    }
}

最終能識別輸入表達式並做加減乘除四則運算的Calc.java，如下：

public class Calc {
    public static void main(String[] args) throws Exception {
        // 讀取resources目錄下example.expr表達式文件
        String s = FileUtil.readUtf8String("example.expr");

        // 從字元串讀取輸入數據
        CharStream input = CharStreams.fromString(s);

        // 新建一個詞法分析器
        ExprLexer lexer = new ExprLexer(input);

        // 新建一個詞法符號的緩衝區，用於存儲詞法分析器將生成的詞法符號
        CommonTokenStream tokens = new CommonTokenStream(lexer);

        // 新建一個語法分析器，處理詞法符號緩衝區中的內容
        ExprParser parser = new ExprParser(tokens);

        // 針對prog規則，開始語法分析
        ParseTree tree = parser.prog();

        // 創建訪問器對象
        EvalVisitor eval = new EvalVisitor();
        // 訪問語法樹
        eval.visit(tree);
    }
}

對整個調用過程疑惑的朋友，建議自行下載源碼，打斷點觀察執行邏輯。

從上面的例子可以看出：使用ANTLR4語法文件獨立於程式，具有程式語言中立性。

訪問器機制也使得語言識別之外的工作在我們所熟悉的Java領域進行。在生成的所需的語法分析器之後，就不再需要同ANTLR語法標記打交道了。

Tags: antlr4