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) には存在しない競合が発生することがあります。

シフト/リデュース競合とは、トークンを消費するか還元するかをテーブルが判断できない状態です。リデュース/リデュース競合とは、2 つの還元が可能な状態です。優先順位宣言によって、意図した式の競合を解決できます。しかし、曖昧な言語構造が原因の競合は、文法を修正するか、言語仕様で明示的に定義する必要があります。