与类似字符串匹配的Antlr lexer标记,如果贪婪的词法分子犯了错误怎么办？

Question

似乎有时Antlr词法分析器在对字符流进行标记时使用哪个规则做出了错误的选择......我正在试图弄清楚如何帮助Antlr做出明显的人性化选择.我想解析这样的文字:

d/dt(x)=a
a=d/dt
d=3
dt=4

这是一种现有语言使用的不幸语法,我正在尝试编写解析器."d/dt(x)"表示微分方程的左侧.如果必须,请忽略行话,只要知道它不是"d"除以"dt".然而,第二次出现的"d/dt"确实是"d"除以"dt".

这是我的语法:

grammar diffeq_grammar;

program :   (statement? NEWLINE)*;

statement
    :   diffeq
    |   assignment;

diffeq  :   DDT ID ')' '=' ID;

assignment
    :   ID '=' NUMBER
    |   ID '=' ID '/' ID
    ;

DDT :   'd/dt(';
ID  :   'a'..'z'+;
NUMBER  :   '0'..'9'+;
NEWLINE :   '\r\n'|'\r'|'\n';

当使用这个语法时,词法分析器抓住第一个"d/dt("并将其转换为令牌DDT.完美!现在,词法分析器看到第二个"d"后跟一个"/"并说"嗯,我可以匹配这个作为一个ID和一个'/',或者我可以贪婪并匹配DDT".词法分析器选择贪婪...但它知之甚少,没有"("输入流后面的几个字符.当lexer查找缺少的"("它会抛出MismatchedTokenException!

到目前为止我找到的唯一解决方案是将所有规则移到解析器中,语法如下:

grammar diffeq_grammar;

program :   (statement? NEWLINE)*;

statement
    :   diffeq
    |   assignment;

diffeq  :   ddt id ')' '=' id;

assignment
    :   id '=' number
    |   id '=' id '/' id
    ;

ddt :   'd' '/' 'd' 't' '(';
id  :   CHAR+;
number  :   DIGIT+;
CHAR    :   'a'..'z';
DIGIT   :   '0'..'9';
NEWLINE :   '\r\n'|'\r'|'\n';

如果我还没有依赖于第一个语法工作的数千行工作代码,这是一个很好的解决方案.在花了两天时间研究这个问题之后,我得出结论,一个词法分析者......真的应该能够区分这两个案例.在某些时候,Antlr lexer正在决定两个规则:DDT和ID.它选择DDT因为词法分析器是贪婪的.但是当匹配DDT失败时,我希望lexer回到使用ID.

只要语法保持基本相同(即词法分析器中的规则,保留在词法分析器中,并且大多数规则保持不变),我可以使用谓词或其他技巧.

理想情况下,我可以使用任何有效的Antlr代码修改DDT的词法分析器规则......并且可以完成.

我的目标语言是Java.

谢谢!

UPDATE

谢谢你们一些很棒的答案!我接受了最符合我问题的答案.我使用的实际解决方案是我自己的答案(不是接受的答案),并且有更多的答案可以奏效.读者,查看所有答案; 其中一些可能比我的更适合你的情况.

Answer 1

只要语法保持基本相同(即词法分析器中的规则,保留在词法分析器中,并且大多数规则保持不变),我可以使用谓词或其他技巧.

在这种情况下,强制词法分析器在char-stream中向前看,以确保确实"d/dt("使用了门控句法谓词.

演示:

grammar diffeq_grammar;

@parser::members {
  public static void main(String[] args) throws Exception {
    String src = 
        "d/dt(x)=a\n" +
        "a=d/dt\n" +
        "d=3\n" +
        "dt=4\n";
    diffeq_grammarLexer lexer = new diffeq_grammarLexer(new ANTLRStringStream(src));
    diffeq_grammarParser parser = new diffeq_grammarParser(new CommonTokenStream(lexer));
    parser.program();
  }
}

@lexer::members {
  private boolean ahead(String text) {
    for(int i = 0; i < text.length(); i++) {
      if(input.LA(i + 1) != text.charAt(i)) {
        return false;
      }
    }
    return true;
  }
}

program
 : (statement? NEWLINE)* EOF
 ;

statement
 : diffeq     {System.out.println("diffeq     : " + $text);}
 | assignment {System.out.println("assignment : " + $text);}
 ;

diffeq
 : DDT ID ')' '=' ID
 ;

assignment
 : ID '=' NUMBER
 | ID '=' ID '/' ID
 ;

DDT     : {ahead("d/dt(")}?=> 'd/dt(';
ID      : 'a'..'z'+;
NUMBER  : '0'..'9'+;
NEWLINE : '\r\n' | '\r' | '\n';

如果您现在运行演示:

java -cp antlr-3.3.jar org.antlr.Tool diffeq_grammar.g
javac -cp antlr-3.3.jar *.java
java -cp .:antlr-3.3.jar diffeq_grammarParser

(使用Windows时,在最后一个命令中替换:with ;)

您将看到以下输出:

diffeq     : d/dt(x)=a
assignment : a=d/dt
assignment : d=3
assignment : dt=4