導出
from BNF記法
derivation
具体例
こんな生成規則を考える
bnfE -> 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
ところどころ省略しているが
E\xRightarrow{\ast}(a+b)*cのように書けるし、E\xRightarrow{+}(a+b)*cのようにも書ける
記号
\xRightarrow{\ast}
0回以上のステップで導出できることを表す
\xRightarrow{+}
1回以上のステップで導出できることを表す
導出の途中に非終端記号が複数出てきた時に、どれから導出するかの話
導出の各ステップでの任意性を排除したい
例えば上の生成規則で、
E から (a + b) * c を導出を進め、以下のようになった時E\Rightarrow T \Rightarrow T * F
この次にT*F\Rightarrow F * Fにするか、T*F\Rightarrow T*(E)にするかの話
参考