移位-歸約衝突(shift-reduce conflict)
想像輸送帶旁的工人遇到一個時刻,兩種動作看來都有效:他可以把桌上已有的零件夾成一個完成的件,或先等一下、從帶子拿下一個物件,而說明書沒說該選哪個。卡在兩者之間,他無法繼續。移位-歸約衝突正是 LR 剖析器內部的這種兩難:在某個狀態、某個前瞻詞符下,表同時說「移位」與「歸約」都可能,卻無從選擇。
衝突有兩種口味。移位-歸約衝突意味剖析器分不清該壓入下一個詞符還是歸約堆疊上的東西;經典案例是懸置 else(dangling-else),在 if E then S 之後剖析器看到 else,分不清該 else 是接到這個 if 還是外層的 if。歸約-歸約衝突意味兩條不同規則都可能用來歸約同一個句柄,剖析器分不清是哪一條。衝突在文法歧義時出現,或在文法無歧義、但就是不在所選 LR 變體能力範圍內時出現。標準療法是:宣告運算子的優先序與結合性(例如告訴工具 * 比 + 結合得緊、+ 向左結合,這會以正確方式悄悄化解算術的移位-歸約衝突)、改寫文法以消除歧義,或對懸置 else 採用常見慣例「else 配最近的未匹配 if」,這恰好是以偏向移位來化解衝突。
衝突之所以重要,是因為它們是你跑剖析器產生器時文法問題現身的日常方式:bison 印出「N 個 shift/reduce 衝突」並以一條預設規則(移位勝出)悄悄化解,那未必是你的本意。把衝突當成該調查的警告、而非可忽略的雜訊,正是「剖析出你本意之物的文法」與「悄悄誤讀程式的文法」之間的差別。
懸置 else:以 S -> if E then S | if E then S else S | other,在剖析 if E then S 之後,前瞻 else 觸發一個移位-歸約衝突。bison 的預設(移位)把 else 接到最近的 if,這是慣例上、通常也是本意的解讀。
衝突 = 表同時提供兩個動作;以優先序/結合性或改寫來化解。
產生器的預設化解(移位優先於歸約)會讓衝突消音,卻未必符合你的本意。被回報的衝突是「文法歧義或超出剖析器類別」的真實訊號,而非該抑制的表面雜訊。