プログラム言語論（ ’06 年度）
・テスト問題用紙（ ’07 年 2 月 6 日（ 火）・ 8:50 〜 10:20 ）解答上、その他の注意事項

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

1

I. （ Backus-Naur 記法）
下の記号列の中で、次の BNF
N → N0 | 1N1 | εの 非終端記号 N から生成されるものには○、生成されないものには ×をつけよ。

(1)

1 0 1(2)0 1 0(3)0 1 1(4)1 1 1 1

II. （コンパイラのフェーズ ）次の (1)〜(3) の C 言語のプログラムにはそれぞれ誤りがある。コンパイラのどのフェーズで誤りが検出されるか？
（あるいはされないか？） もっとも適当なものを下の選択肢 (A)〜(E) から選べ。
(1) （ブロックの “{”〜“}” の代わりに大括弧 “[”〜“]” を使った。）#include <stdio.h>
int main(void) [int i;for (i=0; i<10; i++) [printf("Hello World!Y=n");]](2) （ 正弦関数 double sin(double) に文字列を渡した。）#include <stdio.h>#include <math.h>int main(void) {printf("sin(45 °) = %fY=n", sin("45 °"));
return 0;}(3) （ 文字列リテラルの終わりを示す「 " 」を忘れた。）#include <stdio.h>
int main(void) {printf("Hello! WorldY=n);return 0;}(1)〜(3) の選択肢
(A) 字句解析フェーズでエラーが検出される。
(B) 構文解析フェーズでエラーが検出される。
(C) 意味解析フェーズでエラーが検出される。
(D) コード 生成フェーズでエラーが検出される。
(E) 実行時にエラーとなるか、まったくエラーにならない（が作成者の意図と異なる動作をする）。

2III. （ 正規表現）
以下の表で「 (ab|ba)*(a|ε) 」と「 (aba|bab)*(b|ε) 」という正規表現について、それぞれ 、ababaabab 、 ababababa 、abababbab という文字列と全体がマッチする時は○を全体がマッチしない時は ×をつけよ。
ababaababababababaabababbab(ab|ba)*(a|ε)

(1)

(2)

(3)

(aba|bab)*(b|ε)

(4)

(5)

(6)

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

E→

id | E “#” E | E “+” E | E “*” | “(” E “)”

ただし 、この文法は曖昧なので、優先順位と結合性について次のように決めておく。
「 # 」と「 + 」は、いずれも右結合で、「 * 」は「 # 」よりも優先順位が高く、「 # 」は「 + 」よりも優先順位が高いものとする。つまり、「 a # b * 」は 「 a # (b *) 」と解釈され、「 a + b # c 」は「 a + (b # c) 」と解釈される。
以下の演算子順位行列の空欄を <·（シフト ）、 >·（還元）、 err（エラー）のいずれかで埋めよ。
左\右#<·

*<·

(<·)
err

id
<·

終始+<·+(1)

(2)

<·

<·>·

<·>·

#*()
id

(3)
>·
<·>·>·

(4)
>·
<·>·
>·

<·
>·
<·>·
>·

<·
err
<·
err
err>·
>·
>·
>·

<·
err
<·
err
err>·
>·
err
>·
>·

3



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

SLE
F→→→→

if E then S else S | begin L end | print E “;”ε | S LF | E “+” F
id | “(” E “)”

ただし 、「 S 」,「 L 」, 「 E 」,「 F 」は非終端記号、「 if 」, 「 then 」, 「 else 」, 「 begin 」, 「 end 」,「 print 」, 「 ; 」, 「 + 」, 「 id 」,「 ( 」, 「 ) 」は終端記号である。また、開始記号は「 S 」である。

(1) E の生成規則から左再帰を除去せよ。ただし補助的な非終端記号として E 0 を用いること。
(2) First(S ) を求めよ。
(3) Follow(L) を求めよ。
(4) 〜 (6)
この文法に対して、入力が文法にしたがっていれば「正しい構文です。」間違っていれば「 構文に誤りがあります。」と表示する構文解析プログラムを作成する。プログラム（ 次
ページ ）中の空欄 (4)〜(6) を埋めよ。ただし 、非終端記号 S , L, E, E 0 , F に対応する関数
は、それぞれ S, L, E, E1, F である。
（プログラムの補足説明: プログラム中では、終端記号は、“;” のような 1 文字のものは、その字そのもの（の ASCII コード ）、if などのキーワード は、C 言語のマクロ（ 例えば ifの場合は IF ）として表現している。

yylex 関数は、入力を読んで、次の終端記号を返す関数である。token という大域変数に、現在処理中の終端記号が代入される。eat 関数は、現在 token に入っている値が、引数として与えられた終端記号と等しいかど うか確かめ、等しければ次の終端記号を読み込む。）

4

再帰下降構文解析プログラム/* これより上の部分は問題に直接関係がないので後掲 *//* 関数プロトタイプ宣言 */void S(void);void L(void);void E(void);void E1(void);void F(void);void S(void) {if (token == IF) {eat(IF); E(); eat(THEN); S(); eat(ELSE); S();} else if (token == BEGIN) {(4)} else if (token == PRINT) {eat(PRINT); E(); eat(’;’);} else {printf("構文に誤りがあります。Y=n"); exit(0); /* プログラムを終了 */}}void L(void) {if ((5)) {S(); L();(6)) {} else if (/* 何もしない */} else {
printf("構文に誤りがあります。Y=n"); exit(0); /* プログラムを終了 */}}/* 関数 E(), E1(), F() は直接問題に関係ないので省略する */int main() {/* main 関数 */token = yylex(); /* 最初のトークンを読む */S();
printf("正しい構文です!Y=n");}（ 参考） 上のプログラムで省略された最初の部分（ 問題には直接は関係ない。）#include <stdio.h>#include <stdlib.h>#include <string.h>#include <ctype.h>/* exit() 用*//* strcmp() 用 *//* isalpha() 用 *//* 終端記号に対するマクロ */#define IF257/* トークン if*/
#define THEN
258/* トークン then */#define ELSE
259/* トークン else */#define BEGIN
260/* トークン begin */#define END
261/* トークン end*/#define PRINT262/* トークン print */#define NUM
263/* トークン num*/

次ページに続く5int token;/* 大域変数の宣言 */int yylex(void) {int c;
char buf[256];/* 簡易字句解析ルーチン */do { /* 空白は読み飛ばす。 */c = getchar();} while (c == ’ ’ || c == ’Y=t’ || c == ’Y=n’);
if (isalpha(c)) { /* アルファベットだったら… */char* ptr = buf;
ungetc(c, stdin);while (1) {c=getchar();if (!isalpha(c) && !isdigit(c)) break;*ptr++ = c;}
*ptr = ’Y=0’;
ungetc(c, stdin);}if (strcmp(buf, "if")==0) {/* キーワード でないか */return IF;} else if (strcmp(buf, "then")==0) {return THEN;} else if (strcmp(buf, "else")==0) {return ELSE;} else if (strcmp(buf, "begin")==0) {return BEGIN;} else if (strcmp(buf, "end")==0) {return END;
} else if (strcmp(buf, "print")==0) {return PRINT;} else {printf("構文に誤りがあります。Y=n"); exit(0); /* プログラムを終了 */}} else if (isdigit (c)) { /* 数字だったら… */double poi;ungetc(c, stdin); scanf("%lf", &poi);return NUM;
} else {/* 上のどの条件にも合わなければ 、文字をそのまま返す。*/
return c;/* ’(’, ’)’, ’+’, ’;’ など */}void eat(int t) {/* token（ 終端記号）を消費して、次の token を読む */if (token == t) {/* 現在のトークンを捨てて、次のトークンを読む */token = yylex();return;} else {printf("構文に誤りがあります。Y=n"); exit(0); /* プログラムを終了 */}}6

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 文字からなるトークンを表す。
下に示すのは bison が自動生成した LR 構文解析表である。

01

while
shift 1
shift 1do=id
shift 2
shift 2

reduce IV2

shift 53

shift 74567

shift 1
shift 1
shift 1

shift 2
shift 2
shift 2
reduce II
reduce III
reduce I

8910+$

Egoto 3
goto 4

reduce IV
shift 6
acceptshift 6
goto 8goto 9goto 10shift 6

reduce II

shift 6

reduce I

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

(A).
(C).

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

0E 3=5E 8+60 id 2 = 5 E 8 + 6(B).
(D).

0 E 3 = 5 id 2 + 6(B).
(D).

0 while 1 E 4 + 6 id 2 do 70 id 2 = 5 id 2 + 6(2) の選択肢
(A).
(C).

0 while 1 E 4 do 70 while 1 id 2 + 6 id 2 do 7

70 while 1 E 4 + 6 E 9 do 7

プログラム言語論（ ’06 年度）
・テスト解答用紙 (’07 年 2 月 6 日)

学籍番号

氏名

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

(3×4)
(2).

(3).

(4).

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

(3×3)
(2).

(3).

III. （ 正規表現）

(3×6)

(1).

(2).

(3).

(4).

(5).

(6).

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

(4×4)
(2).

(3).

V. （ 再帰下降構文解析）
(1).

(4).
(4, 4, 4, 3, 2, 2)

E →E0 →{(3). {}}

(2).

(4).
(5).
(6).
VI. （ LR 構文解析）
(1).

(3×2)
(2).

テストの感想