shift/reduceとreduce/reduceのconflict

shift/reduce conflict

文法規則がshiftとreduceの両方が解釈できることを示す

つまりその入力の時点で、さらに長い非終端記号を選択することもできるし、そこで打ち切って非終端記号にしてしまうこともできてしまう

一概に文法規則が間違っているとは言えない

競合した場合、happyは自動的にshiftが選ぶ

code:bnf

S -> if E then S ①

S -> if E then S else S ②

S -> other ③

code:example

if a then (if b then s1) else s2

if a then (if b then s1 else s2) // 一般的にはこっち

https://gyazo.com/948646d84a2ef06dd28ec683d1c9a056

緑の部分を①を使ってreduceするか

exampleの前者

②を使うためにelseをshiftするか

exampleの後者

どうやって解消するか

reduce/reduce conflict

同時にReduceできる文法規則が複数あることを示す

便宜上Happyは先に書かれた方の文法を優先するがこれは正しいとは限らない

人間がこのエラーを取り除く必要がある

解析手順によってプログラムの出力が異なる

どうやって解消するか

code:エラー.bnf

sequence: /* 空 */

| maybeword

| sequence word

maybeword: /* 空 */

| word

以下のように修正するなど

code:修正後.bnf

sequence: /* 空 */

| sequence word

maybeword: /* 空 */

| word

具体例

Hytlで実際に問題になっていたもの一部抜粋

code:.y

Exp :: { Exp }

: Exp '+' Exp

| var Factor

| Factor

Factor

: '(' Exp ')'

| int

| var

| list

code:info

state 44 contains 1 reduce/reduce conflicts.

// 中略

State 44

Factor -> list . (rule 25)

list -> Factor ':' list . (rule 27)

int reduce using rule 27

var reduce using rule 27

'+' reduce using rule 27

':' reduce using rule 27

(reduce using rule 25)

%eof reduce using rule 27

https://gyazo.com/c5df8376980d033a6a3edf8c9c5b7888

あってる？

なぜなっていたかというと以下のような構文をサポートしていたため

list : list

どう解決するか

code:bnf

Exp :: { Exp }

: Exp '+' Exp

| var Factor

| list

| Factor

Factor

: '(' Exp ')'

| int

| var

ルール内に配列のネストレベルを計算させる

わからんけど

型検査で解決する

わからんけど

一番上のブロックにどのStateでエラーが起きているかが表示されている

code:.info

state 31 contains 10 reduce/reduce conflicts.

実際にState31を見てみる

端折っているがこんなふうに書かれてある

code:.info

State 31

Factor -> list . (rule 20)

list -> Exp ':' list . (rule 22)

int reduce using rule 22

var reduce using rule 22

bool reduce using rule 22

'+' reduce using rule 22

(reduce using rule 20)

'-' reduce using rule 22

(reduce using rule 20)

'*' reduce using rule 22

(reduce using rule 20)

'/' reduce using rule 22

(reduce using rule 20)

最初の方の行の

参考

両方