技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。

�W−９

次の曖昧さをもつ文法によって <式> を定義する。

　<式> ::＝ <式> <演算> <式> | <変数> | <定数>
　<演算> ::＝　"＋" | "−"
　<変数> ::＝　"ｘ" | "ｙ" | "ｚ"
　<定数> ::＝　"1" | "2" | "3" | "4" | "5"

ここでは文法の生成規則を、BNF (Backus Naur Form) で示している。非終端記号は <> でくくり、終端記号は "" でくくって表す。次の式を上の文法にあてはめたときに生成可能な構文木 (導出木) は何通りあるか。

　ｘ − 3 ＋ ｙ − 5

---

正解

�C

---

解説

以下の5通りある。

(1) ｘ− (3＋(ｙ−5))
(2) ((ｘ−3)＋ｙ) −5
(3) (ｘ−3) ＋ (ｙ−5)
(4) (ｘ−(3＋ｙ)) −5
(5) ｘ− ((3＋ｙ)−5)

それぞれの構文木は以下のとおりである。

　(1) 　　　　　(2)
　−　　　　　　　　−
┌┴┐　　　　　　┌┴┐
ｘ　＋　　　　　　＋　5
　┌┴┐　　　　┌┴┐
　3　−　　　　−　ｙ
　　┌┴┐　　┌┴┐
　　ｙ　5　　ｘ　3


　(3)
　　　＋
　┌─┴─┐
　−　　　−
┌┴┐　┌┴┐
ｘ　3　ｙ　5


　(4) 　　　　(5)
　　−　　　　−
　┌┴┐　　┌┴┐
　−　5　　ｘ　−
┌┴┐　　　　┌┴┐
ｘ　＋　　　　＋　5
　┌┴┐　　┌┴┐
　3　ｙ　　3　ｙ

�W−８

目次

�W−１０

---