文法の競合：複数のアクションが可能

Question

jison（http://zaa.ch/jison/docs/）という単純なパーサを説明文に記載して書こうとしました。

%lex 

%% 
[\s\n\t]+     return 'TK_SPACE'; 
[0-9]+("."[0-9]+)?\b  return 'TK_NUMBER'; 
[a-zA-Z]+([a-zA-Z0-9]+)?\b return 'TK_WORD'; 
<<EOF>>      return 'EOF'; 

/lex 

%start document 

%% 

document 
    : nodes EOF 
    { console.log($1); } 
    | EOF 
    ; 

nodes 
    : nodes node 
    { $1.push($2); $$ = $1; } 
    | node 
    { $$ = [$1]; } 
    ; 

node 
    : text 
    ; 

text 
    : text text_element 
    { $$ = $1 + $2; } 
    | text_element 
    ; 

text_element 
    : TK_NUMBER 
    | TK_WORD 
    | TK_SPACE 
    ; 

この文章は警告付きでコンパイルされています。

Conflict in grammar: multiple actions possible when lookahead token is TK_SPACE in state 5 
- reduce by rule: node -> text 
- shift token (then go to state 9) 
Conflict in grammar: multiple actions possible when lookahead token is TK_WORD in state 5 
- reduce by rule: node -> text 
- shift token (then go to state 8) 
Conflict in grammar: multiple actions possible when lookahead token is TK_NUMBER in state 5 
- reduce by rule: node -> text 
- shift token (then go to state 7) 

States with conflicts: 
State 5 
    node -> text . #lookaheads= TK_SPACE TK_WORD TK_NUMBER EOF 
    text -> text .text_element #lookaheads= EOF TK_NUMBER TK_WORD TK_SPACE 
    text_element -> .TK_NUMBER 
    text_element -> .TK_WORD 
    text_element -> .TK_SPACE 

しかし、テキストを解析しようとするとうまくいきます。これはコードのフルバージョンではなく、テキスト付きのバージョンです。私はnodeにノードを追加したいです。

Answer 1

問題は、文法があいまいであることです。nodesは、1のシーケンスまたはセパレータなしのモードnodeで構成されています。 nodeは、textであり、これもまた、セパレータを含まない1つまたは複数のものからなる。したがって、nodeが終了し、次の処理が始まる時期を知らせる方法はありません。

例として、入力したシーケンスが3 text_elementsの場合、すべてが3のnodeという単一のものでも、3つずつのnodeのものもあります。

Bisonは常にshiftoverを優先することでこの競合を解決します。これは常にtextオブジェクトを大きくして、nodes: nodes nodeというルールを決して縮小しないようにし、文法から削除するほうが好ましいでしょう。これは純粋なあいまいさ（先読み問題ではない）なので、結果として得られる文法は同じ言語にマッチするので、問題はないかもしれません。私はjison（またはあなたが実際に使っているパーサージェネレータ）は同じものと仮定します。

一般に、生成されたパーサーによって解析された文法は、指定した文法ではないため、競合が問題になります。生成されたパーサーによって実際にどのような文法が解析されているかを把握することは重要ではなく、shoft-reduce構文解析がどのように機能するか、そして実際にパーサージェネレータによって生成される状態を慎重に理解する必要があります。情報はすべて.outputファイル（-vのbisonによって生成されます - 他の発電機は異なるかもしれません）にありますが、それを読んで理解する必要があります。