So-net無料ブログ作成

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

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

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


nice!(0)  コメント(0)  トラックバック(0) 
共通テーマ:パソコン・インターネット

nice! 0

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。

×

この広告は1年以上新しい記事の更新がないブログに表示されております。