コンパイラ（ ’11 年度）・期末テスト問題用紙（ ’11 年 7 月 28 日（ 木）・ 10:30 〜 12:00 ）解答上、その他の注意事項

I. 問題は、問 I〜VI まである。
II. 解答用紙の右上の欄に学籍番号・名前を記入すること。
III. 解答欄を間違えないよう注意すること。
IV. 解答中の文字（ 特に a と d ）がはっきりと区別できるよう注意すること。
V. 持ち込みは不可である。筆記用具・時計・学生証以外のものは、かばんの中などにしまうこと。
VI. テストの配点は 80 点である。合格はレポートの得点を加点して、100 点満点中 60 点以上とする。

1

I. （ Backus-Naur 記法）
次のような BNF で表される文法を考える。

例: yxxyxy に対する解析木

N G

N → N y | N x N | xy | yx
ただし 、N は非終端記号、x, y は終端記号である。
次の各記号列について、N から導出されるものには 、その解析木 (parse tree) を右の例にならって書き、導出されないものには 7 を記せ。
（解析木は一通りとは限らないが、そのうち一つを書けば良い。）(1) xyxyyxy (2) yxxxyyy (3) yxxxyxxy

GG
GG
GG

N

ww
www
ww

N Gyx

N

GG
GG
GG

yxyx

II. （ 正規表現）
以下の文字列について、「 0(0|101)* 」という正規表現に（一部でなく）全体がマッチする文字列には (L) 、「 0(10)*1 」という正規表現に全体がマッチする文字列には (R) 、両方に全体がマッチする文字列には (B) 、ど ちらにもマッチしない文字列には (N) をつけよ。
(1) 01010101(2) 010100101

2(3) 010101(4) 0101010

III. （コンパイラのフェーズ ）コンパイラは、字句（ 単語）を切り分ける字句解析フェーズ、プログラムの構造を木の形に表す構文解析フェーズ、変数の宣言や型のチェックを行なう意味解析（ 静的解析）フェーズ、目的のコード を生成するコード 生成フェーズなどに概念的に分けることができる。
次の (1)〜(3) の C 言語のプログラムにはそれぞれ誤りがある。コンパイラのどのフェーズで誤りが検出されるか？
（あるいはされないか？） もっとも適当なものを下の選択肢 (A)〜(E) から選べ。なお、(1)〜(3) のいずれも単独でコンパイルされ 、標準ライブラリとのみリンクされるものとする。
（つまり、他のファイルに変数や関数が定義されていることはない。）(1) （ for 文のセミコロン ; が一つ多い。）#include <stdio.h>
int main(void) {int i;for (i=0; i<5; i++;) {printf("Hello World!\n");}return 0;}(2) （ 文字列リテラルに *演算子を適用しようとした。）#include <stdio.h>
int main(void) {printf("Hello! World\n" * 3);
return 0;}(3) （コメントの終わりを示す「 */ 」を忘れた。）#include <stdio.h>
int main(void) {printf("Hello! World\n");return 0;}/* 表示する *(1)〜(3) の選択肢
(A) 字句解析フェーズでエラーが検出される。
(B) 構文解析フェーズでエラーが検出される。
(C) 意味（ 静的）解析フェーズでエラーが検出される。
(D) コード 生成フェーズでエラーが検出される。
(E) 実行時にエラーとなるか 、まったくエラーにならない（が作成者の意図と異なる動作をする）。
3

IV. （ 演算子順位法）
次の BNF で表される文法を演算子順位法により構文解析する。
E→

id | E “:” E | E “>” E | E “>>” E | “(” E “)”

ただし 、id はアルファベット 1 文字からなるトークンを表す。
この文法は曖昧なので、優先順位と結合性について次のように決めておく。
「 : 」は右結合、「 > 」は非結合、「 >> 」は左結合であり、「 : 」は「 > 」よりも優先順位が高く、「 > 」 は「 >> 」よりも優先順位が高いものとする。
つまり、下表中の左の欄の式は、右の欄の式として解釈される。
式

解釈a : b : ca > b > ca >> b >> c
a : b > ca > b : ca : b >> ca >> b : ca > b >> ca >> b > c

a : (b : c)
構文エラー(a >> b) >> c
(a : b) > ca > (b : c)(a : b) >> ca >> (b : c)(a > b) >> ca >> (b > c)以下の演算子順位行列の空欄 (1)〜(4) を <·（シフト ）、 >·（ 還元）、 7（エラー） のうちもっとも適切なもので埋めよ。
左\右:>>>

()

id

終始

<·
(1)
<·
<·<·>·>·<·>·(3)<·<·>·>·

<·
(2)>·
(4)
<·>·>·

<·
<·<·
<·<·
7
7

7>·>·>·
>·>·<·<·<·<·<·
77


>·
>·>·
7>·>·

:>>>
()
id

4V. （ 再帰下降構文解析）
次のような BNF で表された文法に対して、再帰的下降構文解析ルーチンを作成する。
→|||
StatementList →|Expr→|
Statement

id “=” Expr “;”
if “(” Expr “)” Statement else Statement
while “(” Expr “)” Statement“{” StatementList “}”εStatement StatementList
num
Expr “,” num

ただし 、Statement, StatementList, Expr は非終端記号、id, if, else, while, num, “=”, “(”, “)”, “;”,“{”, “}”, “,” は終端記号である。開始記号（ start symbol ）は Statement である。

(1) Expr から左再帰を除去せよ。補助的に導入する非終端記号は Expr’ とせよ。
以下の (2)〜(4) は、(1) で Expr から左再帰を除去して得られた BNF について答えよ。

(2) Follow (StatementList) を求めよ。
(3) Follow (Expr’) を求めよ。
(4) 下の構文解析表の StatementList の行を埋めよ。
id=;

if()

else while {Statement →StatementList →Expr →Expr’ →
(4) の解答は次の選択肢から選べ。
（ 構文エラーの場合は (G) を選択し 、空欄のまま残さないこと。）
(A).
(B).
(C).
(D).
(E).
(F).
(G).

id “=” Expr “;”
if “(” Expr “)” Statement else Statement
while “(” Expr “)” Statement“{” StatementList “}”εStatement StatementList
7

ただし 、7 は “構文誤り” を示す。

5}

num,$

VI. （ LR 構文解析）
次のような BNF で与えられる文法は曖昧であるが、優先順位を適当に指定することにより、LR構文解析表を作成することができる。

E →|||

while E do E
id “=” E
E “+” E
id··· I· · · II· · · III· · · IV

ただし 、

• · · · のあとの I, II などは生成規則の番号である。
• E は非終端記号、while, do, id, “=”, “+” は終端記号である。id はアルファベット 1 文字からなるトークンを表す。
• 開始記号（ start symbol ）は（ 当然）E である。
bison の出力する LR 構文解析表は次のようになる。 （ 注: bison に -v オプションを指定する
ことによって、LR 構文解析表をファイルに出力させることができる。）

01

while
shift 1
shift 1

doid
shift 2
shift 2

=reduce IV2

shift 53

shift 845

shift 1891011$E
goto 3
goto 4

reduce IV
shift 7shift 6
shift 7shift 2

goto 9accept67+shift 1
shift 1

shift 2
shift 2
reduce II
reduce III
reduce I

goto 10
goto 11shift 7

reduce II

shift 7

reduce I

ここで、shift S は「シフトして状態 s へ遷移」、 goto s は、「状態 s へ遷移」、 reduce X は、「生成規則 X を使って還元」を表す。
次の入力に対して、↑ の次（ 右）の記号をシフトした直後の（ つまりシフトしたあと、還元がまだ起こっていない時の）スタックの状態はどのようになっているか ?

(1) id+id+id↑(2) while id+id do id=id+id↑

次の選択肢から選べ。
（ 左がスタックの底とする）

6

(1) の選択肢
0E 3+7(A).
0 id 2 + 7 E 10 + 7(C).

(B).
(D).

0 id 2 + 7 id 2 + 7
0 E 3 + 7 E 10 + 7(2) の選択肢
0E 3+7(A).
0 while 1 E 4 do 8 id 2 = 5 E 9 + 7(C).

(B).
(D).

70 while 1 id 2 + 7 id 2 do 8 E 11 + 70 while 1 E 4 do 8 E 11 + 7コンパイラ（ ’11 年度）・期末テスト解答用紙 (’11 年 7 月 28 日)

学籍番号I. （ Backus-Naur 記法）
(1).

氏名

(4×3)
(2).

(3).

II. （ 正規表現）
(1).

(4×4)
(2).

(3).

(4).

III. （コンパイラのフェーズ ）
(1).

(4×3)
(2).

(3).

IV. （ 演算子順位法）(1).
裏ページに続く。

(4×4)
(2).

(3).

(4).

V. （ 再帰下降構文解析）(1).
Expr →(4×4)

Expr’ →{(3). {}}

(2).

id=;

if()

else while {}

num,

$

(4). StatementList →VI. （ LR 構文解析）(1).
テストの感想(4×2)(2).