文脈依存文法の視点で見る LR(1) 項集合と LALR(1) 項集合

ドラゴンブック (ISBN978-4-7819-1229-5) 例4.34 (275 ページ) 記載の非 SLR 文法だけど LALR(1) 文法である次の構文で遊んでみます。拡大文法で書いています。ここでは表現をアレンジして PEG 風味で記述しています。

    S'<-S
    S<-L=R
    S<-R
    L<-*R
    L<-x
    R<-L

これの LR(1) 項集合を作ります。まず、上の拡大文法の非終端記号の FOLLOW 集合を考えて、文脈依存文法にします。&($) は PEG の表記を利用した先読み記号を表しています。即座にわかるとおり、FOLLOW(S') = {$} なので、FOLLOW(S) = {$} です。一方、FOLLOW(L) = {=, $} であり、 FOLLOW(R) = {=, $} です。 SLR でシフト・還元衝突が生じるのは、FOLLOW(R) が記号 「=」 を含んでいるのが原因でした。

    S'&($)<-S&($)
    S&($)<-L&(=)=R&($)
    S&($)<-R&($)
    L&(=)<-*R&(=)
    L&($)<-*R&($)
    L&(=)<-x&(=)
    L&($)<-x&($)
    R&(=)<-L&(=)
    R&($)<-L&($)

LR(1) 項集合の初期状態の項を上の文脈依存文法の表記のままで作ります。カーソルはドットで表すことにします。すると、おもしろいことに、左辺が R&($) の生成規則は使うのに、R&(=) の生成規則は入ってきません。

I0 = {[S'&($)<-.S&($)]
      [S&($)<-.L&(=)=R&($)]
      [S&($)<-.R&($)]
      [L&(=)<-.*R&(=)]
      [L&(=)<-.x&(=)]
      [R&($)<-.L&($)]
      [L&($)<-.*R&($)]
      [L&($)<-.x&($)]}

I0 から記号 L で移る、SLR では衝突を生じる項集合 I2 は次のようになります。記号 「=」 でシフト、記号 「$」 で還元になっていて、区別がついています。

I2 = {[S&($)<-L.&(=)=R&($)]
      [R&($)<-L.&($)]}

文脈自由文法の構文を文脈依存文法に視点を広げて扱うことで LR(1) 項集合が得られているのはおもしろいものです。

(2014年5月19日加筆: 生成経路ごとの先読み集合和であることをあからさまに書き下しました。結論。LALR(1) の先読み集合がどうやって得られるかを表すには文脈依存文法の書き方はふさわしくありません)

さて、この例の構文は、 LR(1) 文法よりも限定された LALR(1) 文法でもあります。LALR(1) 項集合を作るために、拡大文法の FOLLOW 集合の記号をテンプレートとして加えた文脈依存文法で書き直します。置換する箇所をシャープ記号で表すことにします。なお、置換の際に記号が重複したら、今、扱っているのは集合なので、当然のことながら一つにまとめるのは約束ごとです。

I0 のテンプレート
    S'&(#)<-.S&(#)
    S&(#)<-.L&(=)=R&(#)
    S&(#)<-.R&(#)
    L&(=/#)<-.*R&(=/#)
    L&(=/#)<-.x&(=/#)
    R&(#)<-.L&(#)
    # は {$}

LALR(1) 項集合の初期状態 I0 は、カーネル項の先読み記号「$」でテンプレートを置換したものから作ります。非終端記号 L をまとめているだけで、LR(1) 項集合の I0 と同じ集合が得られます。

I0 = {[S'&($)<-.S&($)]
      [S&($)<-.L&(=)=R&($)]
      [S&($)<-.R&($)]
      [L&(=/$)<-.*R&(=/$)]
      [L&(=/$)<-.x&(=/$)]
      [R&($)<-.L&($)]}

記号 S で移る I1 と、記号 L で移る I2 も、 そして、記号 R で移る I3 とも、カーネル項の先読み記号は I0 から「$」なので、テンプレートをこれで置換したものから作ります。記号 * と記号 x で移る I4 と I5 は、カーネル項の先読み記号は I0 から「=/$」なので、テンプレートをこれで置換したものから作ります。I4 の 2 番目の先読み記号が I0 のものとは違っているのはそのためです。

I1 のテンプレート
     S'&(#)<-S.&(#)
     # は I0 からの先読み集合
I1 = {[S'&($)<-S.&($)]}

I2 のテンプレート
     S&(#)<-L.&(=)=R&(#)
     R&(#')<-L.&(#')
     # と #' は I0 からの先読み集合
I2 = {[S&($)<-L.&(=)=R&($)]
      [R&($)<-L.&($)]}

I3 のテンプレート
     S&(#)<-R.&(#)
     # は I0 からの先読み集合
I3 = {[S&($)<-R.&($)]}

I4 のテンプレート
      L&(#)<-*.R&(#)
      R&(#)<-.L&(#)
      L&(#)<-.*R&(#)
      L&(#)<-.x&(#)
      # は (I0 からの先読み集合) ∪ (I4 からの先読み集合) ∪ (I6 からの先読み集合)
I4 = {[L&(=/$)<-*.R&(=/$)]
      [R&(=/$)<-.L&(=/$)]
      [L&(=/$)<-.*R&(=/$)]
      [L&(=/$)<-.x&(=/$)]}

I5 のテンプレート
     L&(#)<-x.&(#)
     # は (I0 からの先読み集合) ∪ (I4 からの先読み集合) ∪ (I6 からの先読み集合)
I5 = {[L&(=/$)<-x.&(=/$)]}

I6 のテンプレート
     S&(#)<-L&(=)=.R&(#)
     R&(#)<-.L&(#)
     L&(#)<-.*R&(#)
     L&(#)<-.x&(#)
     # は I2 からの先読み集合
I6 = {[S&($)<-L&(=)=.R&($)]
      [R&($)<-.L&($)]
      [L&($)<-.*R&($)]
      [L&($)<-.x&($)]}

I7 のテンプレート
     L&(#)->*R.&(#)
     # は I4 からの先読み集合
I7 = {[L&(=/$)->*R.&(=/$)]}

I8 のテンプレート
     R&(#)->L.&(#)
     # は (I4 からの先読み集合) ∪ (I6 からの先読み集合)
I8 = {[R&(=/$)->*R.&(=/$)]}

I9 のテンプレート
     S&(#)->L&(=)=R&(#).
     # は I6 からの先読み集合
I8 = {[S&($)->L&(=)=R&($).]}

I4、I5、I8 で LR(1) と LALR(1) に違いが生じます。LR(1) では同じカーネル項でも先読み記号が「=/$」の場合と「$」の場合とを区別しているのに対して、LALR(1) ではこの 3 状態に辿り着くそれぞれの生成経路の先読み集合の和集合「=/$」にまとめてしまいます。