LR Parsing

• LR($k$) Parsing は， Left-to-right parse, Rightmost-derivation, k-token lookahead からきている．
• 図 3.18 に，以下のプログラムで Grammar 3.1 を用いた LR パースを 説明している．新しい start production $S'\rightarrow S\$ を定義してい る． a := 7;
  b := c + (d := 5 + 6, d)
  
• パーサは，スタック(stack) と入力(input) を持つ．入力の最初の $k$ トークンは先読みである．スタックと，先読みに対してパーサは以下の 2 種 類のアクションを起こす．
  1. シフト(shift): 最初の入力をスタックトップへ移す．
  2. 還元(reduce): (例えば，文法規則 $X\rightarrow\:A\:B\:C$ を選ぶと すれば，スタックから $C$，$B$，$A$ の順番でポップし，スタックへ $X$ を プッシュする．

• 最初は，スタックは空(empty) で，パーサは入力の最初からスキャンす る．ファイルの終了マーク $\$ をシフトすることにより，受理($accepting$) とい い，パーサは，成功し終了したことを示す．