LR 語法分析

LR 語法分析是一種針對決定性上下文無關文法、由表格驅動的自底向上方法。L 表示從左到右讀取詞法單元；R 表示剖析器以反向順序建構最右推導。

移進-歸約機 #

剖析器維護一個由狀態和文法符號組成的堆疊。對於每個狀態和前瞻詞法單元，動作表格會選擇下列其中一項：

1. Shift（移進）：消耗該詞法單元，並將目的狀態推入堆疊。
2. Reduce（歸約）：將產生式右側替換為其左側的非終結符號，然後使用 goto 表格選取下一個狀態。
3. Accept（接受）：在輸入結尾識別增廣開始產生式。
4. Error（錯誤）：回報不存在有效的後續操作。

push state 0
repeat
  action = ACTION[top_state, lookahead]
  if action is shift s: consume lookahead; push s
  if action is reduce A → β: pop |β| grammar symbols and states; push GOTO[top_state, A]
  if action is accept: return syntax tree
  otherwise: report a syntax error

語意動作通常會在歸約時執行。平行的值堆疊會儲存待歸約符號對應的 AST 節點或其他值。

項目與前瞻 #

LR 項目會記錄一個產生式，以及一個表示已識別輸入的圓點，例如 E → E + · T。項目集合構成剖析器狀態。closure 會加入圓點後非終結符號所需的產生式，而 goto 會跨越文法符號推進圓點。

LR(0) 歸約沒有前瞻資訊，因此可接受的文法類別較小。SLR 使用 FOLLOW 集合限制歸約。Canonical LR(1) 為每個項目附加前瞻集合，因此能識別更多文法。LALR(1) 合併相容的 LR(1) 狀態以縮減表格大小；合併可能引入 Canonical LR(1) 不會產生的衝突。

移進/歸約衝突表示表格無法判斷應該消耗詞法單元還是執行歸約。歸約/歸約衝突表示有兩種可能的歸約。優先順序宣告可以解決預期的運算式衝突，但由含糊的語言結構造成的衝突，應透過修正文法來解決，或在語言規格中明確定義。