Java-ANTLR,表达式语法有问题

2022-11-03 10:44:12

我最近开始使用ANTLR.我目前正在尝试使用,-,*和array [index]以及其他一些结构来编码表达式语法.

这是所需的语法：

Exp -> Exp (+ | - | * | < | &&) Exp
     | Exp [ Exp ]
     | -Exp
     | ( Exp )
     | Exp.length
     | true
     | false
     | Id
     | this
     | ! Exp

我首先将其重构为AndExp,SumExp,ProdExp等,以解决优先级问题.大致像这样：

Exp        -> AndExp
AndExp     -> CmpExp (&& CmpExp)*
CmpExp     -> SumExp (< SumExp)*
SumExp     -> ProdExp ((+|-) ProdExp)*
ProdExp    -> UnaryExp (Times UnaryExp)*
UnaryExp   -> Minus* PrimaryExp
PrimaryExp -> Exp.length
            | Exp [ Exp ]
            | ! Exp
            | true
            | false
            | Id
            | this

然后,我意识到这使用了左递归,而ANTLR不喜欢这样.我继续学习eliminate the left-recursion,最后得到了这个语法：

grammar test;

options {
    language=Java;
    output=AST;
    backtrack=true;
}

start      : expression;

expression : andExp;
andExp     : cmpExp (And^ cmpExp)*;
cmpExp     : sumExp (LessThan^ sumExp)*;
sumExp     : prodExp ((Plus | Minus)^ prodExp)*;
prodExp    : unaryExp (Times^ unaryExp)*;
unaryExp   : Minus* primaryExp;

primaryExp : INT                   primaryPrime
           | 'true'                primaryPrime
           | 'false'               primaryPrime
           | 'this'                primaryPrime
           | ID                    primaryPrime
           | '!' expression        primaryPrime
           | '('! expression ')'!  primaryPrime
           ;


primaryPrime
           : '[' expression ']'             primaryPrime
           | '.' ID '(' exprList ')'        primaryPrime
           | '.length'                      primaryPrime
           | 'new' 'int' '[' expression ']' primaryPrime
           | 'new' ID '(' ')'               primaryPrime
           |
           ;


exprList   :
           | expression (',' expression)*;

LessThan   : '<';
Plus       : '+';
Minus      : '-';
Times      : '*';
And        : '&&';
Not        : '!';
INT        :    '0' | ('1'..'9')('0'..'9')*;
ID         :    ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*;
WS         : ('\t' | ' ' | '\r' | '\n'| '\u000C') { $channel=HIDDEN; } ;

>问题1：这种语法是否需要“回溯”(除非激活,否则无法通过ANTLR获得)还是缺少简单的东西？
>问题2：在添加一些^和-> ^(TOKEN …)构造为刷树,我遇到了以下令人讨厌的情况(由于primaryPrime是由于左分解)：

primaryPrime
    : '[' expression ']' primaryPrime -> ^(ARRAY_EXPR expression)
//...

这会将array [index]变成

array
ARRAY_EXPR
    index

虽然我真的想要

ARRAY_EXPR
    array
    index

解决此问题的最佳方法是什么？我是在这里吗？还是应该一起采取其他方法？

解决方法:

否,还不需要回溯.但是,如果确实需要一些回溯,建议不要立即使用backtrack = true,而应在确实需要回溯的规则之前使用谓词.通过使用backtrack = true,可以对所有规则启用回溯,而可能只有一两个需要回溯.但是,如果您的语言相对较小,则backtrack = true比手工混合谓词更容易,并且可能不会对性能产生重大影响.但是,如果可以避免,请这样做.

您有几个解析器规则匹配空字符串,这会导致问题.通常,最好让规则匹配某些内容,并将规则设置为可选.所以代替：

foo : bar baz ;
bar : 'bar' ;
baz : 'baz' | /* epsilon */ ;

做

foo : bar baz? ;
bar : 'bar' ;
baz : 'baz' ;

代替.

另外,在使用诸如true,false等保留关键字的情况下,请不要在解析器规则中混合使用它们：始终在词法分析器规则的顶部明确定义它们. Lexer规则是从上到下匹配的,因此(至少)最安全地定义它们(例如ID)也可以匹配它们.我通常把它们作为第一个词法分析器规则.

您可以通过将参数传递给解析器规则来做到这一点,尽管这样会使语法(有点)的可读性降低.

您的语法和我的评论：

grammar test;

options {
  output=AST;
}

tokens {
  ARRAY_EXPR;
}

start      : expression;

expression : andExp;
andExp     : cmpExp (And^ cmpExp)*;
cmpExp     : sumExp (LessThan^ sumExp)*;
sumExp     : prodExp ((Plus | Minus)^ prodExp)*;
prodExp    : unaryExp (Times^ unaryExp)*;
unaryExp   :  '-' primaryExp
           |  '!' primaryExp // negation is really a `unaryExp`
           |  primaryExp
           ;

primaryExp : INT                  primaryPrime[null]?
           | 'true'               primaryPrime[null]?
           | 'false'              primaryPrime[null]?
           | 'this'               primaryPrime[null]?
           | (ID -> ID)           (primaryPrime[new CommonTree($ID)] -> primaryPrime)?
           | '('! expression ')'! primaryPrime[null]?
           ;

// removed the matching of 'epsilon'
primaryPrime [CommonTree parent]
           : '[' expression ']'             primaryPrime[null]? -> ^(ARRAY_EXPR {parent} expression primaryPrime?)
           | '.' ID '(' exprList? ')'       primaryPrime[null]?
           | '.length'                      primaryPrime[null]?
           | 'new' 'int' '[' expression ']' primaryPrime[null]?
           | 'new' ID '(' ')'               primaryPrime[null]?
           ;

// removed the matching of 'epsilon' 
exprList   : expression (',' expression)*;

// be sure to create explicit tokens for keywords!
True       : 'true';
False      : 'false';
This       : 'this';
LessThan   : '<';
Plus       : '+';
Minus      : '-';
Times      : '*';
And        : '&&';
Not        : '!';
INT        : '0' | ('1'..'9')('0'..'9')*;
ID         : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*;
WS         : ('\t' | ' ' | '\r' | '\n'| '\u000C') { $channel=HIDDEN; } ;

会将输入“ array [2 * 3]”解析为以下AST：

如您所见,通过运行以下测试类：

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

public class Main {
  public static void main(String[] args) throws Exception {
    String source = "array[2*3]";
    testLexer lexer = new testLexer(new ANTLRStringStream(source));
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    testParser parser = new testParser(tokens);
    testParser.start_return returnValue = parser.start();
    CommonTree tree = (CommonTree)returnValue.getTree();
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT(tree);
    System.out.println(st);
  }
}

码农公寓

相关文章