SLR パーサの生成

• Grammar 3.23 のための LR(0) パース表を作ってみよう．図3.24 に示す．
• 状態3 では，シンボル + に対して，重複している．これは LR(0) パーサによりパースすることはできない．よりパワフル なアルゴリズムを必要とする．
• 簡単に，LR(0) よりよいアルゴリズムを構成する方法を SLR と いう．Simple LR の略である．
• SLR のパーサは，「FOLLOW 集合により示された 還元アクションのみ 表におく」ことを除いて，LR(0) パーサと同一である．
• 以下が SLR テーブルへ 還元アクションをおくためのアルゴリズムであ る．
  $R\leftarrow \{\:\}$

  
  
       for 

  $T$

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

• アクション $(I,X,A\rightarrow\alpha)$ は，状態 $I$ において， 先読みシンボル $X$ に対して，パーサは規則 $A\rightarrow \alpha$ を還元 することを示す．
• このように Grammar 3.23 では，LR(0) の状態遷移ダイヤグラム (図3.24)が，図3.25 に示すように還元アクションが削られている．
• Grammar 3.23は，文法のクラスがSLR クラスに属する．このクラスに属 する場合は，SLR パーサ表が conflicts(エントリの重複) を含んでいない．