c++ - Lemon Parser は物事をスキップします (または私の誤解)

Question

詳細情報を更新

Lemon を使用して要素の単純な配列を解析する際に問題が発生しています。誰かが私を啓発できますか??

この文字列 "[0 0 612 792][100 200]" を mygrammar 定義で解析しようとしていますが、パーサーは常に最初の配列要素をスキップし、最後の要素を複製します...任意のアイデア??

文法ファイルは

%token_type { char* }

%include {
    #include <assert.h>
}

%parse_accept { printf("The parser has completed successfully.\n"); }
%syntax_error { fprintf(stderr, "Syntax Error\n"); }
%parse_failure { fprintf(stderr, "Parse failure\n"); }

%start_symbol program

array_value ::= INT_LITERAL(A). {printf("Av: %s\n", A);} 

array_value_list ::=.
array_value_list ::= array_value_list array_value.

array_declaration ::= LBRACKET array_value_list RBRACKET.

array_list ::= array_declaration.
array_list ::= array_list array_declaration.

program ::= array_list END_TOKEN.

re2c を使用してトークンを取得し、各トークンのパーサーを呼び出すコードは次のとおりです。

  while(token = scan(&scanner, buff_end)) { 
    // Send strings to the parser with NAME tokens  

    if(token == INT_LITERAL) {
      name_length = scanner.cur - scanner.top;
      strncpy(name_str, scanner.top, name_length);
      name_str[name_length] = '\0';
      //printf("Token:Pre: %s\tName: %s\n", tokenStr(token),name_str);
      Parse(parser, token, name_str);
    }
    else {
      //printf("Token: %s\n", tokenStr(token));
      Parse(parser, token, 0);
    }
    // Execute Parse for the last time
    if(token == END_TOKEN) {
      Parse(parser, 0, NULL);
      break;
    }
  }

入力文字列 "[ 0 -100 612 792][100 200]" の場合、出力は次のようになります。

Av: -100
Av: 612
Av: 792
Av: 792
Av: 200
Av: 200

お気づきのとおり、最初の要素は表示されず、最後の要素が複製されています。

レモンからの文法は次のとおりです。

State 0:
          array_declaration ::= * LBRACKET array_value_list RBRACKET
          array_list ::= * array_declaration
          array_list ::= * array_list array_declaration
          program ::= * array_list END_TOKEN

                      LBRACKET shift        3      
             array_declaration shift        1        /* because array_declaration==array_list */
                    array_list shift        1      
                       program accept

State 1:
          array_declaration ::= * LBRACKET array_value_list RBRACKET
          array_list ::= array_list * array_declaration
          program ::= array_list * END_TOKEN

                      LBRACKET shift        3      
                     END_TOKEN shift        4      
             array_declaration shift-reduce 5      array_list ::= array_list array_declaration

State 2:
          array_value ::= * INT_LITERAL
          array_value_list ::= array_value_list * array_value
          array_declaration ::= LBRACKET array_value_list * RBRACKET

                   INT_LITERAL shift-reduce 0      array_value ::= INT_LITERAL
                      RBRACKET shift-reduce 3      array_declaration ::= LBRACKET array_value_list RBRACKET
                   array_value shift-reduce 2      array_value_list ::= array_value_list array_value

State 3:
      (1) array_value_list ::= *
          array_value_list ::= * array_value_list array_value
          array_declaration ::= LBRACKET * array_value_list RBRACKET

              array_value_list shift        2      
                     {default} reduce       1      array_value_list ::=

State 4:
      (6) program ::= array_list END_TOKEN *

                             $ reduce       6      program ::= array_list END_TOKEN

----------------------------------------------------
Symbols:
    0: $:
    1: INT_LITERAL
    2: LBRACKET
    3: RBRACKET
    4: END_TOKEN
    5: error:
    6: array_value: INT_LITERAL
    7: array_value_list: <lambda> INT_LITERAL
    8: array_declaration: LBRACKET
    9: array_list: LBRACKET
   10: program: LBRACKET

サンプル文字列の出力トレースは次のとおりです。

T__Input 'LBRACKET'
T__Shift 'LBRACKET', go to state 3
T__Return. Stack=[LBRACKET]
T__Input 'INT_LITERAL'
T__Reduce [array_value_list ::=], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'RBRACKET'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'RBRACKET'
T__Return. Stack=[LBRACKET array_value_list RBRACKET]
T__Input 'LBRACKET'
T__Reduce [array_declaration ::= LBRACKET array_value_list RBRACKET], go to state 0.
T__Shift 'array_declaration', go to state 1
T__Shift 'LBRACKET', go to state 3
T__Return. Stack=[array_declaration LBRACKET]
T__Input 'INT_LITERAL'
T__Reduce [array_value_list ::=], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[array_declaration LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[array_declaration LBRACKET array_value_list INT_LITERAL]
T__Input 'RBRACKET'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'RBRACKET'
T__Return. Stack=[array_declaration LBRACKET array_value_list RBRACKET]
T__Input 'END_TOKEN'
T__Reduce [array_declaration ::= LBRACKET array_value_list RBRACKET], go to state 1.
T__Shift 'array_declaration'
T__Reduce [array_list ::= array_list array_declaration], go to state 0.
T__Shift 'array_list', go to state 1
T__Shift 'END_TOKEN', go to state 4
T__Return. Stack=[array_list END_TOKEN]
T__Input '$'
T__Reduce [program ::= array_list END_TOKEN], go to state 0.
T__Accept!
T__Return. Stack=]

私はこのエラーで立ち往生しています。これは、理解できない概念エラーであると確信しています。どんな助けでも大歓迎です。

ありがとう

score 2 · Accepted Answer

name_strスキャナーコードにの定義を示していませんが、の配列である可能性が高いようですchar。name_lengthその場合、バッファーサイズよりも小さいことを確認しないため、バッファーオーバーランの危険があります。さらに、コピーする文字列に NUL 文字がないことが既にわかっているため、memcpy代わりに使用することもできます。strncpyしかし、実際にはどちらも問題ではありません。問題は、すべてのトークンを同じバッファーにコピーしていることです。

パーサーに渡すのは、NUL で終わる文字列のアドレスです。パーサーは文字列をコピーしません。アドレスをトークンのセマンティック値として格納するだけです。つまり、パーサーは、少なくとも解析が完了するまで、渡されたトークン文字列を所有していると想定します。

しかし、実際には、文字バッファー ( name_str) はスキャナーによって所有されており、トークンをパーサーにプッシュすると、文字バッファーを自由に使用できると見なされます。これは、バッファを次のトークンで上書きすることです。

バイソンとは異なり、lemon は先読みが問題にならない場合、すぐには減少しません。bison は、リテラルが表示されるとすぐに還元INT_LITERALさarray_valueれます。これは、還元が先読みに依存しないためです。しかし、lemon には常に先読みトークンがあるため、次のトークンを受け取るまでは還元INT_LITERALされません。array_value残念ながら、次のトークンもである場合INT_LITERAL、リダクションが発生する前に次のトークンが文字バッファーを上書きしてしまうため、リダクションのアクションによって次のトークンの文字列が出力されます。次のトークンがの場合]、文字バッファーはスキャナーによって上書きされないため、その場合、前のトークンの削減によって既に印刷されていても、現在のトークンが印刷されます。

一般に、スキャナーには、パーサーがトークン値を必要とする期間を知る方法がありません。その問題のある環境に対する適切な所有権ポリシーは 2 つだけです。

スキャナーは所有権を保持します。値を保持する必要がある場合、パーサーはコピーを作成する必要があります。
スキャナーは所有権をパーサーに渡します。パーサーは、トークンの処理が完了したときにトークンを明示的に解放する必要があります。

最初のポリシーは、2 つのコンポーネントがリソース管理プロトコルに同意する必要がないため、よりクリーンです。ただし、パーサージェネレーターには、そのポリシーの実装を可能にするメカニズムが含まれていない可能性があります。これは、パーサー関数の上部で何らかのアクションを実行する必要があるためです。

したがって、2 番目のポリシーを使用する必要があります。スキャナーは、新しく割り当てられたメモリにトークン文字列のコピーを作成し、このメモリをその所有権と共にパーサーに渡して、パーサーが (最終的に) コピーを解放する必要があります。これは、同じ理由で、ほとんどの機能する bison パーサーで使用されるのと同じプロトコルであり、コピーが作成されないときに発生するさまざまなエラーは、おそらく最も一般的なあいまいな bison エラーです。

もちろん、この単純なケースでは、スキャナに文字列を整数に変換させることで、メモリ管理の問題を回避できます。

score 0 · Accepted Answer

指定したパーサー定義からは Lemon パーサーを生成できません。array_value再帰リストの終端要素をarray_value_list空にすることができます。パーサーは、このルールを無限に減らすことができ、解析の競合を報告します。

競合を解決するために、空の要素ではなく空のリストルールの概念に切り替えます。これは、レモンのドキュメントからリストの推奨される左再帰定義です。

list ::= .
list ::= list element.

このパターンをパーサーに適用すると、次の結果が得られます。

array_value ::= INT_LITERAL(A). {printf("Array value: %s\n", A);}
array_value_list ::= .
array_value_list ::= array_value_list array_value.
init_array ::=. {printf("Init Array\n");}
end_array ::=. {printf("End Array\n");}
array_declaration ::= init_array LBRACKET array_value_list RBRACKET end_array.
array_list ::= array_declaration.
array_list ::= array_list array_declaration.
program ::= array_list END_TOKEN.

c++ - Lemon Parser は物事をスキップします (または私の誤解)

詳細情報を更新

2 に答える 2

Related

Reference