6

Ironyを使用して小さなパーサーを作成しようとしています。残念ながら、「シフト削減の競合」が発生します。文法は私の得意分野ではなく、この 1 つの小さなことを完了するだけで済みます。エラーを生成する簡略化された文法は次のとおりです。

ExpressionTerm := "asd"
LogicalExpression :=
    ExpressionTerm |
    LogicalExpression "AND" LogicalExpression |
    LogicalExpression "OR" LogicalExpression

「shift-reduce 競合」とは何を意味し、どうすれば解決できますか? それは私の文法があいまいであることを意味していると私は推測していますが、私は自分の論理を十分にひねってその方法を理解することはできません.

追加:明確にするために - 「asd」は単なるリテラル文字列「asd」です。したがって、次の式がこの文法によって解析されると予想されます。

asd
asd AND asd
asd AND asd OR asd
asd OR asd AND asd OR asd

追加 2:言い忘れましたが、文法の語根は ですLogicalExpression。

追加 3:ああ、わかった! あいまいさは、

asd AND asd OR asd

次の 2 つの異なる方法で解釈できます。

(asd AND asd) OR asd
asd AND (asd OR asd)

しかし、どうすればこれを解決できますか？OK、AND または OR のどちらか一方を他方よりも強くすることができます (いずれにせよ意図していました)。しかし、オペレーターが 1 人しかいない場合でもエラーが表示されるようになりました。つまり、これも同じエラーを生成します。

LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression

この場合、私はこれが欲しい：

asd OR asd OR asd

これに解析されます：

(asd OR asd) OR asd

これを行うためのあいまいでない方法は何ですか?

追加 4:わかりました！

LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")"

これは、演算子の優先順位を NOT->AND->OR として、すべてのブール式を解析します。「asd」は、用語を意図した表現に置き換えることができます。

4

4 に答える 4

3

単一の先読みしか使用しない場合、文法はあいまいです。説明のために、「asd」とは何ですか? それはExpressionTermですか、それともより長い用語ですか。それがシフト削減競合です。ここでもreduce-reduceの競合が疑われます。

ほとんどの LL(1) / LALR(1) ジェネレーターは、優先順位演算子を介してシフト削減の競合に対処する方法を提供します。また、ほとんどの場合、shift-reduce 競合が存在する場合はデフォルトで最長のシーケンスになるため、多くの場合、これらは無視できます (精査した後)。(この場合、正しく動作させるために、単一の用語を一番下に移動する必要があるかもしれません)。

于 2009-05-26T12:41:07.613 に答える
1

Shift-Reduce の競合は、文法があいまいであることを意味します。再帰ルールでは、トークン「asd」が or の一部として解釈される可能性があり、パーサーはどちらExpressionTermをLogicalExpression決定できません。引き分けにするには、追加のルールが必要です。

于 2009-05-26T12:45:25.450 に答える
0

シフトリデュースの競合は、パーサーに関して頭を動かすのが難しいことの1つです。競合を説明する最も簡単な方法は、次の擬似コードです。

if (a) then
   if (b) then
     printf('a + b');
   else
     print('this could be a + !b or !a');

elseステートメントは最初または2番目のifにバインドできます。あいまいな文法の場合、通常、文法で予想されるshift-reduce警告の数を示す値を定義します。

または、LL（k）またはLL（*）パーサーを使用することもできます。これらのタイプのパーサーには、シフト/削減のあいまいさがありません。アプリケーションに応じて、LALR（1）パーサーよりも簡単または難しい場合があります。

于 2009-06-04T01:16:17.240 に答える
0

asd トークンを置換することができるため、文法があいまいですLL(1)。LALR(1)ExpressionTermLogicalExpression

于 2013-09-08T13:22:16.040 に答える