平成28年 秋期 基本情報技術者 午後 問02
問02 4問選択コンパイラの字句解析と構文解析に関する次の記述を読んで,設問1,2に答えよ。 コンパイラの字句解析では,原始プログラムを文字列として読み込んで, 文字列中の文字の並びが字句として認識できるかどうかを解析し, その結果を字句の並びとして出力する。字句とは,原始プログラム中の名前や定数など, 構文規則で規定されている文字の並びの最小単位である。 構文解析では,字句解析が出力した字句を読み込みながら, 字句の並びが構文規則で規定されている文法に合っているかどうかを解析し, その結果を構文木などの中間表現で出力する。
123 や 123.4e−1 など,構文規則で規定されている符号なし浮動小数点定数を 例として字句解析の処理を考える。 “|”は,“又は”を意味する。 “[”と “]”で囲まれた部分は,省略可能を意味する。 〔符号なし浮動小数点定数の構文規則〕
構文規則は,状態遷移図で表現することもできる。符号なし浮動小数点定数の 構文規則に対する状態遷移図を,図1に示す。字句解析では,文字の並び中の文字を 読み込みながら初期状態から状態を遷移させて,文字の並びを読み終えたときの状態が 最終状態ならば,その文字の並びは符号なし浮動小数点定数であると判定する。 ここで,円の中の数字は状態番号を示す。初期状態の状態番号は 0 であり, 最終状態は二重円で示している。また,文字の並びは左から右に向けて 1 文字ずつ処理される。
図1 符号なし浮動小数点定数の構文規則に対する状態遷移図 a,b に関する解答群 エ 数字 オ 符号
構文規則で規定されている式を例として,構文解析の処理を考える。式の構文解析では, 式を構成する演算子や名前などの字句を,式の左から右に読み込みながら, 字句の並びが構文規則で規定されている文法に合っているかどうかを解析し, その結果を構文木として出力する。 例えば,2項演算子 op,名前 v,w,x を構成要素とする式 v op w op x は, 次の演算順序@,Aになるように解釈され,その結果は, 図2に示す2分木で表現する構文木として出力される。図2の構文木では, 深さ優先でたどりながら,帰り掛けに節の演算子を評価する。 〔演算順序〕 @ v と w に対して演算 op を施す。 A @の結果と x に対して演算 op を施す。
図2 式の構文木と演算順序の例 式の構文規則では,式の構文を規定するだけではなく,演算子の優先順位も規定する。 2項演算子 op1 と op2,名前 v,w,x,y,z を構成要素とする式の構文規則を定義する。 ここで,“演算子 op1 の優先順位は,演算子 op2 の優先順位よりも高い”とする。 これを規定する場合,式の構文規則は次のとおりになる。 この構文規則で受理される式の例を,例1に示す。 〔式の構文規則則〕
項 → 因子 l 項 op1 因子 因子 → 名前 名前 → v | w | x | y | Z 例1: v op2 w op1 x さらに,式の構文に括弧を追加し,“括弧を合む式では,演算の優先順位は, 括弧内の演算の方が高い”とする。これを規定する場合,因子の構文規則は次の とおりになる。この構文規則で受理される式の例を,例2に示す。 〔因子の構文規則〕 例2 v op w op1 (x op2 y) op1 z c に関する解答群 ウ 式 op2 項 エ 式 op2 名前 d に関する解答群 e に関する解答群 ウ エ
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ] | ||||||||||||||||