本文へスキップ

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


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

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


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


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

V−6 目次 V−8