0

小さな Visual Basic 言語用のパーサーを作成しようとしています。そして、次のシフト/削減の競合を解決できません。私はこれらのルールを持っています:

simple_type_name:
    qualified_type_name
    | primitive_type_name;

qualified_type_name:
    ID
    | qualified_type_name PERIOD ID;

primitive_type_name: BOOLEAN|CHAR|STRING|BYTE|SBYTE|USHORT|SHORT|UINTEGER|INTEGER|ULONG|LONG|SINGLE|DOUBLE;

バイソンは私にこう言います：

simple_type_name  ->  qualified_type_name .   (rule 20)
qualified_type_name  ->  qualified_type_name . PERIOD ID   (rule 23)

PERIOD  shift, and go to state 41

PERIOD  [reduce using rule 20 (simple_type_name)]
$default reduce using rule 20 (simple_type_name)

では、この紛争の正しい解決策は何ですか?

4

1 に答える 1

2

simple_type_nameの後に .が続く文法には、他の規則が必要PERIODです。何かのようなもの：

expression: simple_type_name PERIOD expression

多分？

PERIOD問題は、 の後に続くものが、これを修飾型名にする単純IDな名前なのか、それとも単純な型名にする何か他のものなのかを判断するために、さらに先読みが必要なことです。

考えられる解決策の 1 つ (文法を十分に示していないため、わかりません) は、ピリオドが続く場所を因数分解することです。ルールを複製して、と の両方にsimple_type_name置き換えます。上記の例では、次のようになります。simple_type_namequalified_type_nameprimitive_type_nameexpression

expression: qualified_type_name PERIOD expression
          | primitive_type_name PERIOD expression

simple_type_name文法の残りの部分によっては、因数分解を完全に解除することが必要または望ましい場合がありますsimple_type_name。

編集

わかりました。文法をさらにリンクしました。これで、問題のある の使用がsimple_type_name末尾のコンテキスト (ルールの右端) にあることがわかります。したがって、単純な因数分解だけでは十分ではありません。アンファクタリングを繰り返すことで修正できる場合があります（simple_type_name上記のようにアンファクタリングし、次にアンファクタリングsimple_expressionおよび/またはtype_name同様に）。目標は、アンファクタリングを次のルールにプッシュすることです。

    ... some-nonterminal PERIOD ...

右側に、それをルールに置き換えます

    ... other-nonterminal PERIOD ... | ... qualified_type_name PERIOD ...

ここで、単一の削除につながるルールとother-nonterminalの重複です。some-nonterminalqualified_type_name

残念ながら、これは文法のサイズの指数関数的な爆発に簡単につながる可能性があるため、実用的ではない可能性があります。その場合、唯一のオプションは、 bison の%glr-parserオプションやbtyacc によるバックトラックなど、より強力な解析方法を使用することです。

于 2013-12-03T17:27:32.373 に答える