基本情報技術者 2011年 秋期 午後 問08
次のプログラムの説明及びプログラムを読んで、設問1，2に答えよ。
1行の代入文を解析し、演算の優先順位に従って一つずつ演算を行っていく一連の代入文に変換して出力する。代入文とその出力結果の例を、次に示す。ここで、出力結果にあるwk#1などは、中間結果を保存するための作業変数である。
（代入文の例）
Ans=X1+10*X2
（出力結果の例）
wk#1=10*X2
wk#2=X1+wk#1
Ans=wk#2
代入文の形式は、次のとおりである。
変数=式
“=”は代入演算子で、右辺の式の値を評価した結果を、左辺の変数に代入する。
式は、変数又は定数（以下、項という）の一つ以上の並びで、項が二つ以上のときは各項の間に算術演算子を置く。変数は、英字（“A”〜“Z”、“a”〜“z”）で始まる1文字以上の英数字の列である。定数は、1文字以上の数字（“0”〜“9”）の列である。
算術演算子は、加算（“+”）、減算（“-”）、乗算（“*”）、除算（“/”）の4種類である。乗除算は加減算に優先する。同一優先順位の算術演算子は、左から順に演算する。
〔代入文の構文解析〕
解析処理は、次の手順による。
(1) 代入文を走査して、英字・数字・代入演算子・算術演算子以外の文字が含まれていれば、errに−1を格納して手順(5)へ進む。errは、文法上の誤りがあった場合のエラーコードを格納する変数である。
(2) n文字からなる代入文を、文字型配列Sの要素番号1～nに格納し、S[0]に開始マーク“«”を、S[n+1]に終端マーク“»”を、それぞれ格納する。次に、整数型配列Vを用意し、S[i]の内容に対応した表1のコードをV[i]に格納する。その例を、次に示す。
(3) 初期値としてstに“開始”を、err及びiに0を、それぞれ格納する。stは、解析の状態を格納している変数である。
(4) iに1を加算する。表2で、現在のstの状態（行）と着目している文字S[i]の内容（列）が交差するセルの内容を実行する。ただし、セルが空白の場合は、何も実行しない。実行の結果、errの値が0以外となったら手順(5)へ、stの値が“終端”となったら手順(6)へそれぞれ進む。それ以外の場合は、この手順(4)を繰り返す。
(5) errの値に応じて適切なエラーメッセージを表示し、処理を終了する。
(6) 文法上の誤りがなかった旨を表示し、処理を終了する。
設問1：
問題文を見る〔代入文の構文解析〕に関する次の記述中のに入れる正しい答えを、解答群の中から選べ。
文法上の誤りがある次の代入文①〜④を、解析処理の手順によって解析した。
代入文① Answer=One+Two+Three+
代入文② HexaSum=7FFF+0001
代入文③ Position=Index++
代入文④ X1+10*X2=Ans
解析処理の手順(5)に進んだとき、aの場合はerrの値が51に、bの場合はerrの値が64になっている。
解答群
ア：代入文①
イ：代入文②
ウ：代入文③
エ：代入文④
模範解答
a：イ、b：ウ
解説
解答の導き方
この問題では、代入文を1文字ずつ調べ、文字の並びが文法に合っているかを確認します。この確認を構文解析といいます。
表2では、現在の状態と着目している文字の種類によって、次の状態に進むか、エラーコードを記録します。たとえば「演算」の状態は、算術演算子を読み取った直後です。このあとには、演算する項が必要です。
まず、代入文①〜④に使われている文字は、英字・数字・代入演算子・算術演算子のいずれかです。そのため、手順(1)の「それ以外の文字」によるエラーにはなりません。手順(5)に進む場合は、表2でどのエラーコードが設定されるかを調べます。
a：errの値が51になる代入文
代入文②は「HexaSum=7FFF+0001」です。
- 「HexaSum」は英字から始まるため、左辺として読み進められます。
- 「=」で状態が「代入」になります。
- 「7」を読むと、右辺の項を読み始めた状態は「定数」になります。
- その直後の「F」は英字です。表2では、「定数」の状態で英字に出会うと、errに51を格納します。
この問題で定数として使えるのは、数字（“0”〜“9”）の列です。「7FFF」の「F」は数字ではないため、errが51になります。したがって、aは代入文②です。
b：errの値が64になる代入文
代入文③は「Position=Index++」です。
- 「Position」は左辺として読み進められ、「=」で状態が「代入」になります。
- 「Index」を読むと、右辺の変数を読み取っている状態になります。
- 最初の「+」で状態が「演算」になります。
- 続く2個目の「+」も算術演算子です。表2では、「演算」の状態で算術演算子に出会うと、errに64を格納します。
最初の「+」を読んだ後には、次の項が必要です。ところが、項ではなく「+」が続くため、errが64になります。したがって、bは代入文③です。
ほかの代入文も確認すると、誤りの種類を区別できます。
- 代入文①は、最後の「+」の後に項がありません。「演算」の状態で終端マークを読むため、errは65になります。
- 代入文④は、左辺「X1」の後に「+」があります。「左辺」の状態で算術演算子を読むため、errは24になります。
誤りやすいポイント
- 「HexaSum」という名前に引きずられて、右辺の「7FFF」も正しい数値だと考えないようにします。この問題で定数に使えるのは数字だけです。
- 「Index++」では、最初の「+」と2個目の「+」を分けて追います。1個目で状態が「演算」に変わり、2個目でerrが64になります。
- エラーコードは、代入文全体を見た印象ではなく、表2の「現在の状態」と「着目中の文字」の組合せで決まります。
FAQ
Q: 「7FFF」の「F」を、変数の始まりとして読むことはできませんか？
A: できません。「7」を読んだ時点で状態は「定数」です。その状態で英字の「F」に出会うと、表2に従ってerrが51になります。
A: できません。「7」を読んだ時点で状態は「定数」です。その状態で英字の「F」に出会うと、表2に従ってerrが51になります。
Q: 代入文③は、最後まで読んでからerrが64になるのですか？
A: いいえ。2個目の「+」を読んだ時点でerrが64になります。エラーが設定されたら、手順(5)に進みます。
A: いいえ。2個目の「+」を読んだ時点でerrが64になります。エラーが設定されたら、手順(5)に進みます。
Q: errが65になるのは、どのような場合ですか？
A: 代入文①のように、算術演算子の後に項がないまま終端マークに達した場合です。「演算」の状態で終端マークを読むとerrが65になります。
A: 代入文①のように、算術演算子の後に項がないまま終端マークに達した場合です。「演算」の状態で終端マークを読むとerrが65になります。
関連キーワード: 構文解析、状態遷移表、文法エラー、演算子、定数
設問2：
問題文を見る〔代入文の変換〕に関する次のプログラム中及び記述中のに入れる正しい答えを、解答群の中から選べ。
なお、プログラム中の関数Getpos(配列, 値)は、値が格納されている配列中の最初の要素番号を返す。また、配列S, Vは大域変数として与えられ、副プログラム中から参照できるものとする。
〔代入文の変換〕
変換処理は、次の手順による。〔代入文の構文解析〕の手順は実行済みで、代入文には文法上の誤りがないものとする。
(1) 初期値として、wに0を格納する。
(2) 配列S, Vの開始マークから終端マークまでの範囲を検査し、優先順位が最も高い最初の算術演算子の要素番号を変数nextに格納する。その例を、次に示す。算術演算子がなければ、nextに0を格納する。
配列S |«|A|n|s|=|X|1|+|1|0|*|X|2|»|
↑next ← 10
(3) nextが0なら、配列S中の代入文を出力して、処理を終了する。
(4) nextの位置の演算子とその前後の項からなる文字列を抜き出す（図1の①）。wに1を加算し、出力する代入文を編集して出力する。出力する代入文は、文字列“wk#”、文字列に変換した値w、文字“=”及び抜き出した文字列をこの順に連結したものである。次に、配列Sについて、抜き出した元の文字列を、文字列“wk#”及び文字列に変換した値wで置き換える（図1の②）。置き換えるときに、文字数が増える場合は以降の文字を後ろにずらし、減る場合は以降の文字を前に詰める。さらに、更新された配列Sの内容に応じて配列Vの内容を更新する。文字“#”に対応するコードは、英字のコードと同じとする。
(5) 手順(2)へ戻り、処理を繰り返す。
(1) 手順(2)の処理を行う2種類の副プログラム1, 2を作成した。
プログラム1のαの行では、iに1を格納している。
ここで、αの行を“i ← e”とすれば、繰返し処理の繰返し回数を最小にすることができる。
(2) 手順(4)の処理中で使用する副プログラム3を作成した。このプログラムは、配列S, Vの要素番号from以降（終端マークまで）の要素を前後に移動する。moveは、移動する桁数と方向を示し、符号が正の場合は後ろにずらし、符号が負の場合は前に詰める。moveの値が−3（左に3桁詰める）の場合の例を、次に示す。ここで、配列S, Vは十分な大きさがあるものとする。
c, dに関する解答群
ア：priority < V[i]
イ：priority ≦ V[i]
ウ：priority ≧ V[i]
エ：priority > V[i]
eに関する解答群
ア：Getpos(S[], "«") + 1
イ：Getpos(S[], "«") + 2
ウ：Getpos(S[], "=") − 1
エ：Getpos(S[], "=") + 2
f, gに関する解答群
ア：from, i < to, 1
イ：from, i ≦ to, 1
ウ：to, i ≧ from, −1
エ：to, i > from, −1
模範解答
c：ア、d：イ、e：エ、f：ウ、g：イ
解説
解答の導き方
この設問では、式から次に計算する演算子を選ぶ方法と、配列の要素を移動する順序を考えます。
表1では、加減算のコードが 、乗除算のコードが です。本文には「乗除算は加減算に優先する」とあります。つまり、このコードでは値が大きい演算子ほど優先順位が高くなっています。また、「同一優先順位の算術演算子は、左から順に演算する」ため、同じ優先順位なら左端の演算子を選びます。
c：プログラム1の比較
プログラム1は、配列を左から右へ調べます。最初にpriorityに を格納します。演算子を見つけたとき、より優先順位の高い演算子があれば選び直す必要があります。
たとえば、加減算のコード を見た後に乗除算のコード を見つけた場合、乗除算を選ぶ必要があります。一方、すでに選んだ演算子と同じコードを見つけても、左から調べているので、最初に見つけた左端の演算子を残します。
そのため、現在のpriorityよりV[i] が大きいときだけ選択を更新します。条件は なので、cはアです。
d：プログラム2の比較
プログラム2は、配列を右から左へ調べます。最初にpriorityに を格納します。乗除算のコード を見つけたら、加減算より優先順位が高いため、選択を更新します。
同じ優先順位の演算子が複数ある場合も、左端の演算子を選ぶ必要があります。右から左へ調べているので、同じコードを見つけるたびに選択を更新すると、最後に選ばれるのは左端です。したがって、同じコードの場合にも更新する条件が必要です。
条件は なので、dはイです。
e：プログラム1の開始位置
演算子を探すのは、右辺の中です。右辺の最初の文字は項の一部なので、演算子ではありません。したがって、右辺の先頭文字の次から探せば、演算子を探すために必要な範囲を調べられます。
「=」の位置から2つ後ろがその位置です。選択肢では に当たるので、eはエです。
f、g：配列を移動する向き
要素を移動するときは、まだ移動していない元の値を上書きしない順序で処理します。
- のときは、要素を後ろへずらします。後ろ側の要素から先に移動すれば、まだ移動していない値を保てます。そこで、toから始め、iがfrom以上の間、iを ずつ減らして処理します。fはウです。
- のときは、要素を前へ詰めます。前側の要素から先に移動すれば、まだ使っていない後ろ側の値を上書きしません。そこで、fromから始め、iがto以下の間、iを ずつ増やして処理します。gはイです。
誤りやすいポイント
-
コードの値と優先順位を反対に考えること
表1では、乗除算のコード が加減算のコード より大きく、乗除算のほうが優先順位も高くなります。 -
プログラム1とプログラム2で、同じ比較条件を使うこと
プログラム1は左から調べるので、同じ優先順位なら選択を更新しないようにします。プログラム2は右から調べるので、同じ優先順位でも選択を更新し、左端の演算子を残します。 -
配列を移動する方向と、処理する順番を逆にすること
後ろへずらすときは右側から、前へ詰めるときは左側から処理します。逆向きに処理すると、移動前の値を先に上書きしてしまうことがあります。 -
移動範囲の端を処理から外すこと
fromやtoは移動する範囲に含まれます。そのため、繰返し条件には範囲の端を含める必要があります。
FAQ
Q: なぜ演算子を1つ処理するたびに、次の演算子を探し直すのですか？
A: 演算した部分を作業変数wk# で置き換えると、式の形が変わるためです。置き換え後の式を改めて調べ、次に計算する演算子を選びます。
A: 演算した部分を作業変数wk# で置き換えると、式の形が変わるためです。置き換え後の式を改めて調べ、次に計算する演算子を選びます。
Q: 同じ優先順位の演算子は、なぜ左端から選ぶのですか？
A: 問題文で、同一優先順位の算術演算子は左から順に演算すると定められているためです。プログラム1とプログラム2は、調べる向きが違っても、この規則どおり左端の演算子を選ぶように作られています。
A: 問題文で、同一優先順位の算術演算子は左から順に演算すると定められているためです。プログラム1とプログラム2は、調べる向きが違っても、この規則どおり左端の演算子を選ぶように作られています。
Q: 配列の要素を移動するとき、なぜ処理順序を変えるのですか？
A: 配列の中で要素を移すとき、移動先の値が移動前の値を上書きする場合があります。後ろへずらすときは右側から、前へ詰めるときは左側から処理すると、まだ使っていない値を保てます。
A: 配列の中で要素を移すとき、移動先の値が移動前の値を上書きする場合があります。後ろへずらすときは右側から、前へ詰めるときは左側から処理すると、まだ使っていない値を保てます。
関連キーワード: 演算子の優先順位、配列走査、文字列置換、状態遷移、繰返し処理
