4

私は文法を作成しました。その簡略版を以下に再現します。

(0) exp1: ternary;
(1) exp1: exp2;
(2) ternary: exp2 "?" exp1 ":" exp1;
(3) exp2: exp2 "+" exp3;
(4) exp2: exp3;
(5) exp3: maybe;
(6) exp3: "1";
(7) maybe: exp3 "?";

この言語は明確であり、LR解析可能である必要があると思います。(私が間違っている場合は私に知らせてください!)

ただし、この文法のLR(1)パーサーを生成しようとすると、シフト/リデュースの競合が発生します。パーサーがexp3先読み?で表示すると、シフトするかリデュースするかがわからないためです。

Conflicts in state 3:
    Reduction using rule 4: exp2:  exp3 · | "?"
    Shift to state 6

Conflicts in state 9:
    Reduction using rule 3: exp2:  exp2 "+" exp3 · | "?"
    Shift to state 6

Conflicts in state 13:
    Reduction using rule 4: exp2:  exp3 · | "?"
    Shift to state 16

Conflicts in state 20:
    Reduction using rule 4: exp2:  exp3 · | "?"
    Shift to state 23

Conflicts in state 25:
    Reduction using rule 3: exp2:  exp2 "+" exp3 · | "?"
    Shift to state 23

Conflicts in state 28:
    Reduction using rule 3: exp2:  exp2 "+" exp3 · | "?"
    Shift to state 16

この言語をLR(1)解析可能(競合なし)にするための合理的な方法はありますか?

それとも、GLR(またはおそらくLR(2)?)は、このような言語の唯一の現実的なオプションですか?
(または、そもそも言語が明確であると信じるのは間違っていますか?)


参考までに、私が生成したあいまいなステートマシンは次のとおりです(♦はEOFです)。

State 0:
    exp1:  · ternary | {♦} → shift 1
    ternary:  · exp2 "?" exp1 ":" exp1 | {♦} → shift 2
    exp2:  · exp2 "+" exp3 | {"?", "+"} → shift 2
    exp2:  · exp3 | {"?", "+"} → shift 3
    exp3:  · maybe | {"?", "+"} → shift 4
    exp3:  · "1" | {"?", "+"} → shift 5
    maybe:  · exp3 "?" | {"?", "+"} → shift 3

State 1:
    exp1:  ternary · | {♦} → reduce 0

State 2:
    ternary:  exp2 · "?" exp1 ":" exp1 | {♦} → shift 7
    exp2:  exp2 · "+" exp3 | {"?", "+"} → shift 8

State 3:
    exp2:  exp3 · | {"+"} → reduce 4
    exp2:  exp3 · | {"?"} → reduce 4 shift 6
    maybe:  exp3 · "?" | {"?", "+"} → reduce 4 shift 6

State 4:
    exp3:  maybe · | {"?", "+"} → reduce 5

State 5:
    exp3:  "1" · | {"?", "+"} → reduce 6

State 6:
    maybe:  exp3 "?" · | {"?", "+"} → reduce 7

State 7:
    exp1:  · ternary | {":"} → shift 10
    exp1:  · exp2 | {":"} → shift 11
    ternary:  · exp2 "?" exp1 ":" exp1 | {":"} → shift 11
    ternary:  exp2 "?" · exp1 ":" exp1 | {♦} → shift 12
    exp2:  · exp2 "+" exp3 | {"?", ":", "+"} → shift 11
    exp2:  · exp3 | {"?", ":", "+"} → shift 13
    exp3:  · maybe | {"?", ":", "+"} → shift 14
    exp3:  · "1" | {"?", ":", "+"} → shift 15
    maybe:  · exp3 "?" | {"?", ":", "+"} → shift 13

State 8:
    exp2:  exp2 "+" · exp3 | {"?", "+"} → shift 9
    exp3:  · maybe | {"?", "+"} → shift 4
    exp3:  · "1" | {"?", "+"} → shift 5
    maybe:  · exp3 "?" | {"?", "+"} → shift 9

State 9:
    exp2:  exp2 "+" exp3 · | {"+"} → reduce 3
    exp2:  exp2 "+" exp3 · | {"?"} → reduce 3 shift 6
    maybe:  exp3 · "?" | {"?", "+"} → reduce 3 shift 6

State 10:
    exp1:  ternary · | {":"} → reduce 0

State 11:
    exp1:  exp2 · | {":"} → reduce 1
    ternary:  exp2 · "?" exp1 ":" exp1 | {":"} → shift 26
    exp2:  exp2 · "+" exp3 | {"?", ":", "+"} → shift 27

State 12:
    ternary:  exp2 "?" exp1 · ":" exp1 | {♦} → shift 17

State 13:
    exp2:  exp3 · | {":", "+"} → reduce 4
    exp2:  exp3 · | {"?"} → reduce 4 shift 16
    maybe:  exp3 · "?" | {"?", ":", "+"} → reduce 4 shift 16

State 14:
    exp3:  maybe · | {"?", ":", "+"} → reduce 5

State 15:
    exp3:  "1" · | {"?", ":", "+"} → reduce 6

State 16:
    maybe:  exp3 "?" · | {"?", ":", "+"} → reduce 7

State 17:
    exp1:  · ternary | {♦} → shift 1
    exp1:  · exp2 | {♦} → shift 18
    ternary:  · exp2 "?" exp1 ":" exp1 | {♦} → shift 18
    ternary:  exp2 "?" exp1 ":" · exp1 | {♦} → shift 19
    exp2:  · exp2 "+" exp3 | {♦, "?", "+"} → shift 18
    exp2:  · exp3 | {♦, "?", "+"} → shift 20
    exp3:  · maybe | {♦, "?", "+"} → shift 21
    exp3:  · "1" | {♦, "?", "+"} → shift 22
    maybe:  · exp3 "?" | {♦, "?", "+"} → shift 20

State 18:
    exp1:  exp2 · | {♦} → reduce 1
    ternary:  exp2 · "?" exp1 ":" exp1 | {♦} → shift 7
    exp2:  exp2 · "+" exp3 | {♦, "?", "+"} → shift 24

State 19:
    ternary:  exp2 "?" exp1 ":" exp1 · | {♦} → reduce 2

State 20:
    exp2:  exp3 · | {♦, "+"} → reduce 4
    exp2:  exp3 · | {"?"} → reduce 4 shift 23
    maybe:  exp3 · "?" | {♦, "?", "+"} → reduce 4 shift 23

State 21:
    exp3:  maybe · | {♦, "?", "+"} → reduce 5

State 22:
    exp3:  "1" · | {♦, "?", "+"} → reduce 6

State 23:
    maybe:  exp3 "?" · | {♦, "?", "+"} → reduce 7

State 24:
    exp2:  exp2 "+" · exp3 | {♦, "?", "+"} → shift 25
    exp3:  · maybe | {♦, "?", "+"} → shift 21
    exp3:  · "1" | {♦, "?", "+"} → shift 22
    maybe:  · exp3 "?" | {♦, "?", "+"} → shift 25

State 25:
    exp2:  exp2 "+" exp3 · | {♦, "+"} → reduce 3
    exp2:  exp2 "+" exp3 · | {"?"} → reduce 3 shift 23
    maybe:  exp3 · "?" | {♦, "?", "+"} → reduce 3 shift 23

State 26:
    exp1:  · ternary | {":"} → shift 10
    exp1:  · exp2 | {":"} → shift 11
    ternary:  · exp2 "?" exp1 ":" exp1 | {":"} → shift 11
    ternary:  exp2 "?" · exp1 ":" exp1 | {":"} → shift 29
    exp2:  · exp2 "+" exp3 | {"?", ":", "+"} → shift 11
    exp2:  · exp3 | {"?", ":", "+"} → shift 13
    exp3:  · maybe | {"?", ":", "+"} → shift 14
    exp3:  · "1" | {"?", ":", "+"} → shift 15
    maybe:  · exp3 "?" | {"?", ":", "+"} → shift 13

State 27:
    exp2:  exp2 "+" · exp3 | {"?", ":", "+"} → shift 28
    exp3:  · maybe | {"?", ":", "+"} → shift 14
    exp3:  · "1" | {"?", ":", "+"} → shift 15
    maybe:  · exp3 "?" | {"?", ":", "+"} → shift 28

State 28:
    exp2:  exp2 "+" exp3 · | {":", "+"} → reduce 3
    exp2:  exp2 "+" exp3 · | {"?"} → reduce 3 shift 16
    maybe:  exp3 · "?" | {"?", ":", "+"} → reduce 3 shift 16

State 29:
    ternary:  exp2 "?" exp1 · ":" exp1 | {":"} → shift 30

State 30:
    exp1:  · ternary | {":"} → shift 10
    exp1:  · exp2 | {":"} → shift 11
    ternary:  · exp2 "?" exp1 ":" exp1 | {":"} → shift 11
    ternary:  exp2 "?" exp1 ":" · exp1 | {":"} → shift 31
    exp2:  · exp2 "+" exp3 | {"?", ":", "+"} → shift 11
    exp2:  · exp3 | {"?", ":", "+"} → shift 13
    exp3:  · maybe | {"?", ":", "+"} → shift 14
    exp3:  · "1" | {"?", ":", "+"} → shift 15
    maybe:  · exp3 "?" | {"?", ":", "+"} → shift 13

State 31:
    ternary:  exp2 "?" exp1 ":" exp1 · | {":"} → reduce 2
4

1 に答える 1

1

これは優先順位の問題かもしれないと思います。発生している競合は、パーサーが次のようなものを見ているときに発生します。

 a + b ? c : d

パーサーが見ているときa + b ?cそれが必要かどうかを判断することはできません

  1. b?フォームの式を解析してa + (b?)そこから続行するように、を減らします。または

  2. a + bフォームの式を解析するように、を減らします(a + b) ? c : d

?ここでの課題は、ある場合には優先順位が非常に低く(3項演算子として使用される場合)、別の場合には優先順位が非常に高い(単項演算子として使用される場合)ことだと思います。ただし、この方法で優先順位を割り当てた場合、パーサーはこれらのケースを明確にすることができると思います。

お役に立てれば!

于 2013-03-03T20:27:58.337 に答える