python - ANTLR 解析の MismatchedTokenException

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

score 4 · Accepted Answer

正しくない点がいくつかあります。

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選択肢が 0 回以上繰り返される可能性があり、exprandnestedも繰り返されるという事実によるものです。そして、それらはすべてに一致する可能性がありINT、これは ANTLR が不満を言っていることです。を削除すると、次*のようになります。

body
    :   nested
    |   var
    |   get
    ;

// ...

expr
    :   term (term operator)
    ;

nested
    :   expr (expr operator)
    ;

エラーは消えます (ただし、それでも入力が適切に解析されるわけではありません!)。

これはまだ曖昧に聞こえるかもしれませんが、説明するのは簡単ではありません (または、これらすべてに慣れていない場合は理解できます)。

4

expr内部の再帰を適切に説明するには、 #2exprで説明したように、左再帰を避ける必要があります。次のようにできます。

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)

次の出力が生成されます。

これは、次の AST に対応します。

ここに画像の説明を入力

score -1 · Accepted Answer

問題は、何も一致しないことが許可されているため、body ルールが終了しないことです。私はANTLRを起動しませんでした。本当にそれをいじるのが好きではありません。代わりに、C ++で文法を書き直し（AXパーサージェネレーターを使用）、一致をトレースするためにprintステートメントを追加し、解析から次の結果を得ました"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());

python - ANTLR 解析の MismatchedTokenException

2 に答える 2

1

2

3

4

デモ

Related

Reference