ANTLR 解析不匹配令牌异常

Question

我正在尝试为我自己写的一个简单语言编写一个解析器。这个语言是由后缀表达式组成的。目前，我在解析器上遇到了一些问题。当我用输入 2 2 * test >> 运行它时，出现了一个叫做 MismatchedTokenException 的错误。

另外，我该如何实现一个递归的后缀解析器呢？

这是我的代码：

grammar star;

options {
    language=Python;
    output=AST;
    ASTLabelType=CommonTree;
}

tokens {DECL;}
//start
//  :   decl ;
//decl
//  :   type ID -> ^(DECL type ID)
//  ;

program
    :   (body)+
    ;

body    :   (nested WS)*
    |   (var WS)*
    |   (get WS)*
    ;

var
    :   nested ID '>>'
    ;

get
    :   ID '<<'
    ;

//expressions

term
    :   INT
    ;

expr
    :   term (term operator)*
    ;

nested
    :   expr (expr operator)*
    ;

operator 
    :   ('*' | '+' | '/' | '%' | '-')
    ;

ID
    :   ('a'..'z' | 'A'..'Z') ('a..z' | '0'..'9' | 'A'..'Z')*
    ;

INT
    :   '0'..'9'+
    ;

WS
    :   (' ' | '\n' | '\t' | '\r') {$channel=HIDDEN;}
    ;

Answer 1

问题在于你的规则没有结束条件，因为它可以匹配到什么都不匹配的情况。我没有使用ANTLR，因为我不太喜欢弄这个，所以我用C++重写了你的语法（使用AXE解析器生成器），并添加了一些打印语句来跟踪匹配的过程，结果在解析"2 2 * test >>"时得到了以下结果：

parsed term: 2
parsed expr: 2
parsed nested: 2
parsed term: 2
parsed expr: 2
parsed nested: 2
parsed body: 2 2
parsed body:
parsed body: ... here goes your infinite loop

如果你想调试这个测试案例，下面是AXE的语法，可以在打印语句处设置断点，逐步查看解析过程：

using namespace axe;
typedef std::string::iterator It;

auto space = r_any(" \t\n\r");
auto int_rule = r_numstr();
auto id = r_ident();
auto op = r_any("*+/%-");
auto term = int_rule 
    >> e_ref([](It i1, It i2)
{ 
    std::cout << "\nparsed term: " << std::string(i1, i2); 
});
auto expr = (term & *(term & op)) 
    >> e_ref([](It i1, It i2)
{ 
    std::cout << "\nparsed expr: " << std::string(i1, i2); 
});
auto nested = (expr & *(expr & op))
    >> e_ref([](It i1, It i2)
{ 
    std::cout << "\nparsed nested: " << std::string(i1, i2); 
});
auto get = (id & "<<")  
    >> e_ref([](It i1, It i2)
{ 
    std::cout << "\nparsed get: " << std::string(i1, i2); 
});
auto var = (nested & id & ">>")  
    >> e_ref([](It i1, It i2)
{ 
    std::cout << "\nparsed var: " << std::string(i1, i2); 
});
auto body = (*(nested & space) | *(var & space) | *(get & space))
     >> e_ref([](It i1, It i2)
{ 
    std::cout << "\nparsed body: " << std::string(i1, i2); 
});
auto program = +(body)
    | r_fail([](It i1, It i2) 
{
    std::cout << "\nparsing failed, parsed portion: " 
        << std::string(i1, i2);
});
// test parser
std::ostringstream text;
text << "2 2 * test >>";
std::string str = text.str();
program(str.begin(), str.end());

Answer 2

有几个地方不太对：

1

你把 WS 这个标记放在了 HIDDEN 通道上，这样就让解析规则无法使用它。所以在你的 body 规则中的所有 WS 标记都是错误的。

2

_(你最近的编辑解决了左递归的问题，但我还是想提一下 抱歉，你的 另一个问题 里有一个左递归的规则 (expr)，所以我还是把这些信息留在这里)_

ANTLR 是一个 LL 解析器生成器，所以你不能创建左递归的语法。下面这个就是左递归：

expr
  :  term term operator
  ;

term
  :  INT
  |  ID
  |  expr
  ;

因为在 expr 规则中的第一个 term 可能会匹配到 expr 规则本身。像所有的 LL 解析器一样，ANTLR 生成的解析器无法处理左递归。

3

如果你解决了 WS 的问题，你的 body 规则会产生以下错误信息：

(1/7) Decision can match input such as "INT" using multiple alternatives

这意味着解析器无法“看出” INT 这个标记属于哪个规则。这是因为你所有的 body 选项可以重复零次或多次，而 expr 和 nested 也可以重复。而且它们都可以匹配到一个 INT，这就是 ANTLR 抱怨的地方。如果你像这样去掉 *：

body
    :   nested
    |   var
    |   get
    ;

// ...

expr
    :   term (term operator)
    ;

nested
    :   expr (expr operator)
    ;

错误就会消失（虽然这仍然不会让你的输入被正确解析！）。

我知道这可能听起来还是有点模糊，但要解释清楚并不简单（如果你对这些内容不熟悉的话）。

4

为了正确处理在 expr 内部的递归 expr，你需要避免左递归，正如我在#2中解释的那样。你可以这样做：

expr
  :  term (expr operator | term operator)*
  ;

这仍然是模糊的，但在用 LL 语法描述后缀表达式时，这是不可避免的。为了解决这个问题，你可以在语法的 options { ... } 部分启用全局回溯：

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

演示

一个解析递归表达式的小演示可能是这样的：

grammar star;

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

parse
  :  expr EOF -> expr
  ;

expr
  :  (term -> term) ( expr2 operator -> ^(operator $expr expr2) 
                    | term operator  -> ^(operator term term)
                    )*
  ;

expr2 
  :  expr
  ;

term
  :  INT
  |  ID
  ;

operator 
  :  ('*' | '+' | '/' | '%' | '-')
  ;

ID
  :  ('a'..'z' | 'A'..'Z') ('a..z' | '0'..'9' | 'A'..'Z')*
  ;

INT
  :  '0'..'9'+
  ;

WS
  :  (' ' | '\n' | '\t' | '\r') {$channel=HIDDEN;}
  ;

测试脚本：

#!/usr/bin/env python
import antlr3
from antlr3 import *
from antlr3.tree import *
from starLexer import *
from starParser import *

def print_level_order(tree, indent):
  print '{0}{1}'.format('   '*indent, tree.text)
  for child in tree.getChildren():
    print_level_order(child, indent+1)

input = "5 1 2 + 4 * + 3 -"
char_stream = antlr3.ANTLRStringStream(input)
lexer = starLexer(char_stream)
tokens = antlr3.CommonTokenStream(lexer)
parser = starParser(tokens)
tree = parser.parse().tree 
print_level_order(tree, 0)

产生以下输出：

-
   +
      5
      *
         +
            1
            2
         4
   3

这对应于以下的抽象语法树（AST）：