文法スペックはシフト/競合を減らすことを解決します

StackOverflow https://stackoverflow.com//questions/12715961

質問

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

「テキスト」が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 ]
.

異なる発電機アルゴリズムには多かれ少なかれ問題がありますが、それらはすべて問題を抱えているようです。

ありがとう！

役に立ちましたか？

解決

紛争は基本的にこれら2つの規則から来ます：

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

sentenceと[を参照して、Textである次のトークンを見ると、パーサーはTextをシフトし、最初のルールに一致させるか、そのTextを扱うかどうかをわからないためです。 sentenceListは2番目の規則を一致させるために行く。

2トークンルックアヘッドを使用するパーサージェネレータを持っていた場合、これは問題にならないでしょうが、Bisonはlalr（1）です（1）（1が1つのトークンルックアヘッド）。

試してみることができるいくつかのものがあります：

  • は、2つの異なるトークンとしてテキストに続いてテキストを区別し、次にこれらのトークンの両方を使用するようにルールを書き換えるために、LexerのLookAhakeadをテキストに従って区別します。

  • Bisonの％GLR-Parser機能を使用してGLRパーサーを使用します。これは文章を解析し、後で

    • と一致しないものを捨てます。

  • 文法をリファクタリングして、2トークンルックアヘッドを必要としない。

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

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

これは、sentenceルールのNULLの削減で、sentence（またはsentenceListなどのsentence: /*empty*/で始まる他の任意のルール）を回避します。そのため、パーサーは、次のトークンを見るまで減少を延期する問題のある場合には、Textを自由にシフトさせることができます。ただし、入力全体をパーサスタックに基本的にシフトさせ、次に一度に1文を短くするパーサーが生じるので、メモリを使用します。

別のリファクタリングは、[Text]および[]コンストラクトを[sentenceList]：

にサブ化することです。 
sentence: /* empty */
        | sentence Text 
        | sentence '[' sentenceList ']'
        ;

sentenceList: sentence
            | sentenceList ',' sentence
.

だからsentenceListは、（2つ以上の）カンマで区切られた1つ以上の文で、sentence '[' sentenceList ']'ルールのアクションでは、sentenceListが2つ以上の文であるかどうかを確認して適切に機能します。 。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top