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

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

1

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

X →
|
S →
|

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

例: {a;}に対する解析木{

次の各文について、上の BNF の非終端記号 X から導出されるものには 、その解析木 (parse tree) を右の例にならって書き、導出されないものには × を記せ。
（解析木は一通りとは限らないが 、そのうちひとつを書けば良い。）

yyyyyyyyyyyyyyX EEEEEEE}SSX FεaFFFFFF(1) {a;a;}(2) {{a;a}}(3) {a;{a;}}II. （ 正規表現）「 (y|xyyx)* 」という正規表現に (一部でなく) 全体がマッチする文字列には (L) を、「 (yx*y)*y 」という正規表現に (一部でなく) 全体がマッチする文字列には (R) を、両方に全体がマッチする文字列には (B) を、
ど ちらにも全体がマッチしない文字列には (N) をつけよ。
(1) yxyxxyxyy(2) yxyyxyyyy(3) yxyyxxyyx(4) yyyxxxxyy2;III. （コンパイラのフェーズ ）次の (1)〜(3) の C 言語のプログラムにはそれぞれ誤りがある。コンパイラのどのフェーズで最初に誤りが検出されるか？
（あるいはされないか？）もっとも適当なものを下の選択肢 (A)〜(E)から選べ。
(1) （ printf 関数に浮動小数点数を第 1 引数として渡そうとした。）#include <stdio.h>
int main(void) {printf(3.1415926);
return 0;}(2) （ main 関数の最初のブレース「 { 」を忘れた。）#include <stdio.h>
int main(void)
printf("Hello World!Y=n");return 0;}(3) （ 文字列の終わりを示す「 " 」を忘れた。）#include <stdio.h>
int main(void) {printf("Hello! WorldY=n);return 0;}(1)〜(3) の選択肢
(A) 字句解析フェーズでエラーが検出される。
(B) 構文解析フェーズでエラーが検出される。
(C) 意味解析フェーズでエラーが検出される。
(D) コード 生成フェーズでエラーが検出される。
(E) 実行時にエラーとなるか 、まったくエラーにならない（が作成者の意図と異なる動作をする）。

3

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

E→

id | E “<=>” E | E “&&” E | E “=” E | “(” E “)”

ただし 、この文法は曖昧なので、優先順位と結合性について次のように決めておく。
「 <=> 」は非結合、「 && 」は左結合、「 = 」は右結合で「 <=> 」は「 && 」 よりも優先順
位が高く、「 && 」は「 = 」よりも優先順位が高いものとする。
つまり、下表中の左の欄の式は、右の欄の式として解釈される。
式

解釈a <=> b <=> ca && b && ca = b = ca <=> b && ca && b <=> ca <=> b = c
a = b <=> ca && b = c
a = b && c

構文エラー
(a && b) && ca = (b = c)(a <=> b) && ca && (b <=> c)(a <=> b) = c
a = (b <=> c)(a && b) = c
a = (b && c)

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

&&

=()

id

終始

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

<·(2)
(3)
<·<·>·>·<·>·>·(4)<·>·>·<·<·<·<·<·✗✗✗>·>·>·

>·
>·

<·<·
<·<·<·✗✗

>·>·>·
✗
>·>·

<=>
&&
=()
id4

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

begin L ends
L “;” CC

ただし 、
「 C 」,「 L 」は非終端記号で、「 begin 」, 「 s 」,「 end 」, 「 ; 」は終端記号とする。
開始記号（ start symbol ）は C である。

(1) L の左再帰を除去する。新しく補助的な非終端記号 L0 を導入して、L の生成規則を
L → C L0のようにする時、L0 の生成規則を書け。
この左再帰を除去した生成規則に対して、以下の問に答えよ。

(2) First(C) を求めよ。
(3) Follow(L0 ) を求めよ。
さらに、この文法に対する構文解析表を作成する。

C→L→
L0 →

beginends;$begin L end

✗

s
(4)
(5)

✗✗

以下の問に答えよ。なお、解答中でエラーとなる欄には明示的に ✗ と書き、空欄のままにしないこと。

(4) L の行を埋めよ。
(5) L0 の行を埋めよ。

5VI. （ LR 構文解析）
次のような文法→|
B →|

S“x”
“{” B “}”BSε··· I· · · II· · · III· · · IVに対して、LR 構文解析表を作成する。ただし 、• · · · の後の I, II などは生成規則の番号である。
• 「 S 」, 「 B 」は非終端記号、「 { 」, 「 x 」, 「 } 」は終端記号である。
• 開始記号は「 S 」である。
bison の出力する LR 構文解析表は次のようになる。
（ 注: bison に -v オプションを与えると、LR 構文解析表をファイルに出力する。）
$1
2
3
45
6
7{x}

S

shift 3 shift 2
reduce I
reduce IV

Bgoto 4
goto 5

acceptshift 3 shift 2
reduce II
reduce III

goto 6

goto 7

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

(1) { x x { } }↑(2) { { x x } }↑下の選択肢から選べ。
（ 左がスタックの底とする）(1) の選択肢(2) の選択肢

(A).
(C).

1 { 3 B 5 { 3(A).
(C).

1 { 3 B 5 x 2

1 { 3 B 5 S 7 { 31 { 3 B 5 { 3 B 5 S 7 x 26(B).
(D).

1 { 3 B 5 x 2 { 3(B).
(D).

1 { 3 B 5 { 3 B 5 x 2

1 { 3 B 5 S 7 S 7 { 31 { 3 B 5 S 7 { 3 B 5 S 7 x 2

プログラム言語論（ ’08 年度）・期末テスト解答用紙 (’09 年 2 月 10 日)

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

氏名

(4×3)
(2).

(3).

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

(4×4)
(2).

(3).

(4).

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

(3×3)
(2).

(3).

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

(4×4)
(2).

(3).

(4).

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

(5,3,3,3,3)

L0 →{(3). {}}

(2).

begin
(4).
(5).

ends;

$

L→
L0 →

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