基本情報技術者 2010年 春期 午後 問02
コンパイラの処理内容に関する次の記述を読んで、設問1〜4に答えよ。
コンパイラとは、プログラム言語で記述された原始プログラムを翻訳して目的プログラムを生成するためのソフトウェアである。コンパイラの処理過程において、構文解析は字句解析が出力する字句を読み込みながら構文木を生成し、その字句の列が文法で許されているかどうかを解析する。
設問1：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
2項演算子から成る式の構文は、2分木で表現される。2分木から目的プログラムを生成するには、2分木を深さ優先で探索しながら、帰り掛けに節の演算子を評価する。式の構文木と探索順序の例を図に示す。
探索の結果、図の構文木の例は、aとbに対して演算opを施し、その結果とcに対して演算opを施すと解釈される。
括弧を含む式では、演算の優先度は、括弧内の優先度が高く、それ以外は左から右に式を評価する。このとき、次の式に対する構文木はである。
式：a op ( b op c ) op d
解答群
模範解答
オ
解説
解答の導き方
この問題では、式の計算順を構文木に表します。構文木では、演算子を節（木の途中にある点）に置き、その演算子が使う二つの値や式を左右の子として表します。
まず、問題文には「括弧内の優先度が高く、それ以外は左から右に式を評価する」とあります。したがって、式：a op ( b op c ) op dは、次の順に計算します。
- 括弧の中のb op cを計算します。
- その結果とaで、a op ( b op c ) を計算します。
- その結果とdで、最後のopを計算します。
つまり、式全体のまとまりは、((a op (b op c)) op d) です。
構文木では、最後に行う演算が根（木の最上部の節）になります。最後の演算は「a op ( b op c ) の結果」とdに対するopなので、根はop、左の子はそれまでの計算結果、右の子はdです。
さらに、左の子のopは、aと「括弧内の計算結果」を使います。そのため、左の子はopで、その左の子がa、右の子がopです。括弧内のopの左右には、それぞれbとcが入ります。
この形に当てはまるのはオです。図の例も、先に左側のopを計算し、その結果と右側の値で根のopを計算する構造になっています。
誤りやすいポイント
- 括弧の中を先に計算するだけでなく、括弧の外の演算も左から右にまとめます。括弧の中を計算した後、aとの演算を行い、その結果とdの演算を行います。
- 根を最初に行う演算だと考えないようにします。根は式全体の最後に行う演算です。
- 括弧内のbとcが、aやdと同じ階層の子になるわけではありません。b op cは一つのまとまりとして、構文木の中に入ります。
- 演算の順序だけでなく、左側と右側の値の並びも式のとおりに保ちます。
FAQ
Q: なぜ最後の演算を構文木の根に置くのですか？
A: 根の演算を行うには、その左右に渡す値が必要だからです。先に計算する部分を子の節として表し、最後に行う演算を根に置きます。
A: 根の演算を行うには、その左右に渡す値が必要だからです。先に計算する部分を子の節として表し、最後に行う演算を根に置きます。
Q: 「帰り掛けに節の演算子を評価する」とは、どういう意味ですか？
A: 子に当たる式を先にたどり、その計算が終わって戻ってきたときに、その節の演算子を処理するという意味です。このため、括弧内などの部分式が先に計算されます。
A: 子に当たる式を先にたどり、その計算が終わって戻ってきたときに、その節の演算子を処理するという意味です。このため、括弧内などの部分式が先に計算されます。
Q: 括弧がない場合も、いつも左から右に評価しますか？
A: この問題では、括弧の外は左から右に評価すると指定されています。実際の式では演算子の種類によって優先順位が異なることもあるため、問題文の条件を確認します。
A: この問題では、括弧の外は左から右に評価すると指定されています。実際の式では演算子の種類によって優先順位が異なることもあるため、問題文の条件を確認します。
関連キーワード: 構文木、二分木、演算子の優先順位、深さ優先探索、後行順
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
プログラム言語の文法は、構文規則で規定される。式の構文規則では式の構文を規定しているだけでなく、演算子の優先順位や結合規則も規定している。例として、優先順位が異なる演算子op1、op2と括弧を用いた式の構文規則を考える。
〔式の構文規則〕
(1) 式 → 項 | 式 op1 項
(2) 項 → 因子 | 項 op2 因子
(3) 因子 → 名前 | ( 式 )
(4) 名前 → a | b | c | d | e
“→”は、左側の構文要素が右側で定義されることを示す。
“|”は、“又は”を意味する。
深さ優先で探索すると仮定すれば、与えられた式に含まれる演算子op1とop2の演算順序は、〔式の構文規則〕から生成可能な構文木で表現できる。例えば、次の式に対して〔式の構文規則〕を適用した構文木はである。
式：a op1 b op2 c op2 ( d op1 e )
解答群
模範解答
イ
解説
解答の導き方
この問題では、演算子の優先順位と結合の向きを、構文規則から読み取ります。
まず、規則(1)では「式」の中に「項」が含まれ、規則(2)では「項」の中に「因子」が含まれています。つまり、式を組み立てるときは、まず「項」のまとまりを作り、その中で「因子」を組み合わせます。この階層から、op2はop1より優先順位が高いと分かります。
次に、規則(1)の「式 → 式op1項」に注目します。op1の左側が「式」なので、op1が複数ある場合は左側からまとまります。同様に、規則(2)の「項 → 項op2因子」から、op2も複数ある場合は左側からまとまります。
与えられた式では、最初のop1より右側が、op2を含む「項」です。したがって、全体は「a」と、残りのop2を含むまとまりをop1で結んだ形になります。
その右側の「項」では、op2が左側からまとまるため、まず「b op2 c」ができます。そのまとまりと「( d op1 e )」が、さらにop2で結ばれます。括弧内の「d op1 e」は、括弧の中で別の式としてまとまります。
この構造は、根がop1で、その左の子がa、右の子がop2です。右側のop2の左には「b op2 c」の木があり、右には「d op1 e」の木があります。解答群では、この構造に当たるのがイです。
誤りやすいポイント
- op1とop2を同じ優先順位だと考えると、木の最上位の演算子を誤りやすくなります。規則ではop2が「項」の中で使われるため、op1より優先されます。
- 「b op2 c op2 ( d op1 e )」のop2を右側からまとめるのは誤りです。規則(2)では左側が「項」なので、op2は左からまとまります。
- 括弧内のop1を、括弧の外にあるop1とひと続きに考えてはいけません。括弧内は独立した式として構文木に表します。
FAQ
Q: op2がop1より優先されるのは、どこから分かりますか？
A: op2は「項」の規則で使われ、op1は「式」の規則で使われています。「式」の中に「項」が含まれるため、先に項のまとまりが作られます。
A: op2は「項」の規則で使われ、op1は「式」の規則で使われています。「式」の中に「項」が含まれるため、先に項のまとまりが作られます。
Q: op2が複数あるとき、なぜ左からまとまるのですか？
A: 規則(2)が「項 → 項op2因子」となっているからです。左側に既にできた「項」を置き、そこへ次の因子を結び付ける形です。
A: 規則(2)が「項 → 項op2因子」となっているからです。左側に既にできた「項」を置き、そこへ次の因子を結び付ける形です。
Q: 括弧内のop1が、式全体のop1より先に処理されるのはなぜですか？
A: 括弧内は、規則(3)によって「因子」の一つとして扱われます。その因子を作るために、括弧の中の式の構造を先にたどります。
A: 括弧内は、規則(3)によって「因子」の一つとして扱われます。その因子を作るために、括弧の中の式の構造を先にたどります。
関連キーワード: 構文解析、構文木、演算子の優先順位、結合規則、深さ優先探索
設問3：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
構文解析した結果は、構文木で表現する以外に、2分木と等価な表現の後置表記法（逆ポーランド表記法）で表現できる。後置表記法では、演算で使用する二つのオペランドを演算子の前に記述する。そして、後置表記法は、構文木を探索して得られる演算順序を表現したものであると考えることができる。例えば、設問1の図の例で、演算子opを加算+とした場合、後置表記法ではa b + c +となる。これは、aとbを加算し、その結果とcを加算することを表している。
後置表記法を用いて式a × b + c × d + eを表現するとになる。ここで、加算+と乗算×は、それぞれ設問2の演算子op1とop2に対応し、演算の優先順位や結合規則は、〔式の構文規則〕に従うものとする。
解答群
ア：a b c d × × + e +
イ：a b c × + d × e +
ウ：a b × c d × + e +
エ：a b × c + d × e +
模範解答
ウ
解説
解答の導き方
この問題では、式を計算する順序を、後置表記法で表します。後置表記法は、演算の対象となる値であるオペランドを先に書き、その後ろに演算子を書く方法です。問題文にも「二つのオペランドを演算子の前に記述する」とあります。
まず、式「a × b + c × d + e」を、演算の優先順位に従って整理します。乗算の「×」は加算の「+」より先に計算するので、式は次の順に計算されます。
- を計算します。
- を計算します。
- 1と2の結果を加算します。
- その結果に を加算します。
加算は左から結び付くため、式のまとまりは です。
次に、この計算順序を後置表記法に置き換えます。
- は、オペランドを先に書いて「a b ×」です。
- は、「c d ×」です。
- それぞれの乗算結果を加算するので、その後ろに「+」を置きます。
- 最後に を加算するので、さらに後ろに「e +」を置きます。
したがって、後置表記法は「a b × c d × + e +」となり、該当するのはウです。構文木で考える場合も、子のノードを先にたどり、その後に親の演算子を置くことで、同じ順序になります。
誤りやすいポイント
- 式を左からそのまま読んで、演算子を置く位置を決めないようにします。後置表記法では、演算のまとまりごとに、オペランドの後ろへ演算子を置きます。
- 「×」を先に計算することを忘れると、式のまとまりが変わります。まず、どの演算を先に行うかを確認してから表記します。
- 「+」が2回あるため、後置表記にも「+」が2回必要です。演算子の数は、元の式で行う演算の数と対応します。
- 演算子を一つのまとまりの最後に置くとき、その直前に並ぶ二つの値は、単なる文字とは限りません。すでに計算された結果も、次の演算のオペランドになります。
FAQ
Q: なぜ「a b × c d ×」だけでは完成しないのですか？
A: これは、 と をそれぞれ計算したところまでです。その二つの結果を加算する「+」と、さらに を加算する「+」も書く必要があります。
A: これは、 と をそれぞれ計算したところまでです。その二つの結果を加算する「+」と、さらに を加算する「+」も書く必要があります。
Q: 後置表記法では、かっこを書かなくても計算順序が分かるのですか？
A: はい。オペランドと演算子の並び方によって、どの演算を先に行うかが決まります。そのため、通常はかっこを使わなくても順序を表せます。
A: はい。オペランドと演算子の並び方によって、どの演算を先に行うかが決まります。そのため、通常はかっこを使わなくても順序を表せます。
Q: 構文木と後置表記法はどう関係しますか？
A: 構文木は、どの演算がどの値や計算結果を使うかを木の形で表します。後置表記法は、その木を子から親の順にたどったときの並びで、演算順序を表します。
A: 構文木は、どの演算がどの値や計算結果を使うかを木の形で表します。後置表記法は、その木を子から親の順にたどったときの並びで、演算順序を表します。
関連キーワード: 構文解析、構文木、後置表記法、演算子の優先順位、結合規則
設問4：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
後置表記法で表現された式は、スタックを使って左から右に評価することができる。式a + b + c × dを後置表記法に変換して評価する場合、スタックの操作順序はである。ここで、スタックを操作する命令として次の種類がある。また、加算+と乗算×は、それぞれ設問2の演算子op1とop2に対応し、演算の優先順位や結合規則は、〔式の構文規則〕に従うものとする。
push(x)：スタックにxをプッシュする。
add：スタックからオペランドを二つポップして加算し、その結果をスタックにプッシュする。
mul：スタックからオペランドを二つポップして乗算し、その結果をスタックにプッシュする。
解答群
ア：push(a) → add → push(b) → add → push(c) → mul → push(d)
イ：push(a) → push(b) → add → push(c) → mul → push(d) → add
ウ：push(a) → push(b) → add → push(c) → push(d) → mul → add
エ：push(a) → push(b) → push(c) → push(d) → add → add → mul
模範解答
ウ
解説
解答の導き方
後置表記法（演算子を、計算する値の後ろに置く書き方）に直し、左から順にスタックを操作します。スタックは、値を積み重ねて保存し、最後に積んだ値から取り出す仕組みです。
この式では、加算を左から行い、乗算を加算より先に行います。そのため、計算するまとまりは です。これを後置表記法で表すと、まず を「a b +」、次に を「c d ×」とし、最後にそれらを加算するので、「a b + c d × +」となります。
pushは値をスタックに積みます。addとmulは、それぞれスタックの上から値を2個取り出して計算し、結果を積み直します。以下の表では、スタックの内容を下から上の順に示します。
したがって、操作の並びは「push(a) → push(b) → add → push(c) → push(d) → mul → add」です。解答群ではウに当たります。
誤りやすいポイント
- 乗算を加算より先に行うことと、スタック上で乗算を先に実行することは、必ずしも同じではありません。ここでは と の計算は別々のまとまりなので、先に を計算しても、式のまとまりは変わりません。
- addやmulを行う前には、スタックに値が2個必要です。push(a) の直後にaddを行うなど、値が足りない操作順は誤りです。
- addはスタックの上から2個の値を取り出します。図の例では上の値がx、その下がyで、結果はy+xです。どの値がスタックの上にあるかを確認しましょう。
FAQ
Q: 乗算を含む式なのに、なぜ最初にaddを行うのですか？
A: 優先順位は、式をどのまとまりとして計算するかを決めます。この式は なので、 と はそれぞれ独立したまとまりです。後置表記法では、 の計算を先にしてから を計算しても、最後に2つの結果を加算すれば同じ式になります。
A: 優先順位は、式をどのまとまりとして計算するかを決めます。この式は なので、 と はそれぞれ独立したまとまりです。後置表記法では、 の計算を先にしてから を計算しても、最後に2つの結果を加算すれば同じ式になります。
Q: addは、取り出した2つの値をどの順番で加算しますか？
A: 図のとおり、スタックの上にある値をx、その下にある値をyとすると、結果はy+xです。今回は加算と乗算を使うため、順番を確認しながらスタックの動きを追う練習になります。
A: 図のとおり、スタックの上にある値をx、その下にある値をyとすると、結果はy+xです。今回は加算と乗算を使うため、順番を確認しながらスタックの動きを追う練習になります。
関連キーワード: 後置表記法、スタック、構文木、演算子の優先順位、結合規則
