基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

コンパイラの字句解析と構文解析に関する次の記述を読んで，設問1～2に答えよ。

　コンパイラの字句解析では，原始プログラムを文字列として読み込んで，文字列中の文字の並びが字句として認識できるかどうかを解析し，その結果を字句の並びとして出力する。字句とは，原始プログラム中の名前や定数など，構文規則で規定されている文字の並びの最小単位である。構文解析では，字句解析が出力した字句を読み込みながら，字句の並びが構文規則で規定されている文法に合っているかどうかを解析し，その結果を構文木などの中間表現で出力する。

字句解析の処理について，次の記述中の　に入れる正しい答えを，解答群の中から選べ。

　123. や 123.4e－1 など，構文規則で規定されている符号なし浮動小数点定数を例として字句解析の処理を考える。

• "→"は，左側の構文要素が右側で定義されることを示す。
• "|"は，"又は"を意味する。
• "["と"]"で囲まれた部分は，省略可能を意味する。

　構文規則は，状態遷移図で表現することもできる。符号なし浮動小数点定数の構文規則に対する状態遷移図を，図1に示す。字句解析では，文字の並び中の文字を読み込みながら初期状態から状態を遷移させて，文字の並びを読み終えたときの状態が最終状態ならば，その文字の並びは符号なし浮動小数点定数であると判定する。ここで，円の中の数字は状態番号を示す。初期状態の状態番号は 0 であり，最終状態は二重円で示している。また，文字の並びは左から右に向けて1文字ずつ処理される。

構文解析の処理について，次の記述中の　に入れる正しい答えを，解答群の中から選べ。

　構文規則で規定されている式を例として，構文解析の処理を考える。式の構文解析では，式を構成する演算子や名前などの字句を，式の左から右に読み込みながら，字句の並びが構文規則で規定されている文法に合っているかどうかを解析し，その結果を構文木として出力する。例えば，2項演算子 op，名前 v，w，x を構成要素とする式 v op w op x は，次の演算順序①，②になるように解釈され，その結果は，図2に示す2分木で表現する構文木として出力される。図2の構文木では，深さ優先でたどりながら，帰り掛けに節の演算子を評価する。

〔演算順序〕

1. v と w に対して演算 op を施す。
2. ①の結果と x に対して演算 op を施す。

　式の構文規則では，式の構文を規定するだけではなく，演算子の優先順位も規定する。2項演算子 op1 と op2，名前 v，w，x，y，z を構成要素とする式の構文規則を定義する。ここで，"演算子 op1 の優先順位は，演算子 op2 の優先順位よりも高い"とする。これを規定する場合，式の構文規則は次のとおりになる。この構文規則で受理される式の例を，例1に示す。

〔式の構文規則〕
　式　 → 項　｜c
　項　 → 因子｜項 op1 因子
　因子 → 名前
　名前 → v｜w｜x｜y｜z

　　例1：v op2 w op1 x

　さらに，式の構文に括弧を追加し，"括弧を含む式では，演算の優先順位は，括弧内の演算の方が高い"とする。これを規定する場合，因子の構文規則は次のとおりになる。この構文規則で受理される式の例を，例2に示す。

〔因子の構文規則〕
　因子 → 名前｜(d)

　　例2：v op2 w op1 (x op2 y) op1 z

　例2で示す式を解析したとき，出力される構文木はeとなる。