[平成２８年度秋] 午後 問2 解説

[問題文・解答]

平成２８年度１０月に実施された基本情報技術者試験の午後試験の問題・解答はIPA公式ページからダウンロード出来ます。（以下リンク）

[H28秋 午後 問題文]　　　[H28秋 午後 解答]

[問題概要]

この問題は、選択問題で問2〜問7のうち4問を選択する必要があります。

問題の題材は、コンパイラの字句解析と構文解析です。
符号なし浮動小数点定数の字句解析や演算式の構文解析について問われます。専門知識が無くても解答は可能ですが、状態遷移図や構文木の知識が欲しい問題です。

[設問1]

構文規則から状態遷移図を導出する問題です。問題に記載されている符号なし浮動小数点定数の構文規則は以下の6つです。
①符号なし浮動小数点定数　→　小数点定数 [指数部]　|　数字列 指数部
②小数点定数　→　[数字列].数字列　|　数字列.
③指数部　→　e [符号] 数字列
④数字列　→　数字　|　数字列 数字
⑤符号　→　+　|　-
⑥数字　→　0|1|2|3|4|5|6|7|8|9
上記の構文規則より、最終的な文字列に現れる記号は、数字(0-9）、符号(+,-）、e、.(ドット)の４種類となります。
④より、数字列は数字が１つ以上続く文字列を示します。
③より、指数部は頭にeが１文字の後、符号を挟んで数字列で終わる文字列を示します。ただし、符号は省略可です。
②より小数点定数は「数字列.」で始まるか「.数字列」となります。

a) 規則①②より、符号なし浮動小数点定数の最初の文字は「.」もしくは数字であるため、a)には「.」が当てはまります。

b) 状態0→状態1は数字列を表します。よって、状態0→1→3で受理されるのは「数字列.」もしくは「数字列.数字列」であり、規則①よりこれらは小数点定数の一部を示します。規則①より、小数点定数の後に指数部が続く場合も受理されるため、状態3→4→5→6では指数部を表しています。ここで、①より数字列の後にすぐに指数部が続く場合も受理されるため、状態1から「e」を経て状態4→5→6と遷移する場合も受理されます。従って、b)には「e」が当てはまります。

[答] a) ア　b) イ

[設問2]

式の構文規則と構文木解析に関する問題です。

c) P.11中段に「演算子op1の優先順位は、演算子op2の優先順位よりも高い」とあることから、四則演算で言うとop1が×や÷、op2が＋や−に相当します。
例1の「v op2 w op1 x」を「v ＋ w × x」と考えて評価する場合、まず「v」と「w × x」に分けて考えるのが普通です。つまり、「op2」を境に「v」と「w op1 x」に分ける事になります。これは、式の構文規則の１つ目の規則に相当します。従って、式は項または、式 op2 項で定義され「ウ」が適切となります。ここで、「イ」や「エ」の場合は、op2の後ろの部分が必ず記号単体となってしまい、例1のようにop2の後ろにop1を含む式を表現できなくなるため、不適切です。

d) 式の構文規則に更に括弧を含む場合についてです。P.11下段に「括弧を含む式では、演算の優先順位は、括弧内の演算の方が高い」とあり、例2のように括弧内にはop2を含む式が入る事からd)には式が当てはまります。

e) 構文木では、優先順位の高い演算が深い部分に、優先順位の低い演算は根に近い部分にきます。例2中では括弧内の演算「x op2 y」が最優先であり、次いで1つ目のop1、２つ目のop1、op2の順序となります。2つのop1の優先順位はP.11上段の演算順序の説明に沿ったものです。
以上より、下から括弧内のop2、１つ目のop1、２つ目のop1、最初のop2と上がっていく構文木となっている「ウ」が正解です。

[答] c) ウ　d) ウ　e) ウ

上記の解説は問題と解答を元に自分なりの考え方を記述しており、間違っている部分もあるかと思いますので、ご了承願います。また、誤りについては正しい考え方をご指摘・ご教授頂けると助かります。