首页 文章

ANTLR词法分析器规则中的句法谓词

提问于
浏览
3

简介

看一下这个文档,ANTLR 2曾经有一个名为predicated lexing的东西,有这样的例子(受Pascal启发):

RANGE_OR_INT
    :   ( INT ".." ) => INT  { $setType(INT); }
    |   ( INT '.' )  => REAL { $setType(REAL); }
    |   INT                  { $setType(INT); }
    ;

我看到它的方式,在规则开始时基本上是一个积极的前瞻断言:如果前瞻匹配 INT ".." 则第一个规则将应用(并匹配该输入的 INT 部分),依此类推 .

我还没有在ANTLR 4中找到类似的东西 . 2 to 3 migration guide似乎没有提到这一点,而3 to 4 changes document表示:

ANTLR 3和4之间最大的区别是ANTLR 4接受你给它的任何语法,除非语法有间接的左递归 . 这意味着我们不需要语法谓词或回溯,因此ANTLR 4不支持该语法;您将收到使用它的警告 .

这符合我得到的错误消息,如果我基本上这样做:

(...)=> syntactic predicates are not supported in ANTLR 4

虽然我可以理解一个更智能的解析器实现如何解决这些歧义,但我没有看到这对于词法分析器是如何工作的 .

再现示例

可以肯定的是,让我们试一试:

grammar Demo;
prog:   atom (',' atom)* ;
atom:   INT  { System.out.println("INT:   " + $INT.getText()); }
    |   REAL { System.out.println("REAL:  " + $REAL.getText()); }
    |   a=INT RANGE b=INT { System.out.println("RANGE: " +
                              $a.getText() + " .. " + $b.getText()); }
    ;
WS  :   (' ' | '\t' | '\n' | '\r')+ -> skip ;
INT :   ('0'..'9')+ ;
REAL:   INT '.' INT? | '.' INT ;
RANGE:  '..' ;

将其保存到 Demo.g ,然后编译并运行:

$ wget -nc http://www.antlr.org/download/antlr-4.5.2-complete.jar
$ java -jar antlr-4.5.2-complete.jar Demo.g
$ javac -cp antlr-4.5.2-complete.jar Demo*.java
$ java -cp .:antlr-4.5.2-complete.jar org.antlr.v4.gui.TestRig \
  Demo prog <<< '1,2.,3.4,5 ..6,7..8'
INT:   1
REAL:  2.
REAL:  3.4
RANGE: 5 .. 6
REAL:  7.
line 1:17 extraneous input '.8' expecting {<EOF>, ','}

所以看起来我是正确的:虽然删除语法预定义可能适用于解析器,但词法分析器不会突然猜出正确的令牌类型 .

核心问题

So how would one convert this specific example to ANTLR 4? 有没有办法表达前瞻性条件?或者也许像 INT '..' 这样的单一规则发出两个不同的标记?

参考资料和可能的解决方案

看一下ANTLR 4 Pascal grammar,我注意到它不允许实数在 . 之后没有数字结束,因此从那里学习解决方案似乎不是一个选项 .

我见过Semantic predicates in ANTLR4?syntactic predicates - Upgrading from Antlr 3 to Antlr 4 . 两者都讨论解析器规则中的语法谓词 . 后者也有一个lexer规则的例子,但是前瞻与其后面的规则相同,这意味着可以删除规则而不会产生不利影响 . 在我上面的例子中并非如此 .

check previous/left token in lexer的答案提到词法分析器的 emit 方法,注释引用了ANTLR 3 wiki中的How can I emit more than a single token per lexer rule? FAQ页面,所以我猜这是一种方法 . 如果没有人打败我,我会把它变成一个答案,如果我能在我的例子中得到它 .

ANTLR4 negative lookahead in lexer的答案使用 _input.LA(int) 方法来检查前瞻 . ANTLR 4提到lexical analysis faq没有详细说明 . 这也应该适用于上面的示例,但对于需要考虑多个前瞻字符的情况来说会很困难 .

2 回答

  • 1

    sources of the current (as of this writing) Lexer implementation包含多个关于多个令牌发射的文档字符串条目 . 这些当然也在_1573660中表示 . 根据这些,必须做以下事情:

    出于效率原因,默认情况下,每次nextToken调用不支持多次发出 . 子类并覆盖此方法,nextToken和getToken(将令牌推入列表并从该列表中拉出而不是单个变量,如此实现所做的那样) .

    如果发出多个令牌,则覆盖 .

    • 确保将_token设置为非 null

    如果您子类允许多个令牌发射,则将其设置为要匹配的最后一个令牌或非空的令牌,以便自动令牌发出机制不会发出另一个令牌 .

    但是,我不明白为什么重写 getToken 会很重要,因为我看到在运行时库中的任何地方都没有调用该方法 . 如果你设置 _token ,那么这也将是 getToken 的输出 .

    所以我从单一规则中发出两个令牌的做法是:

    @lexer::members {
    
        private Token _queued;
    
        @Override public Token nextToken() {
            if (_queued != null) {
                emit(_queued);
                _queued = null;
                return getToken();
            }
            return super.nextToken();
        }
    
        @Override public Token emit() {
            if (_type != INT_RANGE)
                return super.emit();
            Token t = _factory.create(
                _tokenFactorySourcePair, INT, null, _channel,
                _tokenStartCharIndex, getCharIndex()-3,
                _tokenStartLine, _tokenStartCharPositionInLine);
            _queued = _factory.create(
                _tokenFactorySourcePair, RANGE, null, _channel,
                getCharIndex()-2, getCharIndex()-1, _tokenStartLine,
                _tokenStartCharPositionInLine + getCharIndex()-2 -
                _tokenStartCharIndex);
            emit(t);
            return t;
        }
    }
    
    INT_RANGE: INT '..' ;
    

    然而,所有的位置计算都感到相当乏味,并给了我另一个(至少对于这个应用程序更好)的想法,我将在一个特殊的答案中发布 .

  • 1

    这是一个非常简短的解决方案:

    @lexer::members { private int _pos; }
    INT_RANGE: INT  { _pos=_input.index(); setType(INT); emit(); }
               '..' { _input.seek(_pos); };
    

    这与整个 INT '..' 表达式匹配,但随后将输入重新排列在 INT 之后,我们发出令牌并保存位置 . 然后在规则的末尾使用该位置以更永久的方式回绕输入 .

    但是,存在一个问题:由此产生的标记将具有不正确的位置信息,因为 _input.seek 不会影响 getCharPositionInLine 返回的内容 . 在这种情况下,人们可以做

    setCharPositionInLine(getCharPositionInLine() - 2)
    

    在规则的最后,但如果不是 .. 处理可变长度的输入,那么这种方法将不起作用 . 我希望我能够在第一个动作中保存 getCharPositionInLine() 的结果,但不幸的是,这已经反映了整个表达的结束 .

    LexerATNSimulator.evaluatePredicate我看到这个方法努力恢复给定的位置状态 . 因此,我们可以通过滥用语义谓词来获得正确的状态:

    @lexer::members {
        private int _savedIndex, _savedLine, _savedColumn;
        private boolean remember() {
            _savedIndex = _input.index();
            _savedLine = getLine();
            _savedColumn = getCharPositionInLine();
            return true;
        }
        private void recall(int type) {
            _input.seek(_savedIndex);
            setLine(_savedLine);
            setCharPositionInLine(_savedColumn);
            setType(type);
        }
    }
    INT_RANGE: INT { remember() }? '..' { recall(INT); } ;
    

    请记住,语义谓词将在某个时间点执行,在这个时间点,来自不同规则的调用会覆盖状态 . 如果有疑问,您可以使用多个此类函数或数组索引,以使每个匹配明确无误 .

相关问题