コンパイラ（ 2014 年度）・期末テスト問題用紙（ 2014 年 07 月 31 日（ 木）・ 10:30 〜 12:00 ）（ 問題訂正適用済み）
訂正は赤字

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

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

1

I. （ Backus-Naur 記法）
例: {a}に対する解析木

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

X →|
S →
|

“{” S “}”
“a”
S X
ε{

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

(1)

{aaa}

(2)

{a{}}

(3)

{{a}a}(4)yyyyyyyyyyyyyy

X E

EEEE
EESSX

εa}

{}{}

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

(1)xyxyxyxyy

(2)

(3)

xyxyxyyxy

xyxyxxyxy(4)

xyxyxyxyx

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

2

(1) （ 文字列リテラルの終わりを示す「 " 」を忘れた。）#include <stdio.h>
int main(void) {printf("Hello! World\n);return 0;}(2) （ printf 関数の引数の順番を間違えた。）#include <stdio.h>#include <math.h>int main(void) {printf(sin(0), "sin(0) = %f\n");return 0;}(3) （ブロックの波括弧 “{”〜“}” の代わりに角括弧 “[”〜“]” を使った。）#include <stdio.h>
int main(void) [int i;for (i=0; i<10; i++) [printf("Hello World!\n");]](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 “)”

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

解釈a == b == ca && b && ca >> b >> ca == 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)〜(5) を <·（シフト ）、 >·（ 還元）、 7（エラー） のうちもっとも適切なもので埋めよ。
左\右>>&&==()id終始<·(2)>·>·<·>·>·<·<·(4)>·<·>·>·

<·
(3)
<·(5)
<·>·>·<·<·<·<·<·
7
7(1)>·>·>·
>·>·

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

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

(1) E から左再帰を除去すると、次のような BNF が得られる。
E → F E0E 0 → ε | “+” F E 0
これを参考にして、S から左再帰を除去せよ。補助的に導入する非終端記号は S 0 とせよ。
以下の (2)〜(4) は、(1) で S と E から左再帰を除去して得られた BNF について答えよ。

(2) Follow(E 0 ) を求めよ。
(3) Follow(S 0 ) を求めよ。
(4) 下の構文解析表の E, E 0 の行を埋めよ。
id{};+ε(C)“+” F E 0$!

S →S0 →E→
E0 →F→(4) の解答は次の選択肢から選べ。
(A)

F E0

(B)

(D)

7

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

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

yylex 関数は、入力を読んで、次の終端記号を返す関数である。token という大域変数に、現在処理中の終端記号が代入される。eat 関数は、現在 token に入っている値が、引数として与えられた終端記号と等しいかど うか確かめ、等しければ次の終端記号を読み込む。）
reportError 関数は、「構文に誤りがあります。」と表示し 、 プログラムを終了する。
5

再帰下降構文解析プログラム#include <stdio.h>#include <stdlib.h>#include <string.h>#include <ctype.h>/* exit() 用 *//* strcmp() 用 *//* isalpha() 用 *//* 終端記号に 対するマクロの 定義 */#define ID257/* トークン id */int token;/* 大域変数の 宣言 *//* 関数プ ロト タ イプ 宣言 */void reportError(void);
int yylex(void);void eat(int t);void S(void);void S1(void);void E(void);void E1(void);void F(void);/* **************************************************************** */* この 部分に 関数 S, S1, E, E1, F の 定義を 挿入する 。
*//* **************************************************************** *//* ここ 以降は 解答に 直接関係は な い 。 */void reportError(void) {printf("構文に誤りがあります。\n"); exit(0); /* プ ログ ラ ムを 終了 */}int main() {/* main関数 */token = yylex(); /* 最初のト ー クン を 読 む */S();if (token == EOF) {printf("正しい構文です!\n");} else {reportError();}}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);6while (1) {c=getchar();if (!isalpha(c) && !isdigit(c)) break;*ptr++ = c;}
*ptr = ’\0’;
ungetc(c, stdin);return ID;} 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 のように整形する。
このことを踏まえて. . .
次のような文法

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 構文解析表をファイルに出力させることができる。）_ˆ

124

shift 6
shift 6

shift 7shift 7578910

shift 6
shift 612

shift 7

goto 3
goto 4shift 8acceptshift 1
shift 6E

shift 5shift 11shift 711$

shift 2
shift 2

shift 1
shift 1
reduce IV

6a}shift 1
shift 1
reduce V

03{

shift 2
shift 2

reduce II
reduce III
shift 2??????

8

goto 9goto 10

goto 12

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

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

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

(A)
(D)

0E3ˆ7(B)

0{1E4ˆ70 { 1 E 4 _ 6 E 9 ˆ 11(E)(C)

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

9(D) reduce IV(E) reduce Vコンパイラ・期末テスト計算用紙

コンパイラ・期末テスト計算用紙

コンパイラ（ 2014 年度）・期末テスト解答用紙（ 2014 年 07 月 31 日）

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

氏名

(3×4)
(2)

(3)

(4)

II. （ 正規表現）

(3×4)

(1)

(2)

(3)

(4)

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

(3×4)

(2)

(3)

(4)

IV. （ 演算子順位法）
(1)

(2×5)
(2)

V. （ 再帰下降構文解析）
S →

(3)

(4)

(5)
(3, 4, 4, 6, 6)

(1)
S0 →

{
(3) {(2)

裏ページに続く。

}}

id(4)

{}

;

+!

$

E→
E0 →
void E(void) { /* ↓ここを埋める↓ */}void E1(void) { /* ↓ここを埋める↓ */(5)}void F(void) {if (token == ID) {/* ←ここを埋める← */} else if () { /* ←ここを埋める← */eat(’{’); E(); eat(’!’); S(); eat(’}’);} else reportError();}VI. （ LR 構文解析）(1)
授業・テストの感想(4, 4, 3)(2)(3)