基本情報技術者 2014年 春期 午後 問12
次のアセンブラプログラムの説明及びプログラムを読んで、設問1〜3に答えよ。
〔プログラム1の説明〕
文字列中の単語を切り出して、単語管理テーブルを作成する副プログラムGETTKNである。
(1) 文字列は英字、数字、空白文字の0文字以上の並びで、最後にピリオドが置かれる。単語は、1文字以上の空白文字又はピリオドで区切られた英数字の並びである。英字には、アルファベットの他に、ピリオド以外の記号を含むものとする。文字列表記中の“△”は空白文字を示す。
(2) 単語管理テーブルには、文字列中に現れる単語ごとに、3語から成る要素を作成し、単語の先頭アドレス、単語の長さ、単語の種別の順に格納する。種別は、単語が数字だけから成るときは0、英字を含むときは1とする。単語の切出しが終了したとき、単語管理テーブルの終端を示すマークとして−1を格納する。
(3) 主プログラムは、文字列の先頭アドレスをGR1に、単語管理テーブルの先頭アドレスをGR2に設定して、GETTKNを呼ぶ。
(4) 副プログラムGETTKNから戻るとき、汎用レジスタGR1〜GR7の内容は元に戻す。
副プログラムGETTKNの実行例を、図1に示す。
設問1：
問題文を見る プログラム1中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：JUMP ACHK
イ：JUMP LP
ウ：LAD GR1,-1,GR1
エ：LAD GR1,1,GR1
オ：LD GR4,0,GR1
カ：LD GR4,1,GR1
bに関する解答群
ア：ADDL GR5,GR6
イ：LAD GR3,1,GR3
ウ：SLL GR3,1
エ：SLL GR5,1
オ：SRL GR5,1
カ：SUBL GR5,GR6
模範解答
a：イ、b：カ
解説
解答の導き方
この問題では、空欄aとbに入る命令を考えます。文字列を読む位置と、単語の情報を記録する処理に注目します。
まず、GR1は文字列中の現在位置を示すアドレス（文字列の場所を表す番号）を持っています。GR2は単語管理テーブルの書込み位置を示します。GR3〜GR6などの汎用レジスタ（処理中の値や場所を一時的に置く場所）は、単語の種別や長さなどを扱います。
aに入る命令
文字を読む部分では、LPに来るたびにGR1を1増やしてから、その位置の文字をGR4に読み込みます。つまり、LPは「次の文字へ進んでから調べる」処理です。
空白文字が見つかると、GETTKNはSETTKNを呼び出して、直前の単語をテーブルに記録します。その後は、空白文字の次の文字を調べる必要があります。GR1は空白文字の位置を指しているので、LPに戻れば、GR1が1増えて次の文字に進みます。
したがって、aにはLPへ戻る命令が入ります。選択肢では JUMP LP です。ここでGR1を別に増やすと、LPでもう一度増えるため、文字を読み飛ばしてしまいます。
bに入る命令
SETTKNでは、まずGR1の値をGR5に移しています。単語を見つけた時点のGR1は、その単語の直後にある空白文字、または区切りのピリオドの位置を指しています。一方、GR6は単語の先頭アドレスです。
問題文には、テーブルに「単語の先頭アドレス、単語の長さ、単語の種別の順に格納する」とあります。単語の長さは、区切り文字の位置から単語の先頭位置を引けば求められます。そのため、GR5からGR6を引く命令が必要です。
実際に図1の実行例で考えると、最初の単語は102番地から始まり、直後の空白文字は106番地にあります。長さは です。したがって、bには SUBL GR5,GR6 が入ります。この命令によって、GR5に単語の長さが残ります。
誤りやすいポイント
- 空白文字を見つけた後に、GR1を増やす命令を入れたくなります。しかし、LPの先頭ですでにGR1を1増やすため、別に増やすと文字を1文字飛ばしてしまいます。
- GR1とGR6の引き算の向きを逆にしないようにします。GR1は単語の終わり側、GR6は単語の先頭側なので、長さは「終わり側の位置 − 先頭側の位置」です。
- GR3は単語の種別だけでなく、単語を処理中かどうかも表します。初期値の−1は「単語を処理していない」状態です。単語の処理を始めると0になり、数字以外の文字が現れると1になります。
FAQ
Q: なぜ空白文字の位置を単語の終わりとして使えるのですか？
A: GR1は空白文字の位置を指していますが、単語の最後の文字はその1つ前です。単語の先頭から空白文字の位置までの番地の差を取ると、単語の文字数になります。
A: GR1は空白文字の位置を指していますが、単語の最後の文字はその1つ前です。単語の先頭から空白文字の位置までの番地の差を取ると、単語の文字数になります。
Q: 数字だけの単語と、英字を含む単語はどこで区別していますか？
A: ACHKで、読み取った文字が「0」から「9」の範囲にあるかを調べます。その範囲外なら、NEXTでGR3を1にして「英字を含む」種別にします。問題文では、英字にアルファベット以外の記号も含まれます。
A: ACHKで、読み取った文字が「0」から「9」の範囲にあるかを調べます。その範囲外なら、NEXTでGR3を1にして「英字を含む」種別にします。問題文では、英字にアルファベット以外の記号も含まれます。
Q: 単語の後に空白がなく、ピリオドで終わる場合はどうなりますか？
A: ピリオドを見つけるとFINに進み、SETTKNを呼び出して最後の単語を記録します。その後、単語管理テーブルに終端マークの−1を格納します。
A: ピリオドを見つけるとFINに進み、SETTKNを呼び出して最後の単語を記録します。その後、単語管理テーブルに終端マークの−1を格納します。
関連キーワード: アセンブリ言語、レジスタ、アドレス、条件分岐、文字列処理
設問2：
問題文を見る 次の文字列が与えられ、プログラム1のラベルNEXTが付いた命令を2度目に実行した直後にGR4に設定されている文字として、正しい答えを、解答群の中から選べ。
解答群
ア：1
イ：2
ウ：3
エ：A
オ：B
カ：C
模範解答
カ
解説
解答の導き方
問われているのは、ラベルNEXTの命令を2度目に実行したとき、GR4に入っている文字です。GR4は、このループで読み取った1文字を一時的に保持するレジスタ（処理中の値を置く場所）です。
まず、GR3の値が何を表すかを確認します。プログラムでは、GR3が−1のときは単語を処理しておらず、0のときは数字だけの単語を処理中、1のときは数字以外の文字を含む単語を処理中です。
文字列「△ 1 A 2 B △ C 3 .」を先頭から追います。
NEXTに進んだとき、GR4にはループで読み取った文字が入っています。2度目にNEXTへ進む直前に読み取った文字はCです。また、NEXTの命令はGR3を変更しますが、GR4は変更しません。したがって、2度目にNEXTの命令を実行した直後も、GR4にはCが設定されています。
誤りやすいポイント
- 文字列に含まれる数字を順番に数えて、2番目の数字「2」を答えにしないようにします。NEXTに進む回数は、数字の出現回数とは異なります。
- 最初のNEXTはAで実行されますが、その後GR3が1になります。GR3が1の間はJPL LPで次の文字へ進むため、後続の2やBではNEXTに進みません。
- 空白の後に新しい単語を処理するとき、GR3は−1から0に戻ります。そのため、Cでは再び数字かどうかを判定し、2度目のNEXTに進みます。
- NEXTは数字以外の文字を含む単語の種別を設定する命令です。NEXTに進んだ文字が、そのままGR4に残る点も確認します。
FAQ
Q: Aの後にある2では、なぜNEXTに進まないのですか？
A: Aを処理した時点でGR3が1になります。その後はJPL LPで次の文字へ進むため、2の数字判定は行わず、NEXTにも進みません。
A: Aを処理した時点でGR3が1になります。その後はJPL LPで次の文字へ進むため、2の数字判定は行わず、NEXTにも進みません。
Q: Cの後にある3で、NEXTがもう一度実行されるのではありませんか？
A: CでNEXTを実行するとGR3が1になります。その後の3では、JPL LPによって次の文字へ進むため、NEXTは実行されません。
A: CでNEXTを実行するとGR3が1になります。その後の3では、JPL LPによって次の文字へ進むため、NEXTは実行されません。
Q: NEXTの命令を実行すると、GR4の文字も変わりますか？
A: 変わりません。GR4に文字を読み込むのはループ中のLD GR4,0,GR1で、NEXTの命令はGR3を変更します。
A: 変わりません。GR4に文字を読み込むのはループ中のLD GR4,0,GR1で、NEXTの命令はGR3を変更します。
関連キーワード: アセンブリ言語、レジスタ、条件分岐、ループ処理、文字列走査
設問3：
問題文を見る GETTKNを使用して、指示に従い2数の和、差、積のいずれかを求める副プログラムCALCを作成した。プログラム2中のに入れる正しい答えを、解答群の中から選べ。
(1) 主プログラムは、文字列の先頭アドレスをGR1に設定して、CALCを呼ぶ。CALCは演算結果をGR0に設定して呼出し元に戻る。文字列の形式を図2に示す。
(2) 数字文字列は0〜65535の整数（符号なしの数字文字列）で1文字以上の文字列とし、演算子は加算（+）、減算（−）、乗算（*）を表す記号1文字とする。演算はそれぞれ論理加算、論理減算、整数の乗算として実行し、桁あふれは発生しないものとする。
(3) CALCは、GETTKNで切り出した数字だけから成る単語を2進数に変換するために、別に用意された副プログラムDTOBを呼ぶ。
(4) DTOBは、数字文字列格納領域の先頭アドレスと文字列の長さが順に格納された2語から成る領域の先頭アドレスがGR1に設定されて、呼び出される。DTOBは数字文字列を2進数に変換し、GR0に設定して呼出し元に戻る。
(5) 副プログラムCALC、DTOBから戻るとき、汎用レジスタGR1〜GR7の内容は元に戻す。
cに関する解答群
ア：LAD GR1,3,GR2
イ：LD GR1,0,GR2
ウ：LD GR1,CTBL
エ：LD GR1,GR2
オ：LD GR2,CTBL
カ：LD GR2,GR1
dに関する解答群
ア：LAD GR3,LTBL
イ：LAD GR3,LTBL,GR3
ウ：LD GR3,LTBL
エ：LD GR3,LTBL,GR3
オ：SLL GR3,1
eに関する解答群
ア：ADDL GR0,GR5
イ：ADDL GR5,GR4
ウ：LD GR5,GR4
エ：SLL GR5,1
オ：SRL GR5,1
模範解答
c：エ、d：エ、e：オ
解説
解答の導き方
空欄には、順に「DTOBへ渡す引数の指定」「演算子に応じた分岐先の取得」「乗算で乗数を処理する命令」が入ります。まず、使われる値がどこにあるかを確認します。
c：DTOBに数字文字列１の情報を渡します
GETTKNは、単語ごとに「先頭アドレス、単語の長さ、単語の種別」の順でテーブルに格納します。したがって、最初の数字文字列のアドレスと長さは、CTBLの先頭から2語の範囲にあります。
一方、DTOBに渡すのは数字文字列そのものではなく、アドレスと文字数が格納された領域の先頭アドレスです。CALCでは「LAD GR2,CTBL」でGR2にCTBLの先頭アドレスを設定しています。また、GETTKNは汎用レジスタの内容を元に戻すため、GETTKNの後もGR2はCTBLの先頭アドレスを指しています。
そのため、GR1にGR2の値をコピーする「LD GR1,GR2」が必要です。これは選択肢のエです。「LD GR1,0,GR2」では、CTBLに格納された単語の先頭アドレスを読み込んでしまい、DTOBが必要とする「アドレスと文字数を格納した領域の先頭アドレス」にはなりません。
d：演算子に対応する処理へ分岐します
GR3には、演算子の文字コードが入っています。その後の「SUBL GR3,=''」で「」の文字コードを引くため、演算子ごとに次の値になります。
- 「*」なら0
- 「+」なら1
- 「-」なら3
LTBLには、先頭から「MULT」「PLUS」「ダミー」「MINUS」の順に分岐先が格納されています。この並びに対応する値を使って、LTBLから分岐先のアドレスを読み込む必要があります。
「LD GR3,LTBL,GR3」は、LTBLにGR3の値を加えた場所から分岐先アドレスを読み込みます。読み込んだアドレスを使って「JUMP 0,GR3」で処理へ移るため、dは選択肢のエです。
「LAD GR3,LTBL,GR3」だと分岐先アドレスではなく、LTBL内の場所のアドレスをGR3に設定します。また、「LD GR3,LTBL」では、演算子にかかわらず先頭の「MULT」のアドレスを読み込んでしまいます。
e：乗数のビットを右から順に調べます
乗算では、GR4を被乗数、GR5を乗数として、GR0に積をためていきます。ループでは、まずGR5の最下位ビットを調べます。ビットが1ならGR4をGR0に加え、続けてGR4を左に論理シフトします。
次のループでGR5の次のビットを調べるには、処理済みの最下位ビットを取り除き、残りのビットを右にずらす必要があります。したがって、GR5を右に論理シフトする「SRL GR5,1」が入ります。これは選択肢のオです。
たとえば、GR5が5（2進数で0101）なら、右にずらしていくことで、最下位ビットを1、0、1の順に調べられます。それぞれのビットが1のときだけGR4を加えるため、結果はGR4の5倍になります。
誤りやすいポイント
- DTOBに渡すのは数字文字列の先頭アドレスではなく、アドレスと文字数が格納された領域の先頭アドレスです。
- GR2にはGETTKNを呼び出す前に設定したCTBLの先頭アドレスが残ります。GETTKNが汎用レジスタの内容を元に戻すためです。
- dでは、演算子から計算した値を使って、LTBLに格納された分岐先アドレスを読み込みます。表の中の場所のアドレスを計算するだけでは足りません。
- 乗算のループでは、GR4は左に、GR5は右にシフトします。GR4は加える値を次の桁に合わせ、GR5は次に調べるビットを最下位に移すためです。
FAQ
Q: なぜ最初のDTOB呼出しでGR1にGR2を設定するのですか？
A: GR2がCTBLの先頭アドレスを持っており、DTOBには数字文字列のアドレスと文字数を格納した領域の先頭アドレスを渡すためです。
A: GR2がCTBLの先頭アドレスを持っており、DTOBには数字文字列のアドレスと文字数を格納した領域の先頭アドレスを渡すためです。
Q: 「」「+」「-」から0、1、3を作るのはなぜですか？
A: LTBLの分岐先が「MULT」「PLUS」「ダミー」「MINUS」の順に並んでいるためです。演算子の文字コードから「」の文字コードを引くと、その表の位置に対応する値になります。
A: LTBLの分岐先が「MULT」「PLUS」「ダミー」「MINUS」の順に並んでいるためです。演算子の文字コードから「」の文字コードを引くと、その表の位置に対応する値になります。
Q: 乗算の途中でGR5が0になったら、なぜ終了できるのですか？
A: GR5のビットを右から順に調べているため、0になった時点で調べるビットがなくなっています。積に加える値がもうないので、ループを終了できます。
A: GR5のビットを右から順に調べているため、0になった時点で調べるビットがなくなっています。積に加える値がもうないので、ループを終了できます。
関連キーワード: アドレス指定、分岐テーブル、文字コード、論理シフト、反復加算法
