コンパイラ（2019 年度）
・期末テスト問題用紙（2019 年 08 月 01 日（木）・ 10:30 〜 12:00）

解答上、その他の注意事項

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

1

I. （Backus-Naur 記法）
例: xxx+*に対する解析木

次のような BNF で表される文法を考える。

S→ S S + | S S * | x

ただし、S は非終端記号、“+”, “*”, “x” は終端記号である。次の各記号列について、S から導出されるものには、その解析木 (parse tree) を右の例にならって書き、導出されないものには 7 を記せ。（解析木は一通りとは限らないが、そのうち一つを書けば良い。）

(1)
(3)

(2)
(4)x x + x *x x x x * * +xxxxxxxxxxxxxxx

Sxx
xx
xxx

S FFFFFFFS F*FFFFFFSS

xx+x x * + xx x * x x + +II. （正規表現）
以下の文字列について、「(zw|wz)*(z|ε)」という正規表現に (一部でなく) 全体がマッチする文字列には (L) を、「(zwz|wzw)*(w|ε)」という正規表現に (一部でなく) 全体がマッチする文字列には (R) を、両方に全体がマッチする文字列には (B) を、どちらにも全体がマッチしない文字列には (N) を記せ。

(1)

wzwzwzwzz

(2)

(3)

zwzwzwwzw

zwzwzwwzz(4)

wzwzwzzwz

III. （コンパイラのフェーズ）
コンパイラは、字句（単語）を切り分ける字句解析フェーズ、プログラムの構造を木の形に表す構文解析フェーズ、変数の宣言や型のチェックを行なう意味解析（静的解析）フェーズ、目的のコードを生成するコード生成フェーズなどに概念的に分けることができる。
次の (1)〜(4) の C 言語のプログラムにはそれぞれ誤りがある。コンパイラのどのフェーズで誤りが検出されるか？（あるいはされないか？） もっとも適当なものを下の選択肢 (A)〜(E) から選べ。なお、(1)〜(4) のいずれも単独でコンパイルされ、標準ライブラリとのみリンクされるものとする。（つまり、他のファイルに変数や関数が定義されていることはない。）

2

(1) （文末のセミコロン “;” を忘れた。）#include <stdio.h>
int main(void) {printf("Hello World!\n")return 0}(2) （文字列リテラルに二重引用符 「"」を忘れた。）#include <stdio.h>
int main(void) {printf(Hello);
return 0;}(3) （コメントを閉じるのを忘れた。）#include <stdio.h>
int main(void) { /* 閉じ忘れのコメント
printf("Hello World!\n");return 0;}(4) （括弧の種類を間違えた。）#include <stdio.h>
int main(void} (printf("Hello! World\n");return 0;}(1)〜(4) の選択肢
(A) 字句解析フェーズでエラーが検出される。
(B) 構文解析フェーズでエラーが検出される。
(C) 意味解析フェーズでエラーが検出される。
(D) コード生成フェーズでエラーが検出される。
(E) 実行時にエラーとなるか、全くエラーにならない（が作成者の意図と異なる動作をする）。

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

E→

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

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

解釈

a + b + c (a + b) + c
a : b : c a : (b : c)a > b > c （構文エラー）a $ b $ c a $ (b $ c)a + b : c (a + b) : c
a : b + c a : (b + c)
a + b > c (a + b) > c
a > b + c a > (b + c)

式

解釈a + b $ c
a $ 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) $ c
a $ (b : c)(a > b) $ c
a $ (b > c)以下の演算子順位行列の空欄 (1)〜(8) を <· 、 、 >· 、 7 のうちもっとも適切なもので埋めよ。
ただし 7 はエラーを表すものとする。（教科書などの記法では、エラーは空欄のままとしているが、このテストでは無回答と区別するために明示的に 7 を書くことにする。）
左\右+:>

$()

id

終始

<·
(1)
<·
<·
(7)
<·>·
>·

<·>·
(3)
(5)
<·<·>·>·

<·
(2)
>·
(6)
<·
<·>·
>·

<·>·
(4)
>·
(8)
<·>·
>·

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

<·
<·
<·
<·
<·
<·
77

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

+:>
$()
id

4V. （再帰下降構文解析）
次のような BNF で定義された文法に対して再帰下降構文解析ルーチンを作成する。
S → S “;” S | id “=” E | pr “(” E “)”E → id | E “+” E | “(” S “@” E “)”
ただし、「S 」,「E 」は非終端記号で、「;」, 「id」, 「=」, 「pr」, 「(」, 「)」, 「+」, 「@」は終端記号とする。開始記号（start symbol）は S である。

(1) E から左再帰を除去すると、次のような BNF が得られる。
EE′→|→|

id E ′“(” S “@” E “)” E ′ε“+” E E ′··· I· · · II· · · III· · · IV

ここで、· · · の後のローマ数字（I, II など）は生成規則の番号である。これを参考にして、S から左再帰を除去せよ。補助的に導入する非終端記号は S ′ とせよ。（後の解答で使用するために、生成規則に番号（V, VI, . . . ）を付けておいてもよい。）
以下の (2)〜(4) は、(1) で S と E から左再帰を除去して得られた BNF について答えよ。ただし、入力の終わりは $ で表すことにする。

(2) First (S ′ ) を求めよ。
(3) Follow (S ′ ) を求めよ。
(4) Follow (E ′ ) を求めよ。
(5) 下の予測型構文解析表の E, E ′ の行を埋めよ。この問題の解答は 7, I 〜 IV の中から選べ。
ただし、7 は “エラー” を示す。（教科書などの記法では、エラーは空欄のままとしているが、このテストでは無回答と区別するために明示的に 7 を書くことにする。）(6) 下の予測型構文解析表の S , S ′ の行を埋めよ。
ただし、この問題の解答は、7 と (1) の解答欄中で、BNF の生成規則に自分で付けた番号(V, VI, . . .) から選んでもよい。また、この文法は曖昧なため衝突が起こる可能性がある。
その場合は、一つの欄に 2 つのの生成規則を I + II のように記入せよ。構文エラーの場合は、必ず 7 を記入し、空欄のまま残さないこと。

;

id=pr()+@$S →S′ →E→E′ →(7) この文法に対して、入力が文法にしたがっていれば「正しい構文です。」間違っていれば「構文に誤りがあります。」と表示する構文解析プログラムを作成する。プログラム（次ページ）中の指定の部分に入る S, S1, E, E1 関数のうち、E, E1 関数 の定義を完成させよ。
5ただし、S, S1, E, E1 は、それぞれ非終端記号 S , S ′ , E, E ′ に対応する関数である。予測型
構文解析表の 7 に相当する入力には reportError 関数を呼び出すようにすること。
（プログラムの補足説明: プログラム中では、終端記号は、“;” のような 1 文字のものは、その字そのもの（の ASCII コード）、id などのトークンは、C 言語のマクロ（例えば id の場合は ID）として表現している。入力の終わり（$）に対応するのは、このプログラムの場合、マクロ EOF である。

yylex 関数は、入力を読んで、次の終端記号を返す関数である。token という大域変数に、現在処理中の終端記号を代入する。eat 関数は、現在 token に入っている値が、引数として与えられた終端記号と等しいかどうか確かめ、等しければ次の終端記号を読み込む。
reportError 関数は、「構文に誤りがあります。」と表示し、プログラムを終了する。）
再帰下降構文解析プログラム#include <stdio.h>#include <stdlib.h>#include <string.h>#include <ctype.h>/* printf(), EOF など *//* exit() 用 *//* strcmp() 用 *//* isalpha() 用 *//* 終端記号に対するマクロの定義 */#define ID257/* トークン id */#define PR
258/* トークン pr */int token;/* 大域変数の宣言 *//* 関数プロトタイプ宣言 */void reportError(void);
int yylex(void);void eat(int t);void S(void);void S1(void);void E(void);void E1(void);/* **************************************************************** */* この部分に 関数 S, S1, E, E1 の定義を挿入する。
/* **************************************************************** *//* ここ以降は解答に直接関係はない。 */void reportError(void) {printf("構文に誤りがあります。\n"); exit(0); /* プログラムを終了 */}int main() {/* main関数 */token = yylex(); /* 最初のトークンを読む */S();
if (token == EOF) {printf("正しい構文です!\n");} else {reportError();
6*/

}
}
int yylex(void) {int c;
char buf[256];/* 簡易字句解析ルーチン */do { /* 空白は読み飛ばす。 */c = getchar();} while (c == ’␣’ || c == ’\t’ || c == ’\n’);
if (isalpha(c)) { /* アルファベットだったら… */char* ptr = buf;
ungetc(c, stdin);while (1) {c = getchar();if (!isalpha(c) && !isdigit(c)) break;*ptr++ = c;}
*ptr = ’\0’;
ungetc(c, stdin);if (strcmp(buf, "id") == 0) return ID;
if (strcmp(buf, "pr") == 0) return PR;
reportError();} else {/* 上のどの条件にも合わなければ、文字をそのまま返す。 */return c;/* ’;’ など */}}void eat(int t) {/* token （終端記号）を消費して、次の tokenを読む */if (token == t) {/* 現在のトークンを捨てて、次のトークンを読む */token = yylex();return;} else {reportError();}}7

VI. （LR 構文解析）「ˆ」, 「_」などの演算子はテキスト整形言語 LATEX で使われている演算子で、xˆa は上付きの添字 xa 、また x_a は下付きの添字 xa を表す。LATEX では x_aˆb を特別扱いして、これを xabや xa b ではなく、 xab のように整形する。
このことを踏まえて. . .
次のような BNF で与えられる文法

E →||||

E “_” E “ˆ” E · · · I
E “_” E· · · IIE “ˆ” E· · · III“{” E “}”· · · IVa··· Vに対して、LR 構文解析表を作成する。ただし、• · · · の後の I, II などは生成規則の番号である。
• E は非終端記号である。
• “_”,”ˆ”, “{”, “}”, “a” は終端記号である。このうち、”a” はアルファベット 1 文字からなるトークンを表す。
• “ˆ”, “_” 演算子の優先度は等しく、どちらも右結合である。
bison の出力する LR 構文解析表は次のようになる。 （注: bison に-v オプションを指定することによって、LR 構文解析表をファイルに出力させることができる。）
_0
⃝
1
⃝
2
⃝
3
⃝
4⃝
5
⃝
6
⃝
7
⃝
8⃝
9
⃝
10
⃝
11
⃝
12
⃝

ˆ

{1shift ⃝1shift ⃝reduce V6shift ⃝6shift ⃝6shift ⃝6shift ⃝6shift ⃝7shift ⃝7shift ⃝11shift ⃝7shift ⃝7shift ⃝a}$2shift ⃝2shift ⃝E
3goto ⃝
4goto ⃝

5shift ⃝8shift ⃝accept12shift ⃝shift ⃝
12shift ⃝shift ⃝
reduce IV
reduce II
reduce III
12shift ⃝shift ⃝??????

8

9goto ⃝
10
goto ⃝

12
goto ⃝

注:s
ここで、shift ⃝は、「シフトしてs へ遷移」
状態 ⃝、s は、goto ⃝「状態s へ遷移」⃝、reduce X は、「生成規則 X を使って還元」を表す。

(1) 〜 (2)次の入力列に対して、↑ の次（右）の記号をシフトした直後の（つまりシフトしたあと、還元がまだ起こっていないときの）スタックの状態はどのようになっているか?
(1) aˆb_cˆd↑(2) aˆ{b_c}ˆd↑

下の選択肢（(1)〜(2) 共通）から選べ。（左がスタックの底とする）

(A)

0 ⃝ˆ
3 ⃝
7
⃝E(E)

0 ⃝_
3 ⃝E
6 ⃝ˆ
9 ⃝
11⃝E(G)

0 ⃝ˆ
3 ⃝E
7 ⃝_
10 ⃝E
6 ⃝ˆ
9 ⃝
11⃝E(B)

0 ⃝ˆ
3 ⃝
6
⃝E(F)

(C)

0 ⃝ˆ
3 ⃝E
6 ⃝ˆ
9 ⃝
11⃝E(D)

0 ⃝ˆ
3 ⃝E
7 ⃝ˆ
10 ⃝
7⃝E0 ⃝_
3 ⃝E
7 ⃝ˆ
10 ⃝
7
⃝E(H)

0 ⃝ˆ
3 ⃝E
6 ⃝_
9 ⃝E
11 ⃝ˆ
9 ⃝
11⃝E

(3) a_bˆc という入力に対しては、c をシフトしたあと、まず生成規則 V による還元を行なっ12 という状態になる。て、DFA は⃝「還元還元衝突（reduce/reduce conflict）の時は、上（先）に書かれている構文規則が優先する。」という Bison の 衝突回避規則に従うと、LR 構文解析表の ? ? ? ? ? ? の部分には何が入るべきか、次の選択肢から選べ。
(A) reduce I(B) reduce II(C) reduce III

9(D) reduce IV(E) reduce Vコンパイラ・期末テスト計算用紙（冊子から切り離しても良い）10コンパイラ（2019 年度）
・期末テスト解答用紙（2019 年 08 月 01 日）

学籍番号

I. （Backus-Naur 記法）
(1)

氏名

(3×4)
(2)

(3)

(4)

II. （正規表現）
(1)

(3×4)
(2)

(3)

(4)

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

(2×4)

(2)

(3)

(4)

IV. （演算子順位法）

(1×8)

(1)

(2)

(3)

(4)

(5)
裏ページに続く。

(6)

(7)

(8)

11

V. （再帰下降構文解析）
S →(3, 2, 3, 3, 4, 5, 5)

(1)
S′ →

{
(3) {(4) {}}}

(2)

;
(5)
(6)

id=

pr

()

+

@

$

E→
E′ →
S →
S′ →
void E(void) {switch (token) {case ID:/* ←ここを埋める← */case ’(’:
default: reportError();/* ←ここを埋める← */}(7)

void E1(void) { /* ↓ここを埋める↓ */}VI. （LR 構文解析）(1)

(5×3)
(2)

(3)

授業・テストの感想

12