基本情報技術者 2015年秋期午前（科目A）問19

問題文

コンパイラで構文解析した結果の表現方法の一つに四つ組形式がある。　(演算子、被演算子1、被演算子2、結果) この形式は、被演算子1と被演算子2に演算子を作用させたものが結果であることを表す。次の一連の四つ組は、どの式を構文解析したものか。ここで、

T_{1}

T_{2}

T_{3}

は一時変数を表す。

(*, B, C, T_{1})

(/, T_{1}, D, T_{2})

(+, A, T_{2}, T_{3})

選択肢

ア：

A + B * C / D

（正解）

イ：

A + B * C / T_{2}

ウ：

B * C + A / D

エ：

B * C + T_{1} / D

コンパイラの四つ組から式を復元する問題【午前2 解説】

要点まとめ

結論：与えられた四つ組を上から順に計算すると $T_{1} = B * C$ , $T_{2} = T_{1} / D$ , $T_{3} = A + T_{2}$ となり式は $A + B * C / D$ である。
根拠：各四つ組は (演算子, 被演算子1, 被演算子2, 結果) を示し、結果を次の被演算子として順に使って中間式を復元できる。
差がつくポイント：一時変数は単なる中間結果なので、その場の記号に惑わされず順に代入して元の結合順（グループ化）を確認すること。

正解の理由

正解: ア
各四つ組を順に読んで式を復元します。
1行目

(*, B, C, T_{1})

より

T_{1} = B * C

.
2行目

(/, T_{1}, D, T_{2})

より

T_{2} = T_{1} / D = (B * C) / D

.
3行目

(+, A, T_{2}, T_{3})

より

T_{3} = A + T_{2} = A + (B * C) / D

.
したがって元の式は

A + B * C / D

で、選択肢のうち該当するのはアです。

よくある誤解

「一時変数名そのものが元の式の記号」だと誤解し、 $T_{1}$ や $T_{2}$ を独立した元変数とみなしてしまう。
演算の優先順位や結合順を無視して左右の演算を入れ替えてしまう（特に除算は結合則が成り立たない）。
四つ組の順序を無視して並び替え、別の部分式を先に評価して誤答に至る。

解法ステップ

各四つ組を「結果 = 被演算子1 演算子被演算子2」の形で解釈する。
上から順に各結果を式に代入して中間式を復元する。
最後の結果（ここでは $T_{3}$ ）が表す式が元の全体式であることを確認する。
選択肢と照合して正しい表記を選ぶ。

選択肢別の誤答解説

ア（正解）: アは上記の復元手順に完全に一致します。 $T_{1} = B * C$ , $T_{2} = (B * C) / D$ , $T_{3} = A + (B * C) / D$ となり $A + B * C / D$ です。
イ: $A + B * C / T_{2}$ は $T_{2}$ を被演算子に残しており、四つ組では最後に $T_{2}$ は結果ではなく中間変数であるため一致しません。式中に未定義の $T_{2}$ が残るため不適。
ウ: $B * C + A / D$ は除算の被演算子が $A$ になっており、四つ組の 2 行目では除算は $T_{1} / D$ （つまり $(B*C)/D）であるため順序が異なります。
エ: $B * C + T_{1} / D$ は $T_{1}$ をそのまま式に残していますが、四つ組の最終結果は $T_{3}$ であり $A$ が加えられているため $A$ が欠けていて不一致です。

補足コラム

四つ組（quadruple）は三番地コードや中間表現の一種で、コンパイラの構文解析・中間コード生成段階でよく用いられます。各四つ組は「演算結果を一時変数へ代入する」ことを表すため、最終的に用いられる一時変数が示す式を辿ることで元の高級言語の式を復元できます。特に除算や非可換な演算が含まれる場合は結合順が結果を左右するので注意が必要です。

簡単なシミュレーション（参考、文字列操作）:

# 擬似的に四つ組から式を復元する例
quads = [('*','B','C','T1'),('/','T1','D','T2'),('+','A','T2','T3')]
env = {}
for op,a,b,res in quads:
    expr = f"({env.get(a,a)} {op} {env.get(b,b)})"
    env[res] = expr
print(env['T3'])  # => (A + ((B * C) / D))

FAQ

Q1: 四つ組の順序が異なれば式は変わりますか？
A1: はい。四つ組は生成順が通常評価順を示すため、順序を変えると中間結果の参照関係が崩れ元の式と一致しなくなります。

Q2: 一時変数は何を意味しますか？
A2: 一時変数（

T_{i}

）は中間結果を表す記号で、元の式の部分式を表現しています。最終的に使われない

T_{i}

は消去や最適化の対象になります。

Q3: 演算子の優先順位は四つ組に依存しますか？
A3: 四つ組はすでに結合順を反映した中間表現です。したがって、元の優先順位は四つ組の構造によって保持されています。

関連キーワード: 四つ組, 三番地コード, 中間コード, 一時変数, 構文解析, 演算子優先順位, コンパイラ最適化

← 前の問題へ次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！