文脈自由文法から無駄を省く

文脈自由文法を与えられたときにその文法から non-productive な規則と unreachable な規則を取り除くアルゴリズムを Scala で実装してみました。

以下のような文脈自由文法を考えます（Parsing Techniques の p.49 より）。

S -> A B | D E
A -> a
B -> b C
C -> c
D -> d F
E -> e
F -> f D

* non-productive な規則の除去

まず、この文法の D とF に注目してみます。書き換えの中で D が登場すると D -> d F しか使える規則がないので D を d F に書き換えることになりますが、ここで現れた F を書き換えるには F -> f D を使うしかありません。すると再び D が現れるので D -> d F を使うことになります。

つまりこの文法では D または F はひとたび現れると取り除く（＝終端記号だけにする）ことができず、したがって文を生成することができなくなるということがわかります。このような規則を non-productive な規則と呼びます。

これを除去するには、以下の手順を踏みます。

- 終端記号だけが右辺に現れる規則は productive な規則とみなす
- 終端記号か productive な非終端記号だけが右辺に現れる規則も productive とみなしてよい
- これを繰り返して productive な規則に関する知識を増やしていき、新たな知識が得られなくなったところで終了。最後まで productive な規則に含まれなかったものは non-productive とみなされる。

上記の例でいうと、

1. 終端記号は productive なので A -> a, C -> c, E -> e の3つも productive
2. {A, C, E} は productive なので B -> b C も productive
3. {A, B, C, E} は productive なので S -> A B も productive

となり、

S -> A B
A -> a
B -> b C
C -> c
E -> e

が残ります。

* unreachable な規則の除去

残る規則をよくみると E -> e という規則は実はスタートシンボルから始まる書き換えで到達することはありませんので無駄です。このような規則を除去するには以下の手順を踏みます。

- スタートシンボルが左辺に現れる規則とその右辺の記号は reachable である
- reachable な記号が左辺に現れる規則も reachable である
- これを繰り返して reachable な規則に関する知識を増やしていき、新たな知識が得られなくなったところで終了

先ほどとパターンが同じです。このように与えられた初期知識を推論規則によって拡げていくアルゴリズムを closure algorithm というそうです。

以上を 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: Seq[V]) {
  override def toString = {
    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))
  }
}
implicit def sym2lh(sym: Symbol) = new LeftHand(sym)

val grammar = Grammar(
  Rules(
    'S ==> ('A, 'B),
    'S ==> ('D, 'E),
    'A ==> ('a),
    'B ==> ('b, 'C),
    'C ==> ('c),
    'D ==> ('d, 'F),
    'E ==> ('e),
    'F ==> ('d, 'D)
  ),
  Start('S)
)

def removeNonProductive(cfg: Grammar) = {
  def improve(unknown: rules, knownToBeProductive: rules): rules = {
    val newKnowledge =
      unknown.filter { rule =>
        rule.rhs.forall {
          case Terminal(_) => true /* base knowledge */
          case nt @ NonTerminal(sym) =>
            knownToBeProductive.exists { rule => rule.lhs == nt }
        }
      }
    if (newKnowledge.isEmpty) knownToBeProductive
    else improve(unknown -- newKnowledge, knownToBeProductive ++ newKnowledge)
  }
  Grammar(improve(cfg.rules, Set[Rule]()), cfg.start)
}

def removeUnreachable(cfg: Grammar) = {
  def improve(unknown: rules, knownToBeReachable: rules): rules = {
    val newKnowledge =
      unknown.filter { rule =>
        rule.lhs == cfg.start /* base knowledge */ ||
        knownToBeReachable.exists { rule2 => rule2.rhs contains rule.lhs }
      }
    if (newKnowledge.isEmpty) knownToBeReachable
    else improve(unknown -- newKnowledge, knownToBeReachable ++ newKnowledge)
  }
  Grammar(improve(cfg.rules, Set[Rule]()), cfg.start)
}

def cleanup(cfg: Grammar) = removeUnreachable(removeNonProductive(cfg))

println(grammar)
println(removeNonProductive(grammar))
println(cleanup(grammar))