FE22春後問2

FE22春後問2

基本情報技術者試験平成22年度春午後問2


 コンパイラの処理内容に関する次の記述を読んで,設問 1 ~ 4 に答えよ。


 コンパイラとは,プログラム言語で記述された原始プログラムを翻訳して目的プログラムを生成するためのソフトウェアである。コンパイラの処理過程において,構文解析は字句解析が出力する字句を読み込みながら構文木を生成し,その字句の列が文法で許されているかどうかを解析する。


設問1

 次の記述中の[   ]に入れる正しい答えを,解答群の中から選べ。


 2 項演算子から成る式の構文は,2 分木で表現される。2 分木から目的プログラムを生成するには,2 分木を深さ優先で探索しながら,帰り掛けにの演算子を評価する。式の構文木と探索順序の例を図に示す。

f:id:tamagopanda:20100729204147p:image

 探索の結果,図の構文木の例は,a と b に対して演算 op を施し,その結果と c に対して演算 op を施すと解釈される。

 括弧を含む式では,演算の優先度は,括弧内の優先度が高く,それ以外は左から右に式を評価する。このとき,次の式に対する構文木は[   ]である。


式: a op (b op c) op d


f:id:tamagopanda:20100729204148p:image


設問2

 次の記述中の[   ]に入れる正しい答えを,解答群の中から選べ。


 プログラム言語の文法は,構文規則で規定される。式の構文規則では式の構文を規定しているだけでなく,演算子の優先順位や結合規則も規定している。例として,優先順位が異なる演算子op 1, 0p2と括弧を用いた式の構文規則を考える。

〔式の構文規則〕
(1)式 → 項|式 op1 項
(2)項 → 因子|項 op2 因子
(3)因子 → 名前|(式)
(4)名前 → a|b|c|d|e
 “→”は,左側の構文要素が右側で定義されることを示す。
 “|”は,“又は”を意味する。

 深さ優先で探索すると仮定すれば,与えられた式に含まれる演算子 op1 と op2 の演算順序は,〔式の構文規則〕から生成可能な構文木で表現できる。例えば,次の式に対して〔式の構文規則〕を適用した構文木は [   ] である。



式: a op1 b op2 c op2 (d op1 e)


f:id:tamagopanda:20100729204149p:image


設問3

 次の記述中の [   ] に入れる正しい答えを,解答群の中から選べ。


 構文解析した結果は,構文木で表現する以外に,2 分木と等価な表現の後置表記法(逆ポーランド表記法)で表現できる。後置表記法では,演算で使用する二つのオペランドを演算子の前に記述する。そして,後置表記法は,構文木を探索して得られる演算順序を表現したものであると考えることができる。例えば,設問 1 の図の例で,演算子 op を加算+とした場合,後置表記法では ab+c+となる。これは,a と b を加算し,その結果と c を加算することを表している。

 後置表記法を用いて式 a×b+c×d+e を表現すると [   ] になる。ここで,加算+と乗算×は,それぞれ設問 2 の演算子 op1 と op2 に対応し,演算の優先順位や結合規則は,〔式の構文規則〕に従うものとする。

解答群
ア abcd ××+ e +
イ abc ×+ d × e +
ウ ab × cd ×+ e +
エ ab × c + d × e +

設問4

 次の記述中の [   ] に入れる正しい答えを,解答群の中から選べ。


 後置表記法で表現された式は,スタックを使って左から右に評価することができる。式a+b+c×dを後置表記法に変換して評価する場合,スタックの操作順序は [   ] である。ここで,スタックを操作する命令として次の種類が

ある。また,加算+と乗算×は,それぞれ設問 2 の演算子 op1 と op2 に対応し,

演算の優先順位や結合規則は,〔式の構文規則〕に従うものとする。


push(x):
スタックに x をプッシュする。

f:id:tamagopanda:20100729204151p:image

add
スタックからオペランドを二つポップして加算し,その結果をスタックにプッシュする。

f:id:tamagopanda:20100729204150p:image

mul:
スタックからオペランドを二つホップして乗算し,その結果をスタックにプッシュする。

解答群
ア push(a) → addpush(b) → addpush(c) → mul → push(d)
イ push(a) → push(b) → addpush(c) → mul → push(d) → add
ウ push(a) → push(b) → addpush(c) → push(d) → mul → add
エ push(a) → push(b) → push(c) → push(d) → addadd → mul


問題掲載者による注意書き

  • 実際の問題文をテキスト化するにあたり,表記の難しい部分を以下のように置き換えている。
    • 空欄[ a ][ b ][ c ]等は,実際の問題文中では,四角で囲まれた,a,b,c だったが,[ ]で置き換えた。