次の曖昧さを持つ文法によって＜式＞を定義する。
＜式＞ ：：＝ ＜式＞ ＜演算＞ ＜式＞ ｜ ＜変数＞ ｜ ＜定数＞
＜演算＞：：＝ “＋” ｜ “－”
＜変数＞：：＝ “ｘ” ｜ “ｙ” ｜ “ｚ”
＜定数＞：：＝ “１” ｜ “２” ｜ “３” ｜ “４” ｜ “５”
ここでは文法の生成規則を、 ＢＮＦ (Backus Naur Form) で示している。
非終端記号は＜＞でくくり、終端記号は “ ”でくくって表す。次の式を
上の文法にあてはめたときに生成可能な構文木 (導出木) は何通りあるか。
ｘ － ３ ＋ ｙ － ５
① ４ ② ５ ③ ６ ④ ７ ⑤ ８
以下の５通りある。
－ －
┌┴┐ ┌┴┐
ｘ ＋ ＋ ５
┌┴┐ ┌┴┐
３ － － ｙ
┌┴┐ ┌┴┐
ｙ ５ ｘ ３
＋
┌─┴─┐
－ －
┌┴┐ ┌┴┐
ｘ ３ ｙ ５
－ －
┌┴┐ ┌┴┐
－ ５ ｘ －
┌┴┐ ┌┴┐
ｘ ＋ ＋ ５
┌┴┐ ┌┴┐
３ ｙ ３ ｙ
EXCELのマクロのご相談なら ファーストマクロ へ
