LR(0) パーサの生成

• LR($k$) パーサは，スタックの中身と，入力の次の $k$ トークンから アクションを決定する．例えば，表3.19 は先読みとして1 つのシンボルを用 いた．
• $k=2$ の場合は，図のカラムは，各 2 つのトークンのシーケンスとな る．
• 実際，$k>1$ の場合は，コンパイラでは用いられない．その一つの理由 として表が巨大になることや，ほとんどの reasonable プログラミング 言語は，LR($1$) 文法で記述可能であることがあげられる．
• LR($0$) 文法は，スタックのみからシフト／還元を決定し解析をする (先読みはない)．
• この文法のクラスは，あまり役立たないが，LR($0$) パース表を 構成するためのアルゴリズムは，LR($1$) パーサ を構成するアルゴリズム へのよい導入となる．
• LR($0$) パーサの生成を説明するために Grammar 3.20 を使う．
• 最初に，スタックを空とし，入力は $\$ まで完全な $S$ 文とする． これを $S'\rightarrow .S\$ と書く．ドット(.) は，パーサの現在位置を 示す．
• この状態では，入力は $S$ で始まり，以下のように示す．
  $S'\rightarrow .S$

  
  
                  $S\rightarrow .x$
  
                  $S\rightarrow .(L)$
  

  これを 状態1 といおう．
• 右側にドットをもつ，文法規則をアイテム(item) とい う(特に，LR($0$) アイテムという)．状態は，アイテム集合である．

シフト アクション

• 状態 1 において，$x$ をシフトしたら何が起こるでしょう．
• 規則 $S\rightarrow .x$ にあるドットを($x$ の右側に)移すことによ り $x$ をパスする． 他の規則は，このアクションでは不適合である．よって 状態 2 を以下のようにする．
  $S\rightarrow x.$

• 状態 1 において，$($ をシフトしたらどうでしょう． 規則 $S\rightarrow .(L)$ にあるドットを移すことにより，以下の規則を生 成する．ここでは，スタックのトップに $($ がある．
  $S\rightarrow (.L)$

• 次に，どのトークンが入力として来るか?
• アイテム集合から $L-productions$ を含んだものを見つけると以下のようになる． これを 状態 3 とする．
  $S\rightarrow (.L)$

  
  
                  $L\rightarrow .L,S$
  
                  $L\rightarrow .S$
  
                  $S\rightarrow .(L)$
  
                  $S\rightarrow .x$
  

  ここで，3 番目の規則より($L-items$)，ドットがちょうど $S$ の前にきてい る．よって $S-productions$ も含んでいる．

Goto アクション

• 状態 1 において，パーサが$S$ 非終端記号よりトークンをパスすると きの効果を考えてみよう．これは $x$ または，( に続く $S-production$ を すべてシフトしたときである．
• 右側にある全てのシンボルをポップした後に，状態 1 において goto アクションを実行する．そして，以下のようになる． これを 状態 4 とする．
  $S'\rightarrow S.\$

還元アクション

• 状態 2 では，ドットはアイテムの最後にきている．これは，規則 $S\rightarrow x$ に相当する右側すべてが揃ったことを示す．つまり， 還元の準備ができたことを示す．パーサは，還元アクションを実行する．

• ある状態で何をなすべきかを示す基本的な操作(operation) は， closure$(I)$， goto$(I)$ で表現される．
• $I$ は，アイテム集合， $X$ は，文法のシンボルである(非終端記号か，終端記号か)．
• Closure は，非終端記号の左側にドットがあるアイテムを，アイ テムの集合に追加する．
• goto は，$I$ の全てのアイテムに対して，$X$ の前にあるドットを $X$ の後にする．

  
   Closure

  $(I) =$

  
  
       repeat
  
                   for $I$ にある全てのアイテム$A\rightarrow \alpha.X\beta$ に対して，
  
                       for $X\rightarrow\gamma$ という production に対して，
  
                                      $I\leftarrow I\cup\{X\rightarrow .\gamma\}$
  
                   until $I$ が変化しなくなる
  
                   return $I$
  

  
   Goto

  $(I,X)$

   =
  
      $J$ を空集合とする．
  
                   for $I$ にあるアイテム $A\rightarrow \alpha.X\beta$に対して，
  
                      $J$ に $A\rightarrow \alpha X.\beta$ を追加する．
  
                   return  Closure$(J)$
  

• 以下に LR(0) パーサのアルゴリズムを示す．シフトと，遷移(goto) の み．
  $T$

   を $\{{\bf Closure}(\{S'\rightarrow\:.S\$\})\}$ に初期化する．
  
  $E$ を 空にする．
  
   repeat
  
       for $T$ にある各状態 $I$ に対して，
  
                       for $I$ に対する各$A\rightarrow \alpha.X\beta$ に対して，
  
                                       let $J$ を  Goto$(I,X)$ とする．
  
                                                  $T\leftarrow T\cup\{J\}$
  
                                                  $E\leftarrow E\cup\{I\rightarrow^{X}\:J\}$
  
   until $E$ と $T$ がこの繰り返しで変化しない．
  

• ここでは， Goto$(I,\$)$ を計算していない．その代わり， accept アクションを計算する．
• 図3.21 で Grammar 3.20 のための状態遷移図を示す．
• LR(0)の還元アクションのための集合 $R$ を計算するアルゴリズムを以 下に示す．
  $R\leftarrow \{\:\}$

  
  
   for $T$ にある各状態 $I$ に対して，
  
       for $I$ にある各アイテム$A\rightarrow \alpha.$ に対して，
  
                      $R\leftarrow R\cup\{(I,A\rightarrow \alpha)\}$
  

• 表 3.22 に，この文法のためのパース表を示す．
• 各辺 $I\rightarrow^{X} J$ に対して，$X$ が終端記号のとき，テーブ ル $(I,X)$ の位置に，$shift\:J$ アクション をおく．
• $X$ が非終端記号のとき，$(I,X)$ の位置に，$goto\:\:\:J$ アクションを おく．
• アイテム $S'\rightarrow S.$ をもつ各状態 $I$ において，位置 $(I,\$)$ に $accept$ アクションをおく．
• 最後に，アイテム $A\rightarrow \gamma.$ を含む状態 (行末にドットを含む production $n$) に対して，トークン $Y$ のための $(I,Y)$ の位置に，$reduce\:\:\:n$ アクションをおく．
• LR(0) は先読みを必要としないので，各状態に対しては、一つのアクショ ンを必要とする．シフトまたは，還元(reduce) であり，両方は必要ではない．
• 実際には，どの状態で シフトするかを知る必要があり，行にその状態 番号，列として文法シンボルをとる．