6

私はJison（Bison）を使用して単純なマークアップ言語を作成しています。私は明らかにこれに慣れていませんが、わずかなバリエーションが非常にうまく機能しています。S/Rの競合の原因がわかりません。

'Text'が2つのレクサーアクション（開始条件が異なる）によって返されることは問題ではないようです。文法のルールが少なくなり、ユーザーへのエラーメッセージが一貫しているため、これが気に入っています。コンテキストに関係なく「テキスト」ルールを共通にすることを試みました。また、各トークンに異なる名前を付けることも試みましたが、すべてが一緒になっている場合、S/R競合には影響がないようです。

パーサーは、プレーンテキスト、サブ配列、およびさまざまな特殊ノードを含むjsonオブジェクトを作成することを目的としています。

仕様：

/* lexical grammar */
%lex

%s bracketed

%%

<bracketed>(\\.|[^\\\,\[\]])+       { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; }
<INITIAL>(\\.|[^\\\[])+             { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; }
"["                                 { this.begin('bracketed'); return '['; }
"]"                                 { this.popState(); return ']'; }
","                                 return ','
<<EOF>>                             return 'END'

/lex

%start template

%%    

template
    : sentence END
    ;

sentence
    : /* empty */
    | sentence Text
    | sentence '[' ']'
    | sentence '[' dynamic ']'
    ;

dynamic
    : sentence
    /*| dynamic ',' sentence*/
    ;

警告：

Conflict in grammar: multiple actions possible when lookahead token is ] in state 5
- reduce by rule: sentence ->
- shift token (then go to state 6)

States with conflicts:
State 5
  sentence -> sentence [ .] #lookaheads= END Text [ ]
  sentence -> sentence [ .dynamic ] #lookaheads= END Text [ ]
  dynamic -> .sentence #lookaheads= ]
  sentence -> . #lookaheads= ] Text [
  sentence -> .sentence Text
  sentence -> .sentence [ ]
  sentence -> .sentence [ dynamic ]

ジェネレータアルゴリズムが異なれば、多かれ少なかれ問題がありますが、すべて問題があるようです。

ありがとう！

4

1 に答える 1

17

競合は、基本的に次の2つのルールから発生します。

sentence: sentence '[' Text ']'
        | sentence '[' sentenceList ']'

その理由は、asentenceとaを確認[し、次のトークンがであるのを確認した後Text、パーサーは、をシフトして最初のルールに一致させるか、それを2番目のルールに一致させるための開始としてText扱うかを認識しないためです。TextsentenceList

2トークン先読みを使用するパーサージェネレーターがある場合、これは問題にはなりませんが、bisonはLALR（1）です（1は1トークン先読みです）。

試すことができることがいくつかあります。

  • レクサーで追加の先読みを行い、Text-followed-by-]とText-not-followed-by-]を2つの異なるトークンとして区別してから、これらのトークンの両方を使用するようにルールを書き直します。

  • バイソンの％glr-parser機能を使用して、GLRパーサーを使用します。これにより、文が双方向に解析され、後で一致しない文が破棄されます

  • 文法をリファクタリングして、2トークンの先読みを必要としないようにします。

あなたのケースで機能するリファクタリングの1つは、sentenceルールを書き直して、すべてを左再帰ではなく右再帰にすることです。

sentence: /* empty */
        | Text sentence 
        | '[' ']' sentence
        | '[' Text ']' sentence
        | '[' sentenceList ']' sentence
        ;

これにより、ルールのnull削減でsentence始まる（またはsentenceなどで始まる他のルール）が回避されます。したがって、パーサーは、問題のあるケースでは、次のトークンが表示されるまで削減を延期して、aを自由にシフトできます。ただし、基本的に入力全体をパーサースタックにシフトし、一度に1文ずつ減らすパーサーになるため、メモリ使用の影響があります。sentenceListsentence: /*empty*/Text

あなたができるもう一つのリファクタリングは、[Text]と[]コンストラクトを[sentenceList]：に含めることです。

sentence: /* empty */
        | sentence Text 
        | sentence '[' sentenceList ']'
        ;

sentenceList: sentence
            | sentenceList ',' sentence

したがって、asentenceListは（2つ以上ではなく）コンマで区切られた1つ以上の文であり、sentence '[' sentenceList ']'ルールのアクションでは、sentenceListが2つ以上の文であるかどうかを確認し、適切に動作します。

于 2012-10-03T22:22:39.497 に答える