文脈自由文法からε規則を取り除く

文脈自由文法は右辺が空文字列を生成する規則を含んでも良い。右辺に何も書かないと収まりが悪いので代わりにεと書く。これをε規則という。例えば、

A -> ε

このようなε規則は文法から言語（＝生成する文の集合）を変えずに取り除くことが出来る。

除去するには A を使っている他の規則について A あり版と A なし版の規則に書き換えてあげればよい。
A あり版を残すのは A が左辺にくる規則はε規則だけじゃないかもしれないからだ。例えば、A -> a b c というのがあるかもしれない。逆にε規則だけだった場合は A なし版だけでいい。
そうやって書き換えた後は A -> ε は安心して消してよいはずである、ということになる。

Parsing Techniques に書いてあるアルゴリズムはもうちょっと間接的だった。

1. B -> αAβ があったら B -> αA'β と B -> αβ に置き換え、この段階では A -> ε は消さない。
2. すべてのε規則についてそういう操作をした後で、例えば A -> a b c があったら A' -> a b c という規則を追加してやる。ただし A -> ε に対して A' -> ε は追加しない。また A が左辺にくる規則が A -> ε だけだった場合は A' を使っている規則を全部除去する。

こうすると実はε規則はまだ（消してないから）残るのだが、スタートシンボルからは到達しないようになっているのであとで [1] のような方法でゆっくり掃除すればいい。

これを Scala で実装してみた。プライムをつける部分の実装はかなり手抜き。

import scala.collection.immutable._

// Type definitions for CFG
abstract class V
case class NonTerminal(sym: Symbol) extends V { override def toString = sym.name}
case class Terminal(sym: Symbol) extends V { override def toString = sym.name}

case class Rule(lhs: V, rhs: List[V]) {
  override def toString = {
    if (rhs.length == 0) lhs + " ==> ε" else
    lhs + " ==> " + rhs.map{_.toString}.reduceLeft[String]{_ + " " + _}
  }
}
type rules = Set[Rule]

case class Grammar(rules: rules, start: NonTerminal)

// DSL for CFG
object Rules { def apply(rules: Rule*) = Set(rules: _*) }
object Start { def apply(nt: Symbol) = NonTerminal(nt) }
class LeftHand(left: Symbol) {
  def ==> (right: Symbol*) = {
    def symbolToV(s: Symbol) =
      if (s.name(0).isUpperCase) NonTerminal(s) else Terminal(s)
    Rule(NonTerminal(left), right.map(symbolToV).toList)
  }
}
implicit def sym2lh(sym: Symbol) = new LeftHand(sym)

val grammar = Grammar(
  Rules(
    'S ==> ('L, 'a, 'M),
    'L ==> ('L, 'M),
    'L ==> (),
    'M ==> ('M, 'M),
    'M ==> ()
  ),
  Start('S)
)

def remove2[T](l: List[T], e1: T, e2: T): List[List[T]] = l match {
  case x::xs if (x == e1)
    => remove2(xs, e1, e2) flatMap { xs2 => List(xs2, e2::xs2) }
  case x::xs
    => remove2(xs, e1, e2) map { xs2 => x::xs2 }
  case Nil => List(List())
}

def prime(v: V) = v match {
  case Terminal(sym) => Terminal(Symbol(sym.name + "'"))
  case NonTerminal(sym) => NonTerminal(Symbol(sym.name + "'"))
}

def eliminateErule(g: Grammar) = {
  def isErule(x: Rule) = x.rhs.length == 0
  def step(rules: rules, vs: Set[V]): rules = {
    def seen(r: Rule) = vs.exists(_ == r.lhs)
    // find an ε-rule: A->ε
    val erule = rules find { r => isErule(r) && !seen(r) }
    erule match {
      case Some(Rule(lhs, rhs)) =>
        // get rules that refer ε-rules: B->αAβ
        val src = rules filter { x => x.rhs.exists(_ == lhs) }
        // replace each B->αAβ with B->αA'β and B->αβ
        val newRules = src.foldLeft(rules) { (rules, rule) =>
          // get B->αA'β and B->αβ from B->αAβ
          val replacedRules = remove2[V](rule.rhs, lhs, prime(lhs)).
                                map{ Rule(rule.lhs, _) }
          rules - rule ++ replacedRules
        }
        step(newRules, vs + lhs)
      case None => // no more ε-rules to eliminate
        addPrimeRules(rules, vs)
    }
  }
  def addPrimeRules(rules: rules, vs: Set[V]) = {
    vs.foldLeft(rules) { (rules, v) =>
      val primed = prime(v)
      val src = rules filter { x => x.lhs == v && !isErule(x) }
      if (src.isEmpty)
        rules filter { x => !x.rhs.exists(_ == primed) }
      else
        src.foldLeft(rules) { (rules, rule) =>
          rules + Rule(primed, rule.rhs)
        }
    }
  }
  Grammar(step(g.rules, Set[V]()), g.start)
}

println(grammar)
println(eliminateErule(grammar))

ε規則の除去は文脈自由文法をチョムスキー標準形にするための第一段階なのだが、続きはまたそのうち。

[1] http://rainyday.blog.so-net.ne.jp/2008-02-20