平成30年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
V−7
次の曖昧さを持つ文法によって<式>を定義する。
 <式> ::= <式> <演算> <式> | <変数> | <定数>
 <演算>::= “+” | “−”
 <変数>::= “x” | “y” | “z”
 <定数>::= “1” | “2” | “3” | “4” | “5”

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

 x − 3 + y − 5

 @ 4  A 5  B 6  C 7  D 8



【正解】 A

以下の5通りある。

 −        −
┌┴┐      ┌┴┐
x +      + 5
 ┌┴┐    ┌┴┐
 3 −    − y
  ┌┴┐  ┌┴┐
  y 5  x 3


   +
 ┌─┴─┐
 −   −
┌┴┐ ┌┴┐
x 3 y 5


  −    −
 ┌┴┐  ┌┴┐
 − 5  x −
┌┴┐    ┌┴┐
x +    + 5
 ┌┴┐  ┌┴┐
 3 y  3 y

EXCELのマクロのご相談なら  ファーストマクロ  



V−6 目次 V−8
ファーストマクロ TOPページ