1.
高水準のプログラム言語で書かれたプログラムの実行には、どのような実行形態があるか。２つ以上の形態についてその実行の手順を述べなさい。また、それぞれの形態の特長を述べなさい。

2.
以下に示す CFG は2種類の文字 `a', `b' を並べたときに a と b の出現が同数になるものを生成する。

G: Σ = { a, b };

VN = { E, A, B, AS, BS };

P = { E →ε, E → EA, E → EB,

A → a ASb, AS → ε, AS → AS A,

B → b BSa, BS → ε, BS → BS B };

S = E.

但し、εは空の文字列を表す。

これを使うと例えば abba という文字列は
E ⇒ E B ⇒ Eb BSa ⇒ Eba ⇒ E Aba ⇒ Ea ASbba ⇒ Eabba ⇒ abba
のように導出できる。ここで下線で示した構文単位に生成規則を適用している。

(1) この例に上げた導出法を何と呼ぶか。

(2) もうひとつの導出法によって aabb という文字列を導出せよ。

3.
Pascal や C 言語では関数の再帰呼び出しが可能であるが、FORTRAN や COBOL では一般には関数の再帰呼び出しは禁止されている。あるプログラミング言語で再帰呼び出しを可能にするには、どのような機能が備えられていなければならないかを考察せよ。

4.
以下のLR解析法で「式」の構文解析を行う。スタック上には記号 X と状態 s を交互に置き、スタックの 最上段にある状態 s と入力素語 a から解析表 A を参照する ことによって動作を決定する。状態遷移は別の解析表 G で 与える。アルゴリズムと還元規則(構文規則)は以下のとおり。

(省略・リンク参照)

問い 以上のアルゴリズムと解析表を用いて ( i+i) *i $ を構文解析するときの、スタックと素語列の状態、オートマトンの動作を以下のような表にしたい。表を解析終了まで完成させなさい。

解析例
スタック 素語の列 動作
$0 (i+i)*i$ shift
$0(4 i+i)*i$ shift
$0(4i5 +i)*i$ reduce 6 (shiftは間違い)

解答例