プログラム言語論（ ’09 年度）
・期末テスト問題用紙（ ’10 年 2 月 17 日（ 水）・ 18:00 〜 19:30 ）解答上、その他の注意事項

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

1

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

S→ +S S| *S S| x

例: * x + x x に対する解析木S FFFFFFFSS F*FFxxxx
FFxxxxFFxxxx
xxx+SSxxx
xxxx

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

xx(1) * * x x x(2) * x x + x(3) + + x x * x x

II. （ 正規表現）「 (ab|ba)*(a|ε) 」という正規表現に (一部でなく) 全体がマッチする文字列には (L) を、「 (aba|bab)*(b|ε) 」という正規表現に (一部でなく) 全体がマッチする文字列には (R) を、両方に全体がマッチする文字列には (B) を、
ど ちらにも全体がマッチしない文字列には (N) を記せ。

(1) ababaabab(2) ababababa(3) abababbab

2III. （コンパイラのフェーズ ）コンパイラは、字句（ 単語）を切り分ける字句解析フェーズ、プログラムの構造を木の形に表す構文解析フェーズ、変数の宣言や型のチェックを行なう意味解析（ 静的解析）フェーズ、目的のコード を生成するコード 生成フェーズなどに概念的に分けることができる。
次の (1)〜(3) の C 言語のプログラムにはそれぞれ誤りがある。コンパイラのどのフェーズで最初に誤りが検出されるか？（あるいはされないか？） もっとも適当なものを下の選択肢 (A)〜(E) から選べ。なお、(1)〜(3) のいずれも単独でコンパイルされ 、標準ライブラリとのみリンクされるものとする。
（つまり、他のファイルに変数や関数が定義されていることはない。）(1) （ 文字列リテラルに二重引用符「 " 」をつけるのを忘れた。）#include <stdio.h>
int main(void) {printf(Hello);
return 0;}(2) （ 文末のセミコロン「 ; 」を忘れた。）#include <stdio.h>
int main(void)
printf("Hello World!Y=n")return 0;}(3) （コメントを閉じるのを忘れた。）#include <stdio.h>
int main(void) { /* コメント
printf("Hello");return 0;}(1)〜(3) の選択肢
(A) 字句解析フェーズでエラーが検出される。
(B) 構文解析フェーズでエラーが検出される。
(C) 意味解析フェーズでエラーが検出される。
(D) コード 生成フェーズでエラーが検出される。
(E) 実行時にエラーとなるか 、まったくエラーにならない（が作成者の意図と異なる動作をする）。

3

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

E→

id | E “..” E | E “=” E | E “,” E | “(” E “)”

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

解釈

a .. b ..
a = b = ca , b , ca .. b = c
a = b .. ca .. b , c
a , b .. ca = b , ca , b = cc

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

=,()

id

終始

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

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

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

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

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

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

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

|x

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

(1) First(A) を求めよ。
(2) Follow(A0 ) を求めよ。
(3) 下の構文解析表の L の行を埋めよ。
(4) 下の構文解析表の A0 の行を埋めよ。

L→
L0 →
A→
A0 →
N→

||?
“||” A L0✗
?
✗&&?
✗✗?
✗!
?
✗N A0?
“!” N(?
✗N A0?
“(” L “)”)
?
ε✗?
✗x?
✗N A0?
x$?
ε✗?
✗

ただし 、✗ の欄は “構文誤り” を示す。

(3), (4) の解答は次の選択肢から選べ。
(A).

ε(B).

“&&” N A05(C).

✗(D).

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

E →||||

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

124shift 6
shift 6shift 5shift 5679shift 6shift 611

shift 2
shift 6

shift 5$E

shift 1

goto 3

shift 1

goto 4shift 7shift 5shift 1010aaccept
shift 2
shift 2
reduce IV58}

shift 2
reduce V
shift 203{

shift 1
shift 1

reduce III
reduce II
shift 1??????

6

goto 8goto 9goto 11

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

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

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

(A).
(C).

0{2E4ˆ5(B).

0{2{2E4ˆ5a1}7ˆ5(D).

0{2E4ˆ5E8ˆ50{2{2E4ˆ5E8}7ˆ5(3) a_bˆc という入力に対しては、c をシフトしたあと 1 回生成規則 V を用いて還元を行なって、0 E 3 _ 6 E 9 ˆ 10 E 11 というスタックの状態になる。
「還元還元衝突（ reduce/reduce conflict ）の時は、上（ 先）に書かれている構文規則が優先する。」という yacc/bison の 衝突回避規則に従うと、表の ? ? ? ? ? ? の部分には何が入るべきか、次の選択肢から選べ。
(A). shift 4(B). shift 77(C). reduce I(D). reduce III

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

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

氏名

(4×3)
(2).

(3).

II. （ 正規表現）

(4×3)

(1).

(2).

(3).

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

(4×3)
(2).

(3).

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

(4×4)
(2).

(3).

(4).

V. （ 再帰下降構文解析）(4×4){(2). {}}

(1).

||
(3).
(4).

&&!

()

x$

L→
A0 →

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

(3).