導出 - mrsekut-p

導出

derivation

開始記号から初めて、非終端記号をその右辺によって置き換えていくこと

具体例

こんな生成規則を考える

code:bnf

E -> E + T | T

T -> T * F | F

F -> (E) | I

I -> a|b|c

この開始記号のEから例えば(a + b) * cを得ることを考える

以下のように導出できる

$ E\Rightarrow T \Rightarrow T * F \Rightarrow F * I \Rightarrow (E) * c \Rightarrow (a + b) * c

ところどころ省略しているがmrsekut.icon

$ E\xRightarrow{\ast}(a+b)*cのように書けるし、$ E\xRightarrow{+}(a+b)*cのようにも書ける

記号

$ \xRightarrow{\ast}

0回以上のステップで導出できることを表す

任意の終端記号$ \alphaに対して$ \alpha\xRightarrow{*}\alphaが成り立つ

$ \xRightarrow{+}

1回以上のステップで導出できることを表す

導出の途中に非終端記号が複数出てきた時に、どれから導出するかの話

導出の各ステップでの任意性を排除したい

例えば上の生成規則で、Eから(a + b) * cを導出を進め、以下のようになった時

$ E\Rightarrow T \Rightarrow T * F

この次に$ T*F\Rightarrow F * Fにするか、$ T*F\Rightarrow T*(E)にするかの話

参考