コンパイラの処理内容に関する次の記述を読んで，設問１〜４に答えよ。

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

設問１　次の記述中の に入れる正しい答えを，解答群の中から選べ。

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

図　構文木と探索順序の例

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

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

　　式：a op (b op c) op d

解答群

基本情報技術者試験

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

〔式の構文規則〕

(1) 式　→　項　　｜　式　op1　項

(2) 項　→　因子　｜　項　op2　因子

(3) 因子→　名前　｜　(式)

(4) 名前→　a　l　b　l　c　l　d　l　e

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

　　“｜”は，“又は”を意味する。

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

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

解答群

基本情報技術者試験

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

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

解答群

基本情報技術者試験

　後置表記法で表現された式は，スタックを使って左から右に評価することができる。 式 a＋b＋c×d を後置表記法に変換して評価する場合，スタックの 操作順序は である。 ここで，スタックを操作する命令として次の種類がある。 また，加算＋と乗算×は，それぞれ設問２の演算子 op1 と op2 に対応し， 演算の優先順位や結合規則は，〔式の構文規則〕に従うものとする。

解答群