匹配相似字符串的 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”。词法分析器选择贪婪......但它几乎不知道，输入流中后面的几个字符没有“(”。当词法分析器查找丢失的“(”它抛出一个 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';

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

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

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

我的目标语言是 Java。

谢谢!

更新

谢谢各位大大的回答!!我接受了最适合我的问题的答案。我使用的实际解决方案是在我自己的答案中(不是接受的答案)，还有更多可能有效的答案。读者，请查看所有答案；其中一些可能比我的更适合您的情况。

Answer 1

I'm okay with using predicates or other tricks as long as the grammar remains basically the same (i.e., the rules in the lexer, stay in the lexer. And most rules are left untouched.).

在这种情况下，强制词法分析器在字符流中向前看以确保确实存在 "d/dt("使用 gated syntactic predicate .

一个演示:

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 时，将最后一个命令中的 : 替换为 ;)

您将看到以下输出:

diffeq : d/dt(x)=a
赋值:a=d/dt
分配:d=3
分配:dt=4