本文へスキップ

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


Since 2016.4.19

平成30年度 技術士第一次試験問題【専門科目】

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通りある。

(1) x− (3+(y−5))
(2) ((x−3)+y) −5
(3) (x−3) + (y−5)
(4) (x−(3+y)) −5
(5) x− ((3+y)−5)

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

 (1)      (2)
 −        −
┌┴┐      ┌┴┐
x +      + 5
 ┌┴┐    ┌┴┐
 3 −    − y
  ┌┴┐  ┌┴┐
  y 5  x 3


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


 (4)     (5)
  −    −
 ┌┴┐  ┌┴┐
 − 5  x −
┌┴┐    ┌┴┐
x +    + 5
 ┌┴┐  ┌┴┐
 3 y  3 y

V−6 目次 V−8