文脈自由文法から 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 ==> -
コメント 0