1

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

2 回答 2

4

有几件事是不正确的：

1

您已将WS令牌放在HIDDEN通道上，这使得它们无法用于解析器规则。因此WS，您的规则中的所有标记body都不正确。

2

_（您的最新编辑删除了左递归问题，但我仍然会指出，抱歉，您的另一个问题有左递归规则（expr），所以我会在此处留下此信息）_

ANTLR 是一个LL 解析器生成器，因此您可以创建左递归语法。以下是左递归的：

expr
  :  term term operator
  ;

term
  :  INT
  |  ID
  |  expr
  ;

因为规则中的第term一个expr可能匹配expr规则本身。与任何 LL 解析器一样，ANTLR 生成的解析器无法处理左递归。

3

如果您解决WS问题，您的body规则将产生以下错误消息：

(1/7) 决策可以使用多种选择来匹配诸如“INT”之类的输入

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

body
    :   nested
    |   var
    |   get
    ;

// ...

expr
    :   term (term operator)
    ;

nested
    :   expr (expr operator)
    ;

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

我意识到这听起来可能仍然含糊不清，但解释起来并非易事（如果您不熟悉这一切，也可以理解）。

4

要正确考虑递归exprinside expr，您需要避免左递归，正如我在#2中解释的那样。你可以这样做：

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

这仍然是模棱两可的，但这是在使用 LL 语法描述后缀表达式的情况下，不可避免的 AFAIK。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：

在此处输入图像描述

于 2011-06-15T19:16:44.273 回答
-1

问题是您的主体规则永远不会终止，因为它不允许匹配任何内容。我没有启动 ANTLR，我真的不喜欢弄乱它，而是用 C++ 重写了你的语法（使用 AX 解析器生成器），添加了打印语句来跟踪匹配并从解析中得到以下结果"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

如果您有兴趣调试此测试用例，AX 语法如下所示，在 prints 处设置断点以单步执行解析器：

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());
于 2011-06-15T18:59:21.717 回答