首页 文章

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

提问于
浏览 次
5

似乎有时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';

当使用这个语法时，词法分析器 grab 第一个“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

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

antlr

3 回答

  • 5

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

    在这种情况下，强制词法分析器在char-stream中向前看，以确保使用gated syntactic predicate确实存在 "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时，在最后一个命令中用 ; 替换 : ）

    您将看到以下输出：

    diffeq     : d/dt(x)=a
assignment : a=d/dt
assignment : d=3
assignment : dt=4
    回复于
  • 3

    虽然考虑到项目中的大量工作代码，这不是您要做的，但您仍应考虑更彻底地分离解析器和词法分析器 . 我最好让解析器和词法分析器做他们最擅长的事情，而不是将它们放在一起 . 出现错误的最明显迹象是 ( 和 ) 令牌之间缺乏对称性：一个是复合令牌的一部分，而另一个是独立令牌 .

    如果重构是一个选项，你可以像这样更改解析器和词法分析器：

    grammar diffeq_grammar;

program :   (statement? NEWLINE)* EOF; // <-- You forgot EOF

statement
    :   diffeq
    |   assignment;

diffeq  :   D OVER DT OPEN id CLOSE EQ id; // <-- here, id is a parser rule

assignment
    :   id EQ NUMBER
    |   id EQ id OVER id
    ;

id  : ID | D | DT; // <-- Nice trick, isn't it?

D       : 'D';
DT      : 'DT';
OVER    : '/';
EQ      : '=';
OPEN    : '(';
CLOSE   : ')';
ID      : 'a'..'z'+;
NUMBER  : '0'..'9'+;
NEWLINE : '\r\n'|'\r'|'\n';

    您可能需要启用回溯和memoization才能工作（但尝试编译它而不先回溯） .

    回复于
  • 1

    这是我最终使用的解决方案 . 我知道这违反了我的一个要求：在解析器中保持词法分析器和解析器规则中的词法分析器规则，但事实证明将DDT移动到ddt不需要更改我的代码 . 此外，dasblinkenlight在他的回答和评论中提出了关于不匹配括号的一些好点 .

    grammar ddt_problem;

program :   (statement? NEWLINE)*;

statement
    :   diffeq
    |   assignment;

diffeq  :   ddt ID ')' '=' ID;

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

ddt :   ( d=ID ) { $d.getText().equals("d") }? '/' ( dt=ID ) { $dt.getText().equals("dt") }? '(';
ID  :   'a'..'z'+;
NUMBER  :   '0'..'9'+;
NEWLINE :   '\r\n'|'\r'|'\n';
    回复于

相关问题