富豪的 CLOSURE 計算結果使い捨て型シフト還元解析おもちゃ

ネタ・プログラミングを一席。
上向き構文解析で使うシフト還元解析器では、解析表をあらかじめ作っておき、解析表に従って状態遷移を繰り返します。この解析表を手作業で作るのは面倒な作業であり、コンパイラコンパイラ等を使うのが常識になっているわけです。わけなのですが……。ふと、実行速度が遅くて良いなら解析表を作らずに使い捨てでシフト還元解析をおこなわせることが可能なのではなかろうかと思い当たりました。そんなわけで、試しにおもちゃをでっちあげてみました。
この解析器では LR(0) オートマトンの遷移先をその場その場で計算しながら使い捨てしつつ、シフト還元動作を繰り返します。ちなみに、シフト・還元のどちらをおこなうかの判定はドラゴン・ブック「LR(0) オートマトンの使用」(266ページ) の文書解説にならってシフト優先とし、シフト先がないときに限って還元が可能かどうかをチェックする妥当な方式を採用しました。

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-

# 富豪的 LR(0) オートマトンによるシフト還元解析器

# 参考文献:
#   A.V. エイホ、M.S. ラム、R. セシィ、J.F. ウルマン著、原田健一訳「コンパイラ 第2版」、
#   2009, サイエンス社、ISBN978-4-7819-1229-5
#   266ページ、「LR(0) オートマトンの使用」

S0 = "S'" # 拡大文法のための頭部

def parse(grammar, word_list)
  # S' -> S を先頭に加えた拡大文法を作る
  g = grammar.dup
  g.unshift [S0, grammar[0][0]]
  # 項集合 CLOSURE({ [S' -> .S] }) をスタックに置く
  stack = [closure(initial_terms(g), g)]
  dump(stack, word_list)
  while true
    # 入力記号列の頭部記号 w で遷移できるか調べる
    j = goto(stack.last, word_list.first, g)
    if not j.empty?
      puts '# shift ' + word_list.first
      stack.push j    # w に対応する項集合へ遷移
      word_list.shift # w をシフト
      dump(stack, word_list)
      next
    end
    # スタック先頭の項集合からゴールを探す。例: [T -> T*F.] 等
    j = stack.last.select{|term| term[2].empty? }
    if j.size < 1
      raise 'Syntax Error' # ゴールがないときはエラー
    elsif j.size > 1       # ゴールが2つ以上のときは還元・還元衝突
      raise 'Reduce/reduce conflict ' . (j.collect{|term| pterm(term) }.join(' / '))
    elsif j.first[0] == S0 && word_list.first == '$'
      puts '# accept'      # ゴール [S' -> S.] は還元ではなく、受理
      return
    else
      puts '# reduce ' + pproduct(j.first)
      stack.pop(j.first[1].size)   # A -> γ の γの長さ分スタックから捨てる
      dump(stack, word_list)
      puts '# goto ' + j.first[0].to_s
      stack.push(goto(stack.last, j.first[0], g)) # A に対応する項集合へ遷移
      dump(stack, word_list)
    end
  end
end

# 項は左辺はそのまま、右辺を . で分割した 2 つの配列で表す。
#
#   [A -> α.Bβ] は [A, [α], [Bβ]]
#   [E -> E.+T] は [:E, [:E], ['+', :T]]
#
# 拡大文法 G' の初期項集合を求める。
def initial_terms(g)
  lft, *rgt = g[0]
  [[lft, [], rgt]] # g[0] が S' -> S のとき { [S' -> .S] }
end

# 項集合 I から項集合 CLOSURE(I) を求める。
def closure(i, g)
  j = i.dup
  while true
    a = []
    j.each do |term|
      # J に [A -> α.Bβ] が含まれるとき、[B -> .γ] を J に加える。
      g.select{|rule| rule.first == term[2].first }.each do |lft, *rgt|
        b = [lft, [], rgt]
        a.push b if ! j.include?(b)
      end
    end
    break if a.empty?
    j.concat(a)
  end
  j
end

# 項集合 I から記号 x による遷移先の項集合 CLOSURE(J) を求める
def goto(i, x, g)
  j = i.select{|term| term[2].first == x }.collect{|a, alpha, beta|
    [a, alpha + [beta.first], beta[1 .. -1] || []]
  }
  return j if j.empty?
  closure(j, g)
end

# 項集合 I からカーネル項を抜き出す。
# カーネル項は [A -> α.Bβ] で α が空でないものか、または [S' -> .S]
def kernel(i)
  i.select{|term| term[0] == S0 || ! term[1].empty? }
end

# ゴール goal から生成規則の印字表現を作成する
def pproduct(goal)
  [goal[0], ' -> ', *(goal[1])].map{|x| x.to_s }.join('')
end

# 項 term の印字表現を作成する
def pterm(term)
  '[' + [term[0], ' -> ', *(term[1]), '.', *(term[2])].map{|x| x.to_s }.join('') + ']'
end

# 計算状況として、スタック中のカーネル項を左揃えで、入力記号列を右揃えで出力する
def dump(stack, w)
  a = stack.collect{|i|
    '{' + kernel(i).collect{|term| pterm(term) }.join(', ') + '}'
  }.join(' ')
  b = w.join(' ')
  s = ' ' * ([1, 76 - a.length - b.length].max)
  puts a + s + b
end

g = []                     # 参考文献 「例 4.26」(ページ 264) より転載
# ここで、シンボルは非終端記号、文字列は終端記号とする。
g[0] = [:E, :E, '+', :T]   # E -> E+T
g[1] = [:E, :T]            # E -> T
g[2] = [:T, :T, '*', :F]   # T -> T*F
g[3] = [:T, :F]            # T -> F
g[4] = [:F, '(', :E, ')']  # F -> (E)
g[5] = [:F, 'id']          # F -> id

parse(g, ['id', '*', 'id', '$'])  # '$' は入力終了記号で、構文中に出現しないこと。

コードの見た目はシンプルですが、Ruby 処理系内部では、やらなくて良い重い演算を何度も繰り返しています。これぞ富豪的構文解析

こんな乱暴なやりかたでもシフト還元動作をしますし、当然ながら、計算状況も SLR 文法で作成した解析表と同じ変化を辿ります。そうはいっても、SLR および LALR(1) で CLOSURE 計算結果を使い捨てにするのはもったいないので、メモライズぐらいはしておいた方が良いかもしれません。使い捨て方式でも、データ構造をまともにして適切にキャッシュすることが条件になるものの、生成規則が 50 個以下の規模なら、案外、状態数が膨れ上がる LR(1) 解析器に向いているやりかたなのではなかろうかという気がしています。

$ ruby lr0.rb
{[S' -> .E]}                                                       id * id $
# shift id
{[S' -> .E]} {[F -> id.]}                                             * id $
# reduce F -> id
{[S' -> .E]}                                                          * id $
# goto F
{[S' -> .E]} {[T -> F.]}                                              * id $
# reduce T -> F
{[S' -> .E]}                                                          * id $
# goto T
{[S' -> .E]} {[E -> T.], [T -> T.*F]}                                 * id $
# shift *
{[S' -> .E]} {[E -> T.], [T -> T.*F]} {[T -> T*.F]}                     id $
# shift id
{[S' -> .E]} {[E -> T.], [T -> T.*F]} {[T -> T*.F]} {[F -> id.]}           $
# reduce F -> id
{[S' -> .E]} {[E -> T.], [T -> T.*F]} {[T -> T*.F]}                        $
# goto F
{[S' -> .E]} {[E -> T.], [T -> T.*F]} {[T -> T*.F]} {[T -> T*F.]}          $
# reduce T -> T*F
{[S' -> .E]}                                                               $
# goto T
{[S' -> .E]} {[E -> T.], [T -> T.*F]}                                      $
# reduce E -> T
{[S' -> .E]}                                                               $
# goto E
{[S' -> .E]} {[S' -> E.], [E -> E.+T]}                                     $
# accept

なお、計算状況にはカーネル項だけを出力しています。非カーネル項まで出力すると見た目が煩雑なので削りました。