解決衝突

Question

有關LALR（1）語法分析器，主要涉及解析的細節衝突的一些問題：

1. 根據不同LALR在教科書中描述的（1）語法分析器如果遇到轉換/減少衝突，那麼這是語法不是LALR（1）開始的標誌，對吧？

2. 縮小/減少衝突可能會出現在有效 LALR（1）語法，由於國家的合併來自LR（1）做LALR（1），對不對？

3. 優先級和結合，如YACC和野牛GNU使用，被介紹的工具來幫助解決移位/減少衝突，對不對？

4. 此外，關聯性只應由解析器檢查，如果衝突的shift/reduce規則優先級等於先行符號優先級，則在任何其他情況下關聯性是不相關的，對嗎？

我問，因爲我不是100％肯定，案卷不提供有關解決衝突的細節，只有幾行我關於這個問題的發現是in the GNU Bison Manual

一個問題有關野牛上述手動鏈接：

• ？他們爲什麼要求在衝突缺席優先規則或超前記號，選擇是轉變？我會認爲，如果裁減規則有任何優先順序，它就完全沒有優先權而擊敗前瞻。

Answer 1

1. 如果任何衝突（或者移位/減少或降低/減少）LALR（k）的施工過程中被發現，則該語法不是LALR（K）。

2. 從LR（1）到LALR（1）的狀態合併不會產生移位/減少衝突，因此如果有衝突，語法也不是LR（1）。但它可能會產生減少/減少衝突。如果有，語法不是LALR（1），即使它是LR（1）。 （這不是真正的「有效性」問題;它是由特定算法解析的問題。）

3. 是，優先級（和關聯性，它只是優先級的子項）允許解決移位/減少衝突。

4. 優先級是與生產（在左側）之間的比較的超前記號（在右側）。關聯性會影響所使用的比較運算符：或者是≤或<（或者在%nonassoc的情況下是錯誤等值）。

在Dragon book中有一個很好的算法討論。然而，這並不是很複雜：如果產品「獲勝」，解析器會減少;否則它會改變。

獎勵問題：優先規則僅適用於爲生產（通過%prec或默認情況下，生產中最後一個終端的優先級）和先行令牌定義的優先級。如果其中任何一個缺少優先聲明，則換班勝利。這可能看起來不合邏輯，但事實就是這樣。