LR(1) アイテム; LR(1) Parsing 表

• SLR より，パワフルなアルゴリズムが LR(1) パースアルゴリズムで ある．
• 文脈自由文法で文法を記述することができるほとんどの言語は， LR(1) 文法である．
• LR(1) パース表は，LR(0) の表と似ている．が，アイテムの意 味は，より洗練されている．
• LR(1) アイテムは，文法 production(grammar production), 右側の位置(a right-hand-side position)(ドットで示す)， 先読みシンボル からなる．
• $(A\rightarrow \alpha.\beta, x)$ で，シーケンス $\alpha$ は， スタックトップにあり，入力の頭には，文字列$\beta x$ があることを示す．
• LR(1) の状態は，LR(1) アイテムからなる．LR(1) の Closure と Goto は，先読みを導入している．

  
   Closure

  $(I)$

   =
  
       repeat
  
                       repeat
  
                                       for 

  $I$

   にあるアイテム$(A\rightarrow\alpha.X\beta,z)$ に対して，
  
                                                       for productiontex2html_image_mark>#tex2html_wrap_inline611# に対して，
  
                                                                       for $w\in FIRST(\beta z)$ に対して，
  
                                                                                      $I\leftarrowI\cup\{(X\rightarrow .\gamma, w)\}$
  
                   until $I$ が変化しない．
  
                   return $I$
  

• Goto$(I,X)$

  
   Goto

  $(I,X)$
  $J\leftarrow \{\:\}$

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

• start 状態は，アイテム $(S'\rightarrow .S\$,?)$ のクロージャであ る．ファイル終了マーク(End-of-File)$\$ は，シフトされないので， 先読みシンボル $?$ には意味はない．
• 還元(reduce) アクションは，以下で与えられるアルゴリズムである．
  $R\leftarrow \{\:\}$

  
  
                   for 

  $T$

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

  アクション $(I,z,A\rightarrow\alpha)$ は，状態$I$ において，先読みシン ボル $z$ でパーサは，規則 $A\rightarrow \alpha$ を還元することを示す．
• Grammar 3.26 は，SLRではない(Exercise 3.9 を参照)が，LR(1)文法のク ラスである．図3.27 は，この文法のための状態遷移を示している．
• この図では，先読みが異なるだけで同じ production であるアイテムが ある．そのような場合には，以下のように，省略する．

  $S'\rightarrow .S\$	$?$
  $S\rightarrow .V=E$	$\$
  $S\rightarrow .E$	$\$
  $E\rightarrow .V$	$\$
  $V\rightarrow .x$	$\$
  $V\rightarrow .*E$	$\$
  $V\rightarrow .x$	$=$
  $V\rightarrow .*E$	$=$

  これを，以下のように省略する．

  $S'\rightarrow .S\$	$?$
  $S\rightarrow .V=E$	$\$
  $S\rightarrow .E$	$\$
  $E\rightarrow .V$	$\$
  $V\rightarrow .x$	$\$,=$
  $V\rightarrow .*E$	$\$,=$

• 状態グラフから導出されたLR(1) パース表は，図3.28a のようになる．
• production の最後にドットが来た場合は，LR(1) 表では還元アクショ ンが実行される(図3.27 の状態 3 のとき， $E\rightarrow V$ の最後にドット がある)．
• ドットが，終端記号または，非終端記号の左に来た場合は，LR(1) パース表では，シフトか遷移(goto) アクションになる(LR(0) 表にあるとき と同様である)．