Unger's method による構文解析

Parsing Techniques で Unger's method として紹介されている方法は、割と分かりやすい一種の分割統治法です。

Expr := Term | Expr + Term
Term := Factor | Term * Factor
Factor := ( Expr ) | i

という文法があったとして、

「Expr は "(i+i)*i" を派生するか？」という問題は「Expr := Term | Expr + Term」という規則から

1. 「Term は "(i+i)*i" を派生するか？」
2. 「"(i+i)*i" を3つに分解すると、Expr, +, Term がそれぞれを派生するか？」

という問題に分割されます。さらに2の問いは、

2a. 「Expr が "i" を、+ が "+" を、Term が "i)*i" を派生するか？」
2b. 「Expr が "i" を、+ が "+i" を、Term が ")*i" を派生するか？」
2c. 「Expr が "i" を、+ が "+i)" を、Term が "*i" を派生するか？」
2d. 「Expr が "i" を、+ が "+i)*" を、Term が "i" を派生するか？」
…

などなどの問いに分割されます。これを再帰的に処理していけば必ず答えに辿り着くというわけです。終端記号がある文字（列）を派生するかどうかはそれ以上分割する必要のない問いです。

ここで気をつける必要があるのは、文脈自由文法一般を考えたときに、

1. 規則の右辺に長さゼロの文字列がくる場合がある（本当は「Expr が "" を、+ が "" を、Term が "(i+i)*i" を派生するか？」を最初に問わなければならない）
2. ループして同じ問いに辿り着く場合がある（1の結果としても、文法に固有の理由からも）

という点です。

これらは生じた場合に「問題が小さくならない」ということにつながります。再帰的なアルゴリズムで問題が小さくならないと結果は無限ループ（というかスタックオーバーフロー）になります。
したがってアルゴリズムは「これまでに発した問い」を覚えておいて前にも聞いたことがある問いが出てきた場合はそこで打ち切るようにしなければなりません。

以上を Scala で実装してみたのが以下です。object Unger より手前までの部分は [1] で使った定義の使い回しです。

import scala.collection.immutable._

// Type definitions for CFG
abstract class V
case class Terminal(sym: Symbol) extends V
case class NonTerminal(sym: Symbol) extends V
case class Rule(lhs: V, rhs: Seq[V]) 
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(
    'Expr   ==> ('Term),
    'Expr   ==> ('Expr, Symbol("+"), 'Term),
    'Term   ==> ('Term, Symbol("*"), 'Factor),
    'Term   ==> ('Factor),
    'Factor ==> (Symbol("{"), 'Expr, Symbol("}")),
    'Factor ==> 'i
  ),
  Start('Expr)
)

object Unger {
  def partition(offset: Int, marbles: Int, cups: Int): List[List[(Int,Int)]] = {
    if (cups == 1) List(List((offset, marbles)))
    else
      if (marbles == 0) List(List.make(cups, (offset, 0)))
      else
        (0 to marbles).toList.flatMap{ l =>
          partition(offset + l, marbles - l, cups - 1).map{(offset, l)::_}
        }
  }
  def recognize(str: List[Symbol], grammar: Grammar) = {
    def -*->(v: V, str: List[Symbol], asked: Set[(V,List[Symbol])]): Boolean = {
      //println((v, str))
      if (asked contains Pair(v, str)) false
      else
        v match {
          case Terminal(sym) => str == List(sym)
          case nt @ NonTerminal(sym) => 
            grammar.rules.filter{_.lhs == nt} exists { rule =>
              partition(0, str.size, rule.rhs.size) exists { p =>
                (p zip rule.rhs.toList) forall {
                  case ((offset, len), v2) =>
                    -*->(v2, str.slice(offset, offset+len), asked + Pair(v,str))
                }
              }
            }
        }
    }
    -*->(grammar.start, str, ListSet.empty[(V, List[Symbol])])
  }
}

val str = args(0).split("").toList.tail.map{Symbol(_)}
println(Unger.recognize(str, grammar))

実行例:

PS D:\scala> scalac -Xscript Unger Unger.scala
PS D:\scala> scala Unger i
true
PS D:\scala> scala Unger i+
false
PS D:\scala> scala Unger i*i
true
PS D:\scala> scala Unger +i*i
false
PS D:\scala> scala Unger i+i*i
true
PS D:\scala> scala Unger "{i+i*i"
false
PS D:\scala> scala Unger "{i+i}*i"
true

今回の実装では文が言語の中に含まれるかどうかを判定するだけでセマンティクスは与えられていませんが、最初に見つけたパースだけで諦めずに全ての可能なパースを探すようにすれば文脈自由文法の構造的多義性にも対応可能なはずです。

ところでコード中の文法で括弧を中括弧にしたのは Windows 上の Scala でコマンドライン引数に閉じ小括弧を使うと変な動作になることを見つけてしまったからです。多分 scala.bat のバグだと思いますが…

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