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

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

1

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

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

S→ +S S| *S S| x

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

S FFFFFFFSS F*FFxxxx
FFxxFFxxxx
xxxxx+SSxxx
xx
xxx
(1)

* x x * x

(2)

(3)

* + x x x+ x * x + x x(4)* * x x + x x

II. （ 正規表現）
以下の文字列について、「 (yx|x(yz)*)* 」という正規表現にマッチする 先頭からの 最長の部分文字列の文字数を答えよ。例えば 、yxxyzyzyyzxy という文字列について考えると、その先頭の部分文字列 yxxyzyzは上の正規表現にマッチするが 、それより長い先頭からの部分文字列: yxxyzyzy, yxxyzyzyy,. . . , yxxyzyzyyzxy はいずれもマッチしないので、マッチする先頭からの最長の部分文字列の文
字数は 7 となる。
（なお、文字列の途中からの部分文字列は考えなくて良い。）

(1)
(3)

xyzyzyxyzyxy
yxzxyzyxxyzx

(2)
(4)

xyzyzyxxyzyz
xyzyxxyzyxxx

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

2x(1) （コメントを閉じるのを忘れた。）#include <stdio.h>
int main(void) { /* 閉じ 忘れ のコ メント
printf("Hello World!\n");return 0;}(2) （ 文末のセミコロン “;” を忘れた。）#include <stdio.h>
int main(void) {printf("Hello World!\n")return 0}(3) （ 文字列リテラルに一重引用符 「 ’ 」を使った。）#include <stdio.h>
int main(void) {printf(’Hello! World\n’);return 0;}(4) （ 文字列リテラルに二重引用符 「 " 」を忘れた。）#include <stdio.h>
int main(void) {printf(Hello);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) !! ca : (b : c)
構文エラー
(a !! b) : ca : (b !! c)(a !! b) == ca == (b !! c)(a : b) == ca == (b : c)以下の演算子順位行列の空欄 (1)〜(5) を <· 、  、 >· 、 7 のうちもっとも適切なもので埋めよ。
ただし 、7 はエラーを表すものとする。
（ 教科書などの記法では、エラーは空欄のままとしているが 、このテストでは無回答と区別するために明示的に 7 を書くことにする。）
左\右!!

:==()

id

終始

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

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

<·
<·
<·<·<·
777>·>·>·
(5)
>·>·

<·
<·
<·
<·
<·
77

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

!!
:
==
()
id4V. （ 再帰下降構文解析）
次のような BNF で定義された文法に対して再帰下降構文解析ルーチンを作成する。
L → A | L “!” A |A → N | A “&” N
N → “(” L “)” | id

L “ˆ” Aただし 、「 L 」, 「 A 」, 「 N 」は非終端記号で、「 ! 」, 「 ˆ 」, 「 & 」, 「 ( 」, 「 ) 」, 「 id 」は終端記号とする。開始記号（ start symbol ）は L である。

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

(2) Follow(L0 ) を求めよ。
(3) Follow(A0 ) を求めよ。
(4) 下の構文解析表の A, A0 の行を埋めよ。ただし 、$ は入力の終わりを表す。
id()!

ˆ$&

L→
L0 →A→
A0 →N→(4) の解答は次の選択肢から選べ。空欄のままにしないこと。
(A)

N A0(B)ε(C)“&” N A0(D)7

ただし 、7 は “エラー” を示す。
（ 教科書などの記法では、エラーは空欄のままとしているが 、このテストでは無回答と区別するために明示的に 7 を書くことにする。）(5) この文法に対して、入力が文法にしたがっていれば「正しい構文です。」間違っていれば「 構文に誤りがあります。」と表示する構文解析プログラムを作成する。プログラム（ 次ページ ）中の指定の部分に入る L, L1, A, A1, N 関数のうち、A, A1, N 関数の定義を完成させよ。ただし 、L, L1, A, A1, N は、それぞれ非終端記号 L, L0 , A, A0 , N に対応する関数である。
（プログラムの補足説明: プログラム中では、終端記号は、“&” のような 1 文字のものは、その字そのもの（の ASCII コード ）、id などのトークンは、C 言語のマクロ（ 例えば id の場合は ID ）として表現している。

yylex 関数は、入力を読んで、次の終端記号を返す関数である。token という大域変数に、現在処理中の終端記号を代入する。eat 関数は、現在 token に入っている値が、引数とし5て与えられた終端記号と等しいかど うか確かめ、等しければ次の終端記号を読み込む。）
reportError 関数は、「構文に誤りがあります。」と表示し 、 プログラムを終了する。
再帰下降構文解析プログラム#include <stdio.h>#include <stdlib.h>#include <string.h>#include <ctype.h>/* exit() 用 *//* strcmp() 用 *//* isalpha() 用 *//* 終端記号に 対するマクロの 定義 */#define ID
257/* トークン x */int token;/* 大域変数の 宣言 *//* 関数プ ロト タ イプ 宣言 */void reportError(void);
int yylex(void);void eat(int t);void L(void);void L1(void);void A(void);void A1(void);void N(void);/* **************************************************************** */* この 部分に 関数 L, L1, A, A1, N の 定義を 挿入する 。
*//* **************************************************************** *//* ここ 以降は 解答に 直接関係は な い 。 */void reportError(void) {printf("構文に誤りがあります。\n"); exit(0); /* プ ログ ラ ムを 終了 */}int main() {/* main関数 */token = yylex(); /* 最初のト ー クン を 読 む */L();if (token == EOF) {printf("正しい構文です!\n");} else {reportError();}}int yylex(void) {int c;
char buf[256];/* 簡易字句解析ル ーチン */do { /* 空白は 読み 飛ば す 。 */c = getchar();} while (c == ’ ’ || c == ’\t’ || c == ’\n’);6

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);return ID;} else {/* 上のど の 条件に も 合わなければ 、文字を その まま返す 。*/
return c;/* ’&’など */}}void eat(int t) {/* token（ 終端記号 ）を消費し て 、次の tokenを読む */if (token == t) {/* 現在のト ー クン を 捨てて 、次のト ー クン を 読 む */token = yylex();return;} else {reportError();}}7

VI. （ LR 構文解析）
次のような文法（ · · · の後の I, II などは生成規則の番号）

E →||
|

id“{” X “}”
E “{” X “}”
E “#” id··· I· · · II· · · III· · · IV

X → id “=” E··· V| X “;” id “=” E · · · V Iに対して、LR 構文解析表を作成する。ただし 、• 「 E 」,「 X 」は非終端記号で、「 id 」,「 { 」, 「 } 」, 「 # 」, 「 = 」, 「 ; 」は終端記号とする。
このうち、「 id 」はアルファベット 1 文字からなるトークンを表す。
• 開始記号（ start symbol ）は E である。
bison の出力する LR 構文解析表は次のようになる。 （ 注: bison に -v オプションを指定する
ことによって、LR 構文解析表をファイルに出力させることができる。）

0id{

shift 1

shift 2}

shift 7shift 8shift 6

shift 10shift 11
acceptshift 4shift 13
shift 1

goto 12shift 2

goto 14
reduce II

10shift 15

12

shift 16

shift 1113

reduce IV
reduce V shift 8

reduce V

14

reduce V

shift 7shift 17

15

reduce III

161718X

shift 9611

E

goto 559$

shift 448;

reduce I

37=goto 3

12#

shift 1
reduce VI

shift 2
shift 7

goto 18
reduce VI

shift 8

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

8

reduce VI

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

(1) {b=c;s=t}{x=y}↑(2) a{b=c#x}{s=t#y;u=v}↑(3) {a={x=y;z=u}}#a↑下の選択肢（ (1)〜(3) 共通）から選べ。
（ 左がスタックの底とする）

(A).
(B).
(C).
(D).
(E).
(F).
(G).
(H).
(I).

0 E 3 { 7 id 40 E 3 # 8 id 130 E 3 { 7 X 12 ; 11 id 150 E 3 { 7 id 4 = 9 E 14 ; 11 id 150 E 3 { 7 id 4 = 9 E 14 # 8 id 130 E 3 { 7 id 4 = 9 E 14 } 16 { 7 id 40 E 3 { 7 X 12 ; 11 id 4 = 9 E 14 ; 11 id 150 E 3 { 7 id 4 = 9 E 14 ; 11 id 4 = 9 E 14 ; 11 id 150 E 3 { 7 id 4 = 9 E 14 } 16 { 7 id 4 = 9 E 14 } 16 { 7 id 49コンパイラ・期末テスト計算用紙（ 冊子から切り離しても良い）コンパイラ・期末テスト計算用紙（ 冊子から切り離しても良い）コンパイラ（ 2015 年度）・期末テスト解答用紙（ 2015 年 07 月 30 日）

学籍番号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. （ 再帰下降構文解析）
L→

(3)

(4)

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

(1)
L0 →

{
(3) {
(2)

裏ページに続く。

}}

id(4)

()

!

ˆ&$

A→
A0 →
void A(void) { /* ↓ここを埋める↓ */}void A1(void) { /* ↓ここを埋める↓ */(5)}void N(void) {if (token == ID) {/* ←ここを埋める← */} else if (eat(’(’); L(); eat(’)’);} else reportError();) { /* ←ここを埋める← */}VI. （ LR 構文解析）(1)
授業・テストの感想

(4×3)
(2)

(3)