1

以下は、私の問題を説明する Bison の文法です。私が使っている実際の文法はもっと複雑です。

%glr-parser
%%
s : e | p '=' s;
p : fp | p ',' fp;
fp : 'x';
e : te | e ';' te;
te : fe | te ',' fe;
fe : 'x';

入力の例は次のとおりです。

x
x = x
x,x = x,x
x,x = x;x
x,x,x = x,x;x,x
x = x,x = x;x

私が求めているのは、「=」の左側の x が右側のものとは異なる方法で解析されることです。ただし、'=' 記号の右側に表示される可能性のある有効な「式」のセットは、左側のものよりも大きくなります (';' のため)。

Bison はメッセージを出力します (入力ファイルは test.y です):

test.y: conflicts: 1 reduce/reduce.

この問題を回避する方法があるはずです。C でも同様の状況があります。以下のプログラムは、エラーなしで gcc を通過します。

int main(void) {
  int x;
  int *px;
  x;
  *px;
  *px = x = 1;
}

この場合、'px' と 'x' は、'=' 記号の左側または右側のどちらに表示されるかによって、異なる扱いを受けます。

4

2 に答える 2

2

あなたの文法におけるreduce-reduceの競合は、コンテキストから来ています:

... = ... x ,

この時点で、パーサーは が であるかxであるfeかを判断する必要がfpあり、1 つのシンボルの先読みでは判断できません。実際、有限の先読みでは知ることができず、 、または入力の終わりにx ,遭遇することなく、そのポイントを何度でも繰り返すことができ、そのいずれかが答えを明らかにします。=;

これは、単一シンボルの先読みで解決できる C の問題とはまったく同じではありません。ただし、C の例は、SLR(1) 文法が LALR(1) 文法よりも強力ではない理由の古典的な例です。これは、ドラゴン ブックでその目的のために使用されています。同様に問題のある文法は、 LALR(1) および LR(1); バイソンのマニュアル（こちら）で見つけることができます：

 def: param_spec return_spec ',';

 param_spec: type | name_list ':' type;

 return_spec: type | name ':' type;

 type: "id";
 name: "id";
 name_list: name | name ',' name_list;

(バイソンのマニュアルでは、LALR(1) 文法でこの問題を解決する方法が説明されていますが、GLR 文法を使用することは常に可能です。)

GLR 文法を使用せずにこのような競合を解決するための鍵は、パーサーに時期尚早の決定を強制しないようにすることです。

たとえば、左辺値と右辺値を構文的に区別することは伝統的であり、一部の言語は引き続きそうしています。ただし、C と C++ にはありません。これは、左辺値として機能する関数を定義できるため、C++ の非常に強力な機能であることが判明しました。

C では、文法を少し単純化するだけだと思います。C 文法では、単項演算子の結果を代入演算子の左側に表示できますが、単項演算子は実際には左辺値 ( *v, v[expr]) と右辺値の混合です。 ( sizeof v、f(expr))。文法は 2 種類の単項演算子を区別できましたが、実際の制限を解決できませんでした。つまり、変更可能な左辺値のみが代入演算子の左側に表示される可能性があります。

C++ では、代入演算子の左側に任意の式を指定できます (一部は括弧で囲む必要があります)。したがって、以下は完全に合法です。

(predicate(x) ? *some_pointer : some_variable) = 42;

あなたの場合、両方の非終端記号が同じ派生セットを生成するため、に置き換えることteで構文的に競合を解決できます。p左側の式が右側の式の厳密なサブセットであるという完全な文法の場合を除いて、これはおそらく一般的な解決策ではありません。完全な文法では、最終的に 3 種類の表現 (左のみ、右のみ、共通) になる可能性があり、文法がかなり複雑になる可能性があり、セマンティック分析のために解決策を残す方が簡単であることが判明する可能性があります (さらに、 C++ の場合、驚くほど便利です)。

于 2013-09-22T15:38:39.840 に答える
2

を使用して%glr-parserいるため、reduce/reduce の競合を「修正」する必要はありません。Bison は 1 つあると言うだけなので、文法があいまいである可能性があることがわかります。そのため、%dprecまたは%mergeディレクティブを使用してあいまいさの解決を追加する必要がある場合があります。しかし、あなたの場合、文法は曖昧ではないので、何もする必要はありません。

競合はエラーではなく、文法が LALR(1) ではないことを示しているだけです。

于 2013-09-22T08:41:12.470 に答える