句構造文法から文を生成する

Type 0 以下の句構造規則を与えられるとひたすらその言語に含まれる文を生成していくプログラムを Scala で書いてみました。

キューを用意して幅優先探索の要領で、
- キューには最初はスタートシンボルだけ入っている
- キューから1つとって句構造規則で置き換えたものをまたキューに突っ込む
- キューから取ったものが文の形をしていれば（終端記号だけで構成されていれば）それを結果とする
というのを繰り返していきます。

import scala.collection.mutable._
import java.util.NoSuchElementException

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}

type rule = (Seq[V], Seq[V])
type sentential = Seq[V]

case class Grammar(rules: Seq[rule], start: NonTerminal)

case class SentenceIterator(grammar: Grammar) extends Iterator[sentential] {
  val queue = new Queue[sentential]
  queue += List(grammar.start)

  def lookahead() = {
    def isSentence(s: sentential) =
      s.forall { case Terminal(_) => true case _ => false }
    try {
      //println(queue)
      var s = queue.dequeue()
      while (!isSentence(s)) {
        for ((l, r) <- grammar.rules) {
          val i = s.indexOf(l)
          if (i >= 0)
            queue += (s.slice(0, i) ++ r ++ s.slice(i + l.length, s.length))
        }
        //println(queue)
        s = queue.dequeue()
      }
      Some(s)
    } catch {
      case e: NoSuchElementException => None
    }
  }

  var sentence: Option[sentential] = lookahead()
  def hasNext = sentence.isDefined
  def next() = {
    sentence match {
      case Some(s) => sentence = lookahead(); s
      case _ => error("")
    }
  }
}

// DSL for PSG
object Rules { def apply(pairs: rule*) = pairs.toList }
object Start { def apply(nt: Symbol) = NonTerminal(nt) }
def rule(left: Symbol*)(right: Symbol*): rule = {
  def symbolToV(s: Symbol) = 
    if (s.name(0).isUpperCase) NonTerminal(s) else Terminal(s)
  (left.map(symbolToV), right.map(symbolToV))
}

val grammar = Grammar(
  Rules(
    rule ('Name)                    ('tom),
    rule ('Name)                    ('dick),
    rule ('Name)                    ('harry),
    rule ('Sentence)                ('Name),
    rule ('Sentence)                ('List, 'End),
    rule ('List)                    ('Name),
    rule ('List)                    ('List, Symbol(","), 'Name),
    rule (Symbol(","), 'Name, 'End) ('and, 'Name)
  ),
  Start('Sentence)
)

/*
// the a^n b^n c^n grammar
val grammar = Grammar(
  Rules(
    rule ('S)         ('a, 'b, 'c),
    rule ('S)         ('a, 'S, 'Q),
    rule ('b, 'Q, 'c) ('b, 'b, 'c, 'c),
    rule ('c, 'Q)     ('Q, 'c)
  ),
  Start('S)
)
*/

val n = args(0).toInt
for (i <- SentenceIterator(grammar) take n)
  println(i)

文法の例は Parsing Techniques という本から採りました。コメントアウトされているほうは abc, aabbcc, aaabbbccc... を生成する規則なのですがどうも2個目まではすぐ見つかるけど3個目はこの方法だとすごく時間がかかるようです。（そしてこのイテレータの実装だと2個目を取り出すときに3個目も見つけておくようになっているため事実上1個までしか出力できない）