LR Parsing Engine

• LR パーサは，どのようにしてシフトまたは，還元を知るのでしょう?
• DFA を使うのか? 入力に対して，DFA を適用することはできない(有限 オートマトンは，文脈自由文法をパースするためには弱いが、スタックに 対しては，DFA の状態番号を使う)．
• DFA の辺のラベルとして，終端記号と非終端記号 を使う．表3.19(ページ57) に Grammar 3.1 の遷移図(transition table) を示す．
• 遷移図の要素は，以下の 4 種類のアクションを示す．
  1. s$n$ 状態 $n$ へシフトする．
  2. g$n$ 状態 $n$ へ遷移する．
  3. r$k$ 規則 $k$ により還元する．
  4. a 受理(Accept)．
  5. 図の要素が空欄 エラー
• 例えば，スタックが id := $E$ となれば，DFA の状態としては， 1，4，6，11 と遷移したことがわかる．もし，次のトークンがセミコロン であれば，状態 11 にある ";" のカラムにより，規則 2 で還元することを 示している．
• 規則 2 である $S\rightarrow$ id:=$E$ より，3 つのトークン をポップし，$S$ をプッシュする．
• 状態 11 の "+" に対するアクションはシフトであり，もし，次のトー クンが + の場合は，その入力(+) を入力から eaten し，スタックにプッシュ する．
• パースアルゴリズムは，以下のように定義することができる． スタックの状態と，入力シンボルをみて，図よりアクションを得る．
  1. $Shift(n)$: もう一つトークンを読み($n$)，$n$ をスタックにプッシュ する．
  2. $Reduce(k)$: 規則 $k$ の右側にあるシンボルの数だけ，スタックか らポップする．規則 $k$ の左側にあるシンボルを $X$ (非終端記号) とする． スタックトップにある状態番号(ひとつ前の状態) の行の $X$ カラムにある "$goto\:\:\:n$" をみて，(状態)スタック(のトップ)に "$n$" をプッシュする．
  3. $Accept$: Parsing の停止．成功．
  4. $Error$: Parsing の停止．失敗．