詞法和語法分析器構建

ANTLR簡介

ANTLR全稱ANother Tool for Languate Recognition,是基于LL(*)演算法實作的語法分析器生成器和詞法分析器生成器，由舊金山大學的Terence Parr博士等人創建，截止到目前，ANTLR已經支持生成適用于Ada95、C、C＃、JavaScript、Objective-C、Perl、Python、Ruby、C++和Standard ML等多種編程語言的詞法和語法分析器了，

ANTLR安裝

$ cd /usr/local/lib
$ wget https://www.antlr.org/download/antlr-4.7.1-complete.jar
$ export CLASSPATH=".:/usr/local/lib/antlr-4.7.1-complete.jar:$CLASSPATH"
$ alias antlr4='java -jar /usr/local/lib/antlr-4.7.1-complete.jar'
$ alias grun='java org.antlr.v4.gui.TestRig'

詞法分析和Antlr詞法定義

詞法分析就是講字符序列轉換為單詞序列的程序，單詞是構成源代碼的最小單位，它由一個或多個連續字符組成，比如對代碼int year=2018進行詞法分析，源代碼將被轉換成由5個單詞組成的序列：int,\s(空格)，year,=和2018，

antlr的詞法定義比較簡單，大部分的詞法都可以使用簡單的正則運算式表示，我們來看一個簡單的例子DemoLexer.g4：

lexer grammer Demo;
PLUS:'+';
MINUS:'-';
MULTIPLE:'*';
DIV:'/';
LPAREN:'(';
RPAREN:')';
NUMBER:[0-9]+;

第1行宣告這是一個詞法定義檔案，第2-7定義4個運算子關鍵字和左右兩個括號，第8行則是正整數的定義，

語法分析和antlr語法定義

語法分析就是根據特定的形式文法對由單詞序列構成的輸入進行分析并確定其語法結構的程序，比如int,\s(空格)，year,=和2018這5個單詞序列按順序輸入到語法分析器，語法分析器就能識別出這是一條變數宣告和初始化的陳述句，

antlr的語法定義和詞法定義類似，列出所有可能的單詞組合情況，我們還是從一個簡單的四則運算語法定義作為例子，

DemoParser.g4

parser grammar DemoParser;
options { tokenVocab=DemoLexer; }
expr:
    '(' expr ')'
    | NUMBER ( MULTIPLE | DIV ) NUMBER
    | NUMBER ( PLUS | MINUS ) NUMBER
;

第1行宣告這是一個語法定義檔案，第2行設定詞法選項，說明使用哪個詞法，第3-7行是運算運算式的文法定義，這里簡單介紹一下，expr為我們為文法取的名稱，此文法有三種情況：由括號包起來的運算式、乘除運算式和加減運算式，需要注意的是乘除運算式和加減運算式定義的順序不能隨便調換，不然會影響運算子的優先級，得到錯誤的語法決議樹，高優先級的運算式需要先定義，

生成詞法分析器和語法分析器

上面只是antlr詞法和語法的定義，無法在java里直接使用，因為它不是合法的java源代碼，我們需要將其轉換成java代碼，這個轉換作業還是由antlr為我們完成，在終端運行如下命令：

antlr4 DemoLexer.g4 -package demo.antlr
antlr4 DemoParser.g4 -package demo.antlr -visitor

命令執行后，將會自動生成如下檔案：

DemoLexer.java
DemoLexer.tokens
DemoParser.java
DemoParser.tokens
DemoParserBaseListener.java
DemoParserBaseVisitor.java
DemoParserListener.java
DemoParserVisitor.java

這些java檔案就是我們能在程式里直接呼叫的詞法分析器和語法分析器，

詞法分析器和語法分析器的使用

生成的詞法分析器和語法分析器拷貝到原始碼目錄后就可以直接使用了，我們來看一下最常用的呼叫方法：

String source = "1+2+3";//我們需要決議的運算式
CharStream charStream = new ANTLRInputStream(source);
DemoLexer lexer = new DemoLexer(charStrem);//詞法分析器
CommonTokenStream tokenStream = new CommonTokenStream(lexer);
DemoParser parser = new DemoParser(tokenStream);//語法分析器
ExprContext exprContext = parser.expr();//以expr規則為起始規矩開始決議,得到語法決議樹

通過以上步驟，運算式字串最終被轉換成了語法決議樹，有了語法決議樹，對運算式求值就變得很簡單了，首先，我們先定義一個決議樹訪問（遍歷）器MainDemoParserVisitor.java:

public MainDemoParserVisitor extends DemoParserBaseVisitor {
    @override
    public Integer visitExpr(ExprContext ctx) {
        if (ctx.MULTIPLE()!=null) {//乘法
            return Integer.parseInt(ctx.NUMBER(0)) * Integer.parseInt(ctx.NUMBER(1));
        } else if (ctx.DIV()!=null) {//除法
            return Integer.parseInt(ctx.NUMBER(0)) / Integer.parseInt(ctx.NUMBER(1));
        } else if (ctx.PLUS()!=null) {//加法
            return Integer.parseInt(ctx.NUMBER(0)) + Integer.parseInt(ctx.NUMBER(1));
        } else if (ctx.MINUS()!=null) {//減法
            return Integer.parseInt(ctx.NUMBER(0)) - Integer.parseInt(ctx.NUMBER(1));
        } else {//對括號內運算式求值
            return visitExpr(ctx.expr());
        }
    }

}

使用訪問器對決議樹進行遍歷并求值：

MainDemoParserVisitor visitor = new MainDemoParserVisitor();//創建訪問者
Integer result = (Integer) vistor.visit(exprContext);//開始遍歷語法決議樹對運算式求值
System.out.println(result);

參考鏈接

1. Antlr檔案：https://github.com/antlr/antlr4/blob/master/doc/index.md
2. Antlr詞法語法示例：https://github.com/antlr/grammars-v4
3. 使用Antlr構建的編程語言Kalang：https://github.com/kasonyang/kalang

標籤：Java

上一篇：你可能不了解的java列舉

下一篇：增添修改洗掉查詢Java vs c#