LALR(1) 先読み集合 - DeREMER-PENNELLO アルゴリズムの実装

構文解析表を作りたい構文に対して LR(0) 項集合が既に求めてあるものとして、それから LALR(1) 先読み集合を求めるコンセプト・コードを書きます。

データ表現をいくつか試行錯誤したところ、配列の添字を rowid として生成規則と LR(0) 項集合の状態を識別するのが都合が良さそうでした。生成規則の右辺は添字でシンボルを参照する必要があるので配列にします。LR(0) 項集合状態は、3 つの組からなり、ある rowid の生成規則の右辺を先頭から末尾まで読み取り位置を移動するとき、状態から状態へと遷移していく状態の経路を少ない手間で辿っていけるように、読み取り位置が左端にある状態を start に、記号による遷移を goto に、受理の状態を accept にふるい分けておきます。

require 'set'

# 拡大文法 G' = ({=, *, x}, {S', S, L, R}, S', {S'->S, S->L=R, S->R, L->*R, L->x, R->L})
Grammar = Struct.new(:terminal, :nonterminal, :start, :production)
Production = Struct.new(:lhs, :rhs)
grammar = Grammar[
  Set['=', '*', 'x'], Set[:S0, :S, :L, :R], :S0,
  [# grammar.production[produnction_rowid] => Production[lhs, rhs]
    Production[:S0, [:S]],          #0
    Production[:S,  [:L, '=', :R]], #1
    Production[:S,  [:R]],          #2
    Production[:L,  ['*', :R]],     #3
    Production[:L,  ['x']],         #4
    Production[:R,  [:L]],          #5
  ]
]

# G' からあらかじめ求めておいた LR(0) 項集合状態
State = Struct.new(:start, :goto, :accept)
state = State[
  [# state.start[production_rowid] => [state_rowid]
    [0],        # S'->.S
    [0],        # S->.L=R
    [0],        # S->.R
    [0, 4, 6],  # L->.*R
    [0, 4, 6],  # L->.x
    [0, 4, 6],  # R->.L
  ],
  [# state.goto[state_rowid] => {symbol => state_rowid}
    {:S => 1, :L => 2, :R => 3, '*' => 4, 'x' => 5},
    {},
    {'=' => 6},
    {},
    {:R => 7, :L => 8, '*' => 4, 'x' => 5},
    {},
    {:R => 9, :L => 8, '*' => 4, 'x' => 5},
    {},
    {},
    {},
  ],
  # state.accept.include?(state_rowid) => True|False
  [1]
]

class << (ENDMARK = Object.new)
  def to_s() '$' end
  def inspect() '$' end
end

先読み集合は 3 段階の集合和で求めます。最初に read_set を求め、続いて follow_set を求め、最後に先読み集合である la_set を求めます。なお、今回の実装では、推移閉包によって集合和を求める union_relation は 1 番目の引数で渡した集合のハッシュを破壊的に書き換えます。

# LALR(1) lookahead set computation
#
# F. L. DeRemer, T. J. Pennelo "Efficient Computation of LALR(1) Lookahead Sets",
#   ACM Transactions on Programming Languages and Systems, Vol. 4, No. 4, 1982
def lookahead(grammar, state)
  nullable = select_nullable(grammar.production)
  dr_set = {}            #:: {[state_rowid, nonterminal] => Set[terminal]}
  reads_relation = {}    #:: {[state_rowid, nonterminal] => Set[[state_rowid, nonterminal]]}
  includes_relation = {} #:: {[state_rowid, nonterminal] => Set[[state_rowid, nonterminal]]}
  lookback_relation = {} #:: {[state_rowid, production_rowid] => Set[[state_rowid, nonterminal]]}
  la_set = {}            #:: {[state_rowid, production_rowid] => Set[terminal]}
#@<dr_set と reads_relation を sate.goto から求める@>
  # Read(p,A) = DR(p,A) + U{Read(r,C) | (p,A) reads (r,C)}
  read_set = union_relation(dr_set, reads_relation)         #:: {[state_rowid, nonterminal] => Set[terminal]}
#@<includes_relation と lookback_relation を production と goto から求める@>
  # Follow(p,A) = Read(p,A) + U{Follow(q,B) | (p,A) includes (q,B)}
  follow_set = union_relation(read_set, includes_relation)  #:: {[state_rowid, nonterminal] => Set[terminal]}
  # LA(q,A->ω.) = U{Follow(p,A) | (q,A->ω.) lookback (p,A)}
  lookback_relation.each_pair do |x, rel|
    la_set[x] = rel.inject(Set.new){|r, y| r.merge follow_set[y] }
  end
  la_set
end

dr_set と reads_relation を state.goto から求めます。この 2 つは、LR(0) 項集合の状態遷移表だけから求めることができます。現在着目している状態 p の非終端記号 A による遷移の先の状態 r で、終端記号 t による遷移があるなら DR 集合に追加し、空文字列を生成する非終端記号 C なら reads 関係に追加します。DR では、状態 r が受理を含むときに限り入力終了記号を追加します。

#@<dr_set と reads_relation を state.goto から求める@>=
  state.goto.each_index do |state_p|
    state.goto[state_p].each_pair do |symbol_a, state_r|
      next unless grammar.nonterminal.include?(symbol_a)
      dr_set[[state_p, symbol_a]] = Set[]
      reads_relation[[state_p, symbol_a]] = Set[]
      includes_relation[[state_p, symbol_a]] = Set[]
      # DR(p,A) = {t| p-(A)->r-(t)-> }
      # (p,A) reads (r,C) is p-(A)->r->(C)-> and C=>ε
      state.goto[state_r].each_key do |symbol_x|
        if grammar.terminal.include?(symbol_x)
          dr_set[[state_p, symbol_a]] << symbol_x
        elsif nullable.include?(symbol_x)
          reads_relation[[state_p, symbol_a]] << [state_r, symbol_x]
        end
      end
      if state.accept.include?(state_r)
        dr_set[[state_p, symbol_a]] << ENDMARK
      end
    end
  end

includes_relation と lookback_relation を production と goto から求めます。この 2 つは、生成規則の右辺の記号を先頭から末尾までに対応する LR(0) 項集合の状態の経路を辿って作ります。

#@<includes_relation と lookback_relation を production と goto から求める@>=
  grammar.production.each_with_index do |prod, prod_rowid|
    next if prod_rowid == 0
    state.start[prod_rowid].each do |state_p|
      # (q,B) includes (p,A) is A->βBγ, γ=>ε and p-(β)*->q
      # (q,A->ω.) lookback (p,A) is p-(ω)*->q
      state_q = state_p
      (0 ... prod.rhs.size).each do |pos|
        symbol_b = prod.rhs[pos]
        if grammar.nonterminal.include?(symbol_b)
          # γ=>ε が成り立つには、右端に到達したときと、記号列が空文字を生成する場合の2通りがある
          if pos + 1 >= prod.rhs.size
            includes_relation[[state_q, symbol_b]] << [state_p, prod.lhs]
          elsif prod.rhs[pos + 1 .. -1].all? {|c| nullable.include?(c) }
            includes_relation[[state_q, symbol_b]] << [state_p, prod.lhs]
          end
        end
        state_q = state.goto[state_q][symbol_b]
      end
      lookback_relation[[state_q, prod_rowid]] ||= Set.new
      lookback_relation[[state_q, prod_rowid]] << [state_p, prod.lhs]
    end
  end

select_nullable は空文字列を生成する非終端記号の集合を求めます。この集合は FIRST 集合からεだけを抜き出したものになっており、FIRST 集合の求め方に似た方法になっています。

# {A| A in Nontermanal and A=>ε on production set }
def select_nullable(production)
  nullable = Set.new
  changed = true
  while changed
    changed = false
    production.each do |e|
      if e.rhs.size == 0 or e.rhs.all? {|a| nullable.include?(a) }
        changed |= ! nullable.add?(e.lhs).nil?
      end
    end
  end
  nullable
end

union_relation は集合和を求めます。DeREMER の論文では digraph の名前になっていて、何をやりたい手続きなのか意図がくみとりにくいため、改名しました。Tarjan のアルゴリズムに集合和演算を混ぜ込んだ形になっています。この版では、f の内容を破壊的に書き換えて戻り値にします。

# F(x) = F'(x) + U{F(y) | x R y }
# derived from Tarjan's strongly connected components algorithm
def union_relation(f, relation)
  stack = []
  mark= {}
  f.each_key{|x| mark[x] = 0 }
  f.each_key do |x|
    next unless mark[x] == 0
    union_relation_traverse(x, relation, f, stack, mark)
  end
  f
end

def union_relation_traverse(x, relation, f, stack, mark)
  stack.push x
  mark[x] = d = stack.size
  relation[x].each do |y|
    if mark[y] == 0
      union_relation_traverse(y, relation, f, stack, mark)
    end
    mark[x] = mark[x] < mark[y] ? mark[x] : mark[y] # [mark[x], mark[y]].min
    f[x].merge f[y]
  end
  if mark[x] == d
    while true
      mark[stack.last] = relation.size + 2
      f[stack.last] = f[x]
      break if stack.pop == x
    end
  end
end

以上を試しで動かしてみます。

lookahead(grammar, state).to_a.sort{|a,b| a[0][0] <=> b[0][0]}.each do |(q, i), la|
  prod = grammar.production[i]
  puts "(%d,[%s->%s.,%s])" % [
    q, prod.lhs.to_s, prod.rhs.map{|x| x.to_s }.join(''), la.to_a.join('/')]
end

このアルゴリズムで先読み集合を求める対象は最終項だけです。先読み集合はシフトするか還元するかの判定に使うものなので、最終項の先読み集合さえ求まっていれば良いわけで、合理的です。

(2,[R->L.,$])
(3,[S->R.,$])
(5,[L->x.,=/$])
(7,[L->*R.,=/$])
(8,[R->L.,=/$])
(9,[S->L=R.,$])