Разбор ANTLR MismatchedTokenException - PullRequest
Новая
       33

Разбор ANTLR MismatchedTokenException

1 голос
/ 15 июня 2011

Я пытаюсь написать простой парсер для еще более простого языка, который я пишу.Он состоит из выражений постфикса.На данный момент у меня проблемы с парсером.Когда я запускаю его на входе 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;}
    ;

Ответы [ 2 ]

4 голосов
/ 15 июня 2011

Несколько вещей не верны:

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) 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)
    ;

, ошибки исчезнут (хотя это все равно не приведет к правильному анализу вашего ввода!).

Я понимаю, чтоэто все еще может звучать расплывчато, но объяснять (или понимать, если вы новичок во всем этом нетривиально) нетрудно.вам нужно держаться подальше от левой рекурсии, как я объяснил в # 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:

enter image description here

0 голосов
/ 15 июня 2011

Проблема в том, что правило вашего тела никогда не заканчивается, потому что оно не может соответствовать ничему. Я не запустил 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, установите точки останова на отпечатках, чтобы пройти через синтаксический анализатор: 

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());
...