はここで同じ接頭辞で生成規則に起因する紛争を減らす

Question

シフト/排除簡素化yaacファイルです：2シフト/競合を減らすがあり

%token CONTEXT_ // the corresponding string is "context" 
%token CONTEXTREF_ //"contextref" 
%token IS_   //"is" 
%token ID_L  //"id_l" 
%token ID_L1  //"id_l1" 
%token LIB_ 

%start design_file 

%% 
design_file :design_unit 
       |design_file design_unit 
       ; 

design_unit :context_cl LIB_ 
       |context_decl 
       ; 

context_cl : /* empty */ { } 
       |context_cl context_ref 
       ; 

context_decl :CONTEXT_ ID_L IS_ ';' 
       ; 

context_ref :CONTEXT_ ID_L1 '.' ID_L ';' 
       ; 

。

CONTEXT_ shift, and go to state 1 

CONTEXT_ [reduce using rule 5 (context_cl)] 

ルール5はcontext_cl : /* empty */ { }です。

一般に、これは問題ではありませんが、パーサはほとんどの場合よく機能します。 しかし、一つの奇妙な場合は、ソースファイルに対して次のように：

context id_l is ... 
... 

パーサがシフトしたが故に構文エラーの原因となる、context id_l is ...を解析するcontext_ref :CONTEXT_ ID_L1 '.' ID_L ';'を使用して、小さくなりません。

したがって、私は競合を排除する必要があります。 私はそれらが最初にを持つ規則context_declとcontext_refによって引き起こされると思います。

私の推測を検証するために、context_ref :CONTEXT_ ID_L1 '.' ID_L ';'をcontext_ref :CONTEXTREF_ ID_L1 '.' ID_L ';'に変更しました。次に、競合はなく、構文エラーもありません。

しかし、私はこのようにcontext_refを置き換えることはできません。これが標準です。

他の方法でこれらの2つの競合を回避するにはどうすればよいですか？あるいは、この種の紛争に対処するための一般的な方法はありますか？

シフト/リダクションの競合の場合、パーサーはシフトするのではなく減らすことを選択しますか？なぜなら、パーサーは常に減らすことになると思うからです。私はあなたの「断続的」構文エラーがどこから来ているか分からない

Answer 1

この競合を生じさせる基本的なパターンは：

xと y両方が同じシンボルで始まる生産を有する

union : x x_rest 
     | y_list y_rest 
y_list: /* empty */ 
     | y_list y 

。

それはy_listではなく、ゼロ以上の1または-以上y S、であれば、問題が消えることは注目に値します：限りxとyは本当に区別できるよう

y_list: y 
     | y_list y 

。 （残りの部分に応じて、いくつかの他の要件がありますが、基本的に同じプレフィックスがあればOKです。最初のトークンで継続が異なるという条件でも同じことがあります）

本当に（潜在的に空であること、またはその両方xとy）潜在的に空にy_listを必要とする、あなたはいつもnullで生産が文法のうち、潜在的に空の生産を因数分解が含まれ、排除実行する必要があります。

union : x x_rest 
     | y_rest   /* Corresponds to an empty y_list */ 
     | y_list y_rest 
y_list: y    /* As above, this list cannot be empty */ 
     | y_list y 

Answer 2

- シフトはそれがcontext_declないcontext_refを解析しようとする原因となりますよう、あなたの文法は書かれては... context id_l1 . id_lなどの入力に一致することはできません。

design_unit : context_cl LIB_ 
       | LIB_ 
       | context_decl 
       ; 

context_cl : context_ref 
       | context_cl context_ref 
       ; 

だから今：その本当に/* empty */から来て、最も簡単な修正は、そのルールを削除するには、それをリファクタリングすることです - しかし、あなたの競合が共通の接頭辞とはほとんどを持っている、と述べた

context_clは「0以上」ではなく「1以上」context_refであり、​​ルールを複製して0ケースを別々にしています。