SSブログ

文脈自由文法から unit rule を取り除く [Scala]

前回の記事の続きで今度は unit rule と呼ばれるものを取り除く。

unit rule とは A → B のように右辺に単一の非終端記号がくる形をとるもの。 こういうのは B が左辺にくる規則を全部 A から直接派生する規則に置き換えてしまってよい。

def eliminateUnitRule(g: Grammar) = {
  def isTerminal(v: V) = v match { case Terminal(_) => true case _ => false}
  def isUnitRule(x: Rule) = x.rhs.length == 1 && !isTerminal(x.rhs(0))
  def step(rules: rules): rules = {
    val unitRule = rules.find(isUnitRule(_))
    unitRule match {
      case Some(rule) =>
        val newRules = rules filter {_.lhs == rule.rhs(0)} map {
          case Rule(_, rhs) => Rule(rule.lhs, rhs)
        }
        step(rules - rule ++ newRules)
      case None => rules
    }
  }
  Grammar(step(g.rules), g.start)
}

ここで以下のような文法を用意して、

val grammar = Grammar(
  Rules(
    'Number   ==> ('Integer),
    'Number   ==> ('Real),
    'Integer  ==> ('Digit),
    'Integer  ==> ('Integer, 'Digit),
    'Real     ==> ('Integer, 'Fraction, 'Scale),
    'Fraction ==> (Symbol("."), 'Integer),
    'Scale    ==> ('e, 'Sign, 'Integer),
    'Scale    ==> ('Empty),
    'Digit    ==> (Symbol("0")),
    'Digit    ==> (Symbol("1")),
    'Digit    ==> (Symbol("2")),
    'Digit    ==> (Symbol("3")),
    'Digit    ==> (Symbol("4")),
    'Digit    ==> (Symbol("5")),
    'Digit    ==> (Symbol("6")),
    'Digit    ==> (Symbol("7")),
    'Digit    ==> (Symbol("8")),
    'Digit    ==> (Symbol("9")),
    'Sign     ==> (Symbol("+")),
    'Sign     ==> (Symbol("-")),
    'Empty    ==> ()
  ),
  Start('Number)
)

前回のε規則の除去と合わせて以下のようにすると、

println(eliminateUnitRule(eliminateErule(grammar)))

こういう結果が得られて A → B の形の規則は存在しなくなる。(見やすく並べ替えた)

 Digit ==> 0
 Digit ==> 1
 Digit ==> 2
 Digit ==> 3
 Digit ==> 4
 Digit ==> 5
 Digit ==> 6
 Digit ==> 7
 Digit ==> 8
 Digit ==> 9
 Empty ==> ε
 Fraction ==> . Integer
 Integer ==> 0
 Integer ==> 1
 Integer ==> 2
 Integer ==> 3
 Integer ==> 4
 Integer ==> 5
 Integer ==> 6
 Integer ==> 7
 Integer ==> 8
 Integer ==> 9
 Integer ==> Integer Digit
 Number ==> 0
 Number ==> 1
 Number ==> 2
 Number ==> 3
 Number ==> 4
 Number ==> 5
 Number ==> 6
 Number ==> 7
 Number ==> 8
 Number ==> 9
 Number ==> Integer Digit
 Number ==> Integer Fraction
 Number ==> Integer Fraction Scale'
 Real ==> Integer Fraction
 Real ==> Integer Fraction Scale'
 Scale ==> e Sign Integer
 Scale ==> ε
 Scale' ==> e Sign Integer
 Sign ==> +
 Sign ==> -

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

nice! 0

コメント 0

コメントを書く

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

トラックバック 0

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