総視聴再生時間43万分以上(2017年5月13日現在)の動画で基本情報技術者試験の過去問&キーワード解説!スキマ時間に動画!〜これじょIT〜

PR広告

平成28年度秋 基本情報技術者試験午後 過去問2設問1 ソフトウェア 合格率アップ!動画付き解説!

コンパイラの字句解析と構文解析に関する次の記述を読んで、設問1~2に答えよ。

 コンパイラの字句解析では、原始プログラムを文字列として読み込んで、文字列中の文字の並びが字句として認識できるかどうかを解析し、その結果を字句の並びとして出力する。字句とは、原始プログラム中の名前や定数など、構文規則で規定されている文字の並びの最小単位である。構文解析では、字句解析が出力した字句を読み込みながら、字句の並びが構文規則で規定されている文法に合っているかどうかを解析し、その結果を構文木などの中間表現で出力する。

設問1 字句解析の処理について、次の記述中の に入れる正しい答えを、解答群の中から選べ。

 123. や 123.4e-1 など、構文規則で規定されている符号なし浮動小数点定数を例として字句解析の処理を考える。

"→"は、左側の構文要素が右側で定義されることを示す。

"|"は、"又は"を意味する。

"["と"]"で囲まれた部分は、省略可能を意味する。

[符号なし浮動小数点定数の構文規則]

符号なし浮動小数点定数 → 小数点定数[指数部]|数字列 指数部

小数点定数 → [数字列].数字列|数字列.

指数部 → e[符号]数字列

数字列 → 数字|数字列 数字

符号 → +|-

数字 → 0|1|2|3|4|5|6|7|8|9

 構文規則は、状態遷移図で表現することもできる。符号なし浮動小数点定数の構文規則に対する状態遷移図を、図1に示す。字句解析では、文字の並び中の文字を読み込みながら初期状態から状態を遷移させて、文字の並びを読み終えたときの状態が最終状態ならば、その文字の並びは符号なし浮動小数点定数であると判定する。ここで、円の中の数字は状態番号を示す。初期状態の状態番号は 0 であり、最終状態は二重円で示している。また、文字の並びは左から右に向けて1文字ずつ処理される。

平成28年度秋 基本情報技術者試験午後問2 ソフトウェア

a、b に関する解答群

  • ア:.
  • イ:e
  • ウ:指数部
  • エ:数字
  • オ:符号

解説 設問1

正解は

aには「ア .」が、

bには「イ e」が入ります!

[符号なし浮動小数点定数の構文規則]

符号なし浮動小数点定数 → 小数点定数[指数部]|数字列 指数部

小数点定数 → [数字列].数字列|数字列.

指数部 → e[符号]数字列

数字列 → 数字|数字列 数字

符号 → +|-

数字 → 0|1|2|3|4|5|6|7|8|9

上と、状態遷移図を見比べてみましょう!

平成28年度秋 基本情報技術者試験午後問2 ソフトウェア

[符号なし浮動小数点の構文規則]を見ると

符号なし浮動小数点定数は

符号なし浮動小数点定数 → 小数点定数[指数部]|数字列 指数部なので

小数点定数[指数部]

数字列 指数部

となります。

数字列 指数部となった場合、必ず先頭に数字列が入ります。

数字列は

数字列 → 数字|数字列 数字 なので

必ず数字が先頭に入ります。

状態遷移図を見ると、数字列が先頭に入るパターンはすでにあります。

数字以外が先頭にくるパターンはあるのでしょうか?

小数点定数の場合を考えます。

小数点定数は

小数点定数 → [数字列].数字列|数字列. なので

[数字列].数字列

数字列.

となります。

[数字列].数字列を考えると先頭の[数字列]は省略できるので、「.」が先頭にくる場合があります。

従って、状態遷移図のaには「ア .」が入ります!

続いて、数字が先頭に入った場合を考えます。その場合、「.」はすでに状態遷移図に記載しています。それ以外があるかを考えます。

符号なし浮動小数点定数 → 小数点定数[指数部]|数字列 指数部 で、小数点定数[指数部]の場合を考えます。

小数点定数は

小数点定数 → [数字列].数字列|数字列. なので

数字が並びます。これは状態遷移図で表現されています。

小数点定数[指数部]の「小数点定数」を表現した後、[指数部]ですが、指数部は

指数部 → e[符号]数字列 です。

数字が続いた後にeが入る可能性があります。

従って、状態遷移図のbには「イ e」が入ります!

設問2

構文解析の処理について、次の記述中の に入れる正しい答えを、解答群の中から選べ。

 構文規則で規定されている式を例として、構文解析の処理を考える。式の構文解析では、式を構成する演算子や名前などの字句を、式の左から右に読み込みながら、字句の並びが構文規則で規定されている文法に合っているかどうかを解析し、その結果を構文木として出力する。例えば、2項演算子 op、名前 v、w、x を構成要素とする式 v op w op x は、次の演算順序①、②になるように解釈され、その結果は、図2に示す2分木で表現する構文木として出力される。図2の構文木では、深さ優先でたどりながら、帰り掛けに節の演算子を評価する。

〔演算順序〕

v と w に対して演算 op を施す。

①の結果と x に対して演算 op を施す。

平成28年度秋 基本情報技術者試験午後問2 ソフトウェア

 式の構文規則では、式の構文を規定するだけではなく、演算子の優先順位も規定する。2項演算子 op1 と op2、名前 v、w、x、y、z を構成要素とする式の構文規則を定義する。ここで、"演算子 op1 の優先順位は、演算子 op2 の優先順位よりも高い"とする。これを規定する場合、式の構文規則は次のとおりになる。この構文規則で受理される式の例を、例1に示す。

〔式の構文規則〕

 式  → 項 |c

 項  → 因子|項 op1 因子

 因子 → 名前

 名前 → v|w|x|y|z

  例1:v op2 w op1 x

 さらに、式の構文に括弧を追加し、"括弧を含む式では、演算の優先順位は、括弧内の演算の方が高い"とする。これを規定する場合、因子の構文規則は次のとおりになる。この構文規則で受理される式の例を、例2に示す。

〔因子の構文規則〕

 因子 → 名前|(d)

  例2:v op2 w op1 (x op2 y) op1 z

 例2で示す式を解析したとき、出力される構文木はeとなる。

c に関する解答群

  • ア:式
  • イ:式 op2 因子
  • ウ:式 op2 項
  • エ:式 op2 名前

d に関する解答群

  • ア:因子
  • イ:項
  • ウ:式
  • エ:名前

e に関する解答群

平成28年度秋 基本情報技術者試験午後問2 ソフトウェア

設問2 c, dの解説動画

設問2 cの解説

正解は「ウ:式 op2 項」です!

例1:v op2 w op1 x

を例として、正解を前提に考えてみます。

式  → 項 |式 op2 項は

式 op2 項

となります。v op2 w op1 x実現するには

式 op2 項

を選択します。

ここで、式を項とすると、区別するために数字をつけています

項1 op2 項2

となります。

項は

因子

項 op1 因子

です。

v op2 w op1 x実現するために

項1を因子

項2に項 op1 因子とします。

すると

項1 op2 項2

は、区別するための数字をつけると

因子1 op2 項3 op1 因子2

さらに、項3を因子とすると

因子1 op2 因子3 op1 因子2

となります。

因子は名前です。すると

名前1 op2 名前3 op1 名前2

となり

名前 → v|w|x|y|z

です。

名前1をv

名前3をw

名前2をx

とすると

v op2 w op1 xを実現できます!

設問2 dの解説

dには「ウ 式」が入ります。

例2を例とすると、かっこがある部分は(x op2 y)です。

かっこの中身「x op2 y」を表現するには、式が必要です。

式 → 項 | 式 op2 項

なので

式 op2 項

を選びます。

この時の式は、項を選びます。区別のため数字を入れると

項1 op2 項

となります。

項 → 因子 | 項 op1 因子

です。

項1と項2ともに、因子を選択すると

因子1 op2 因子2

となり、

因子 → 名前 | (式)

なので、両方とも名前を選択します。

名前1 op2 名前2

となり、

名前 → v|w|x|y|z

です。

名前1をx、名前2をyとすると

(x op2 y)

が表現できます。

従って、dには「ウ 式」が入ります。

設問2 eの解説

作成中

PR広告

フェイスブックコメント

平成28年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成28年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成28年度春 基本情報技術者試験 午後 テキスト・動画解説

平成28年度春 基本情報技術者試験 午前 テキスト・動画解説

平成27年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午前 テキスト・動画解説

平成26年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成26年度春 基本情報技術者試験 午前 テキスト・動画解説