シンプルな（？）文法でshift-reduce競合を修正する

Question

私はバイソンに文法を記述しようとしていますが、それができるかどうかはわかりません。

%token A B C D SEP 

%% 

items   : /* empty */ 
       | items_nonempty 
       ; 

items_nonempty : item 
       | items_nonempty SEP item 
       ; 

item   :  B 
       |  B  SEP D 
       |  B SEP C 
       |  B SEP C SEP D 
       | A SEP B 
       | A SEP B  SEP D 
       | A SEP B SEP C 
       | A SEP B SEP C SEP D 
       ; 

「items」はSEPトークンによって分離item要素の（空の可能）配列である。私の意図した文法はこれです

各アイテムは、SEPで区切られた順に、最大4つのトークン（A B C D）で構成されています。項目内のA、C、およびDのトークンはオプションです。

各アイテム内およびアイテム間で同じセパレータトークンSEPを再利用することに注意してください。

私は意図された文法がはっきりしていることを願っています。私はそれがあいまいではないと思うが、バイソンがそれを解析できるように十分に制限されているかどうかは不明だ。残念ながら、私のパーサーの知識はかなり錆びている。

与えられた文法を使用して、bisonは4つのシフト/リダクションの競合を報告します。 「アウトプット」を見ると、私は彼らの発生場所と理由を理解しています。私はS/Rの競合を取り除くために意図された文法をどのように書くことができますか？

私は%expect宣言を使用したくないです。同様に、私はスキャナがパーザに渡されるのではなく、セパレータトークンを消費させたくないです。

この文法をどのようにサニタイズするかについてのヒントは非常に高く評価されます。

Answer 1

文法は確かに曖昧ではなく、LL（7）であり、LRR（2）であってもLR（2）と信じています。だから、あなたがそれらのいずれかの発電機を持っていたら、それは仕事をするだろう。

lookahead-1の競合は、アイテム間およびアイテム内で同じセパレータを使用することによって発生し、セパレータまたはアイテム構造をあきらめると消滅します。

あなたができることは、異なる文法で2回解析することです。最初のパスでは、適切に配置されたセパレータを検証することができ、そして文法が第二（そしてもっと重要な）パスで

items   : 
       | items_nonempty 
       ; 
items_nonempty : item 
       | items_nonempty SEP item 
       ; 
item   : A 
       | B 
       | C 
       | D 
       ; 

のようなものかもしれない、あなたはアイテムの構造を検証します。これは可能性があります。

items   : 
       | items_nonempty 
       ; 
items_nonempty : item 
       | items_nonempty item 
       ; 
item   : B 
       | B D 
       | B C 
       | B C D 
       | A B 
       | A B D 
       | A B C 
       | A B C D 
       ; 

レクサーによってセパレータが無視されます。

上記は両方ともLALR（1）であり、前者はLL（1）であり、後者はLL（4）ですが、何らかのファクタリングによってLL（1）にすることができます。

これは、bisonまたはlexerツールが提供する特別な製品とは独立したソリューションです。私は自分たちができることを学ぶのを楽しみにしています。

Answer 2

これは1つのシフト/競合を減らすを有する：

%token A B C D SEP 

%% 

items 
    : /* empty */ 
    | items_nonempty 
    ; 

items_nonempty 
    : item 
    | items_nonempty SEP item 
    ; 

item 
    : opt_a B opt_c_d_list 
    ; 

opt_a 
    : /* Nothing */ 
    | A SEP 
    ; 

opt_c_d_list 
    : /* Nothing */ 
    | opt_c_d_list c_or_d 
    ; 

c_or_d 
    : SEP C 
    | SEP D 
    ; 

単独opt_aルールはS/Rが4から2までカウント変化の残留問題が同じSEPが後にCまたはDをsepaeratesことですB、Yaccは先読みできません。あなたは 'B SEP D SEP C'を禁止する意味チェックが必要です。上記のルールはそれを可能にします。

あなたのトークナイザを修正してSEP C？を読むときにCを返し、SEP Dを読むときにDを使うことが考えられますか？語彙のフィードバックと開始条件をflexに使用することもできます。そのため、Bを読み込むと、SEP Cが単なるCとして返され、SEP Dは単なるDとして返されます。明確な文法はありませんS/Rの競合で動作します：

%token A B C D SEP 

%% 

items 
    : /* empty */ 
    | items_nonempty 
    ; 

items_nonempty 
    : item 
    | items_nonempty SEP item 
    ; 

item 
    : opt_a B opt_c opt_d 
    ; 

opt_a 
    : /* Nothing */ 
    | A SEP 
    ; 

opt_c 
    : /* Nothing */ 
    | C 
    ; 

opt_d 
    : /* Nothing */ 
    | D 
    ; 

Answer 3

基本的な問題が書かれた文法はそれがitemの終わりを発見したときを決定する先読みの2つのトークンを必要とするので、それを減らすかあればできることです先読みの次の文字と見なされるSEPの後には、現在のアイテムの別の部分があります。

あなたが効果的に多くの先読みを取得する

• 使用btyaccやバイソンのGLRのサポートを試すことができます多数のアプローチがあります。

• 単一アイテムの任意のリストを受け入れ、次いで、少なくとも1 Bと1-4アイテムのセットにそれらを再編成し、不正な形式のセットを拒否するポストパスを使用する文法を書き込む（これはギュンターの提案である）

• シンプルSEPトークンを返すのではなく、SEPの次のトークンに応じてSEP_BEFORE_A_OR_BまたはSEP_NOT_BEFORE_A_OR_Bを返す代わりに、先読みを行うためにスキャナを使用します。

• は、スキャナでトークンを組み合わせて - 単一のトークンとして（CまたはD続くセパレータ）SEP_CとSEP_Dを返す

Answer 4

あなたは、単一のルールにあなたの他のトークン次SEPを含めることができます。非常に簡潔に書かれた、あなたの文法は次のように表現することができます

%token A B C D SEP 
%% 
items : /* empty */ | item | itemsSEP item ; 
item : a B | a b C | a b c D ; 
itemsSEP : itemSEP | itemsSEP itemSEP ; 
itemSEP : a b c d ; 
a : /* empty */ | A SEP ; 
b : B SEP ; 
c : /* empty */ | C SEP ; 
d : /* empty */ | D SEP ; 

は、だから今は、セパレータに続く項目のitemSEPを持っていますが、区切りが続いていない最後の一つをitem。それらは、それぞれが以下のセパレータを含む小文字の1文字以外の非終端記号から構成され、いくつかの引数をオプションとして扱います。 itemの最後の引数だけが、未処理の端末であり、それに続くセパレータは存在しません。

文法がLALR（1）であるため、このように表現された文法では、シフト・リダクションの競合は発生しません。すべてのステップで、たとえそのルールの主なポイントが1つを取り除いても、適用する削減を正確に知ることになります。SEPしたがって、1つのトークンをさらに先に見ることができます。