ANTLR解析MismatchedTokenException

我正在尝试为我正在编写的更简单的语言编写一个简单的解析器。它由后缀表达式组成。到目前为止，我的解析器遇到了问题。当我在输入上运行它时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;}
    ;

有几点是不正确的：

1

你已经把WS上的令牌HIDDEN通道，这使得它们无法用于解析器规则。所以所有WS你里面的令牌body规则不正确。

2

_(your latest edit removed the left-recursion issue, but I'll still make a point of it sorry, your other question has a left recursive rule (expr), so I'll leave this info in here)_

ANTLR 是一个LL解析器-generator，这样你就可以创建左递归语法。以下是左递归：

expr
  :  term term operator
  ;

term
  :  INT
  |  ID
  |  expr
  ;

因为第一个term在 - 的里面expr规则可能匹配expr统治自己。与任何 LL 解析器一样，ANTLR 生成的解析器无法处理左递归。

3

如果你修复了WS问题，你的body规则将产生以下错误消息：

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

这意味着解析器无法“看到”哪个规则INT令牌所属。这是因为您所有的body替代方案可以重复零次或多次，并且expr and nested也重复。它们都可以匹配INT，这就是 ANTLR 所抱怨的。如果您删除*是这样的：

body
    :   nested
    |   var
    |   get
    ;

// ...

expr
    :   term (term operator)
    ;

nested
    :   expr (expr operator)
    ;

错误将会消失（尽管这仍然不会导致您的输入被正确解析！）。

我意识到这可能听起来仍然含糊不清，但解释起来（或者如果您对这一切还不熟悉的话，理解一下）并不简单。

4

正确考虑递归expr inside expr，你需要远离左递归，正如我在#2。你可以这样做：

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

这仍然是不明确的，但这是在使用 LL 语法描述后缀表达式的情况下，AFAIK 不可避免的。要解决此问题，您可以在options { ... }语法部分：

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

Demo

如何解析递归表达式的一个小演示可能如下所示：

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：