ANTLR快餐教程(2) - ANTLR其实很简单

ANTLR其实很简单

ANTLR是通过递归下降的方式来解析一个语法的。
所谓的递归下降，其实很简单，不过就是一些模式匹配而己。

简单的模式匹配

我们看下官方的一个简单的例子，这是一个赋值表达式的例子。
语法这样写：

assign : ID '=' expr ';' ;

解析器的代码类似于下面这样：

void assign() {
  match(ID);
  match('=');
  expr();
  match(';');

解析只分为两种情况：第一种情况是直接模式匹配，第二种情况是调用其它函数继续分析。

我们写个完整的赋值语句的语法吧。我们简化一下，先不做递归下降，将表达式化简成只支持数字：

grammar assign;
assign : ID '=' expr ';' ;
ID : [a-z]+ ;
expr : NUMBER ;
NUMBER : [1-9][0-9]*|[0]|([0-9]+[.][0-9]+) ;

ID我们简化成只支持小写字母的组合，数字我们写个比较详细的。
上面的代码存成assign.g4，用antlr4 assign.g4命令，就可以生成java解析器代码了。

我们来看看生成的parser中的片段，跟上面的像不像：

    public final AssignContext assign() throws RecognitionException {
        AssignContext _localctx = new AssignContext(_ctx, getState());
        enterRule(_localctx, 0, RULE_assign);
        try {
            enterOuterAlt(_localctx, 1);
            {
            setState(4);
            match(ID);
            setState(5);
            match(T__0);
            setState(6);
            expr();
            setState(7);
            match(T__1);
            }
        }
        catch (RecognitionException re) {
            _localctx.exception = re;
            _errHandler.reportError(this, re);
            _errHandler.recover(this, re);
        }
        finally {
            exitRule();
        }
        return _localctx;
    }

下面是解析expr的情况：

    public final ExprContext expr() throws RecognitionException {
        ExprContext _localctx = new ExprContext(_ctx, getState());
        enterRule(_localctx, 2, RULE_expr);
        try {
            enterOuterAlt(_localctx, 1);
            {
            setState(9);
            match(NUMBER);
            }
        }
        catch (RecognitionException re) {
            _localctx.exception = re;
            _errHandler.reportError(this, re);
            _errHandler.recover(this, re);
        }
        finally {
            exitRule();
        }
        return _localctx;
    }

多种分支的情况

如果有多种可能的话，在语法里用"|"符号分别列出来就是了。ANTLR会把它翻译成switch case一样的语句。

我们把我们上面的例子扩展一下，不光支持'='还支持':='赋值

grammar assign2;
assign : ID '=' expr ';' 
         | ID ':=' expr ';' ;
ID : [a-z]+ ;
expr : NUMBER ;
NUMBER : [1-9][0-9]*|[0]|([0-9]+[.][0-9]+) ;

生成的Parser就变成switch case了：

    public final AssignContext assign() throws RecognitionException {
        AssignContext _localctx = new AssignContext(_ctx, getState());
        enterRule(_localctx, 0, RULE_assign);
        try {
            setState(14);
            _errHandler.sync(this);
            switch ( getInterpreter().adaptivePredict(_input,0,_ctx) ) {
            case 1:
                enterOuterAlt(_localctx, 1);
                {
                setState(4);
                match(ID);
                setState(5);
                match(T__0);
                setState(6);
                expr();
                setState(7);
                match(T__1);
                }
                break;
            case 2:
                enterOuterAlt(_localctx, 2);
                {
                setState(9);
                match(ID);
                setState(10);
                match(T__2);
                setState(11);
                expr();
                setState(12);
                match(T__1);
                }
                break;
            }
        }
        catch (RecognitionException re) {
            _localctx.exception = re;
            _errHandler.reportError(this, re);
            _errHandler.recover(this, re);
        }
        finally {
            exitRule();
        }
        return _localctx;
    }

这次我们直接看java语法的例子：

typeDeclaration
    :   classOrInterfaceModifier* classDeclaration
    |   classOrInterfaceModifier* enumDeclaration
    |   classOrInterfaceModifier* interfaceDeclaration
    |   classOrInterfaceModifier* annotationTypeDeclaration
    |   ';'
    ;

上面的语法在：https://github.com/antlr/grammars-v4/blob/master/java/Java.g4 中，我们把它下载下来，用antlr4 Java.g4运行一下，就生成了Lexer和Parser类。
由于是真的语法，翻出来比起纯粹的例子自然是复杂一些，不过不考虑细节，整个结构上还是很好懂的。大家只要理解这套switch case的结构就好：

...
        try {
            int _alt;
            setState(269);
            _errHandler.sync(this);
            switch ( getInterpreter().adaptivePredict(_input,10,_ctx) ) {
            case 1:
                enterOuterAlt(_localctx, 1);
                {
                setState(243);
                _errHandler.sync(this);
                _la = _input.LA(1);
                while ((((_la) & ~0x3f) == 0 && ((1L << _la) & ((1L << ABSTRACT) | (1L << FINAL) | (1L << PRIVATE) | (1L << PROTECTED) | (1L << PUBLIC) | (1L << STATIC) | (1L << STRICTFP))) != 0) || _la==AT) {
                    {
                    {
                    setState(240);
                    classOrInterfaceModifier();
                    }
                    }
                    setState(245);
                    _errHandler.sync(this);
                    _la = _input.LA(1);
                }
                setState(246);
                classDeclaration();
                }
                break;
            case 2:
                enterOuterAlt(_localctx, 2);
                {
                setState(250);
                _errHandler.sync(this);
                _la = _input.LA(1);
                while ((((_la) & ~0x3f) == 0 && ((1L << _la) & ((1L << ABSTRACT) | (1L << FINAL) | (1L << PRIVATE) | (1L << PROTECTED) | (1L << PUBLIC) | (1L << STATIC) | (1L << STRICTFP))) != 0) || _la==AT) {
                    {
                    {
                    setState(247);
                    classOrInterfaceModifier();
                    }
                    }
                    setState(252);
                    _errHandler.sync(this);
                    _la = _input.LA(1);
                }
                setState(253);
                enumDeclaration();
                }
                break;
            case 3:
                enterOuterAlt(_localctx, 3);
                {
                setState(257);
                _errHandler.sync(this);
                _la = _input.LA(1);
                while ((((_la) & ~0x3f) == 0 && ((1L << _la) & ((1L << ABSTRACT) | (1L << FINAL) | (1L << PRIVATE) | (1L << PROTECTED) | (1L << PUBLIC) | (1L << STATIC) | (1L << STRICTFP))) != 0) || _la==AT) {
                    {
                    {
                    setState(254);
                    classOrInterfaceModifier();
                    }
                    }
                    setState(259);
                    _errHandler.sync(this);
                    _la = _input.LA(1);
                }
                setState(260);
                interfaceDeclaration();
                }
                break;
            case 4:
                enterOuterAlt(_localctx, 4);
                {
                setState(264);
                _errHandler.sync(this);
                _alt = getInterpreter().adaptivePredict(_input,9,_ctx);
                while ( _alt!=2 && _alt!=org.antlr.v4.runtime.atn.ATN.INVALID_ALT_NUMBER ) {
                    if ( _alt==1 ) {
                        {
                        {
                        setState(261);
                        classOrInterfaceModifier();
                        }
                        } 
                    }
                    setState(266);
                    _errHandler.sync(this);
                    _alt = getInterpreter().adaptivePredict(_input,9,_ctx);
                }
                setState(267);
                annotationTypeDeclaration();
                }
                break;
            case 5:
                enterOuterAlt(_localctx, 5);
                {
                setState(268);
                match(SEMI);
                }
                break;
            }
        }
...

二义性文法

选择太多了也未必见得是好事儿，有一种副作用就是选择不是唯一的，这叫做『二义性文法』。
最简单的二义性文法就是把同一条规则写两遍，比如上面例子的":="我们就改成"="，让"|"之前和之后两条都一样。

grammar assign2;
assign : ID '=' expr ';' 
         | ID '=' expr ';' ;
ID : [a-z]+ ;
expr : NUMBER ;
NUMBER : [1-9][0-9]*|[0]|([0-9]+[.][0-9]+) ;

但是ANTLR4是兼容这种情况的，不报错。在实际应用的时候，它选择第一条符合条件的规则，请看生成的代码

        try {
            setState(14);
            _errHandler.sync(this);
            switch ( getInterpreter().adaptivePredict(_input,0,_ctx) ) {
            case 1:
                enterOuterAlt(_localctx, 1);
                {
                setState(4);
                match(ID);
                setState(5);
                match(T__0);
                setState(6);
                expr();
                setState(7);
                match(T__1);
                }
                break;
            case 2:
                enterOuterAlt(_localctx, 2);
                {
                setState(9);
                match(ID);
                setState(10);
                match(T__0);
                setState(11);
                expr();
                setState(12);
                match(T__1);
                }
                break;
            }
        }

最著名的二义性的例子就是关键字。在常见的编程语言中，关键字都是和标识符冲突的.
比如我们定义一个if关键字：

IF : 'if' ;
ID : [a-z]+ ;

明显，IF和ID两个规则都可以解析'if'这个串，那到底是按IF算，还是按ID算呢？在ANTLR里，规则很简单，按照可以匹配的第一条处理。

但是，光靠第一条优先，也还是解决不了所有的问题。
我们看两类新的问题

第一类：1 + 2 * 3。这个如何处理，是先算+还是先算*?
前人想出了三种办法来解决：

  • 从左到右：管人是如何理解乘除加减的，我就从左到右算。Smalltalk就是这样做的
  • 中缀转前缀：带来问题的是中缀表达式，我们给换个形式不就OK了吗，比如改成这样(+ 1 (* 2 3))，lisp就是这么做的
  • 运算符优先级：最常用的一种作法，后面我们详情分析。基本上大部分常见的语言都有一个运算符优先级的表。

第二类，是一些语言的设计所导致的，给词法分析阶段带来困难。
比如"*"运算符，在大部分语言中都只表示乘法，但是在C语言中表示指针，当i*j时，表示乘法，但是当int *j;时，就变成表示指针。
所以像Go语言在设计时，就把类型定义移到了后面。我们入门阶段暂时也不打算解析这么复杂的，将来用到了再说。

下一步做啥

经过前面学习的写grammar的过程，我们可以把字符流CharStream，转换成一棵ParseTree。
CharStream是字符流，经过词法分析会变成Token流。
Token流再最终组装成一棵ParseTree，叶子节点是TerminalNode，非叶子节点是RuleNode.

ParseTree结构图

为了节省空间，Token流之上都没有复制字符流的内容，都是通过指向字符流区缓冲区来获取内容。空白字符在Token流以上就不存在了。

既然有了ParseTree，后面的事情就好办了。我们只要遍历这棵ParseTree，就可以访问所有的节点，然后继续做代码生成之类的后端的工作。

为了方便使用，ANTLR将这些节点，封装成RuleNode的子类，前面代码中我们看到的xxxContext类，就是这些子类。比如AssignContext，ExprContext等。

具体的接口，请看图：

ParserRuleContext

我们看个AssignContext是如何被实现的：

    public static class AssignContext extends ParserRuleContext {
        public TerminalNode ID() { return getToken(assign2Parser.ID, 0); }
        public ExprContext expr() {
            return getRuleContext(ExprContext.class,0);
        }
        public TerminalNode IF() { return getToken(assign2Parser.IF, 0); }
        public AssignContext(ParserRuleContext parent, int invokingState) {
            super(parent, invokingState);
        }
        @Override public int getRuleIndex() { return RULE_assign; }
        @Override
        public void enterRule(ParseTreeListener listener) {
            if ( listener instanceof assign2Listener ) ((assign2Listener)listener).enterAssign(this);
        }
        @Override
        public void exitRule(ParseTreeListener listener) {
            if ( listener instanceof assign2Listener ) ((assign2Listener)listener).exitAssign(this);
        }
    }

两种访问ParserTree的方法

ANTLR提供了两种方法来访问ParseTree：

  • 一种是通过Parse-Tree Listener的方法
  • 另一种是通过Parse-Tree Visitor的方法

Listener方法有点类似于解析XML的SAX方法。
废话不多说了，这篇文章已经有点长了，我们直接上代码：

// Generated from assign2.g4 by ANTLR 4.6
import org.antlr.v4.runtime.tree.ParseTreeListener;

/**
 * This interface defines a complete listener for a parse tree produced by
 * {@link assign2Parser}.
 */
public interface assign2Listener extends ParseTreeListener {
    /**
     * Enter a parse tree produced by {@link assign2Parser#assign}.
     * @param ctx the parse tree
     */
    void enterAssign(assign2Parser.AssignContext ctx);
    /**
     * Exit a parse tree produced by {@link assign2Parser#assign}.
     * @param ctx the parse tree
     */
    void exitAssign(assign2Parser.AssignContext ctx);
    /**
     * Enter a parse tree produced by {@link assign2Parser#expr}.
     * @param ctx the parse tree
     */
    void enterExpr(assign2Parser.ExprContext ctx);
    /**
     * Exit a parse tree produced by {@link assign2Parser#expr}.
     * @param ctx the parse tree
     */
    void exitExpr(assign2Parser.ExprContext ctx);
}

开始解析Assign的时候，会回调etnterAssign方法，结束时回调exitAssign方法。

另一种是采用visitor模式的方法，我们调用antlr4的时候要增加-visitor参数来生成。

Visitor仍然非常简单，我们直接看代码：

// Generated from assign2.g4 by ANTLR 4.6
import org.antlr.v4.runtime.tree.ParseTreeVisitor;

/**
 * This interface defines a complete generic visitor for a parse tree produced
 * by {@link assign2Parser}.
 *
 * @param <T> The return type of the visit operation. Use {@link Void} for
 * operations with no return type.
 */
public interface assign2Visitor<T> extends ParseTreeVisitor<T> {
    /**
     * Visit a parse tree produced by {@link assign2Parser#assign}.
     * @param ctx the parse tree
     * @return the visitor result
     */
    T visitAssign(assign2Parser.AssignContext ctx);
    /**
     * Visit a parse tree produced by {@link assign2Parser#expr}.
     * @param ctx the parse tree
     * @return the visitor result
     */
    T visitExpr(assign2Parser.ExprContext ctx);
}

好的，基本概念已经准备好了，下一篇教程我们就正式利用这些组件来实现了一个解析器。

结束之前，我们搞个能运行的调用前面语法解析器的例子，最终生成一棵ParseTree.

语法文件再列一遍，省得大家向上翻了：

grammar Assign;
assign : ID '=' expr ';' 
         | ID ':=' expr ';' ;
ID : [a-z]+ ;
expr : NUMBER ;
NUMBER : [1-9][0-9]*|[0]|([0-9]+[.][0-9]+) ;
WS : [ \t\r\n]+ -> skip ;

调用antlr4 Assign.g4，然后写个调用的main方法吧：

import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.*;

public class TestAssign {
    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);

        AssignLexer lexer = new AssignLexer(input);

        CommonTokenStream tokens = new CommonTokenStream(lexer);

        AssignParser parser = new AssignParser(tokens);

        ParseTree tree = parser.assign();

        System.out.println(tree.toStringTree(parser));
    }
}

试试灵不灵吧：

java TestAssign
a = 1;

输出如下：

(assign a = (expr 1) ;)

再试一个用:=赋值的：

java TestAssign
b := 0;

输出如下：

(assign b := (expr 0) ;)

很好玩吧？虽然例子很简单，但是我们已经完成了从写语法规则到使用ParseTree的全过程。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 217,509评论 6赞 504
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,806评论 3赞 394
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 163,875评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,441评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,488评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,365评论 1赞 302
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,190评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,062评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,500评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,706评论 3赞 335
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,834评论 1赞 347
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,559评论 5赞 345
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,167评论 3赞 328
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,779评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,912评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,958评论 2赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,779评论 2赞 354

推荐阅读更多精彩内容