2.
以下に示す CFG は2種類の文字 `a', `b' を並べたときに a と b の出現が同数になるものを生成する。
G: Σ = { a, b };これを使うと例えば abba という文字列は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.
但し、εは空の文字列を表す。
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は間違い) |