問題 1 ：次の問に答えよ． 1. 次に挙げるものの役割を，それぞれ説明し

問題 1 ：次の問に答えよ．
1. 次に挙げるものの役割を，それぞれ説明しなさい．
記号表，中間表現，静的リンク，スタックポインタ
2. 浮動小数点を表す正規表現を示しなさい．浮動小数点は，0.5E11 のよ
うに，E の前に実数，後ろに整数を記述する（両者とも先頭に − を付
けることができる）．また，実数は，小数点の前後の 0 が省略できるが，
小数点だけでは，実数ではないことに気を付けよ．
問題 2 ：次の文法について答えよ．
0
1
2
3
S
E
E
E
→
→
→
→
E
E
E
E
$
+E
*E
^E
4 E
5 E
6 E
→ (E)
→ -E
→ num
1. この文法は，曖昧性を含んでいる．次の性質を満たすように変形し，曖
昧性を解消せよ．適宜，新しい非終端記号を用意すること．
• +，* は，左結合の 2 項演算子である．^ は，右結合の 2 項演算子で
ある．-は，右結合の単項演算子である．
• 演算子の強さは，- > ^ > * > + である．
2. 変形した文法から，左再帰を除去せよ．
3. Yacc は，演算子に結合規則を指定することによって，上記のような曖
昧な文法でも扱える．演算子の結合規則を，1 のように指定したとする
と，次のトークン列を，Yacc で構文解析した際に生じるシフトと還元
を順に全て示せ．また，そのときの各スタックの様子も図示しなさい．
num + num * num * - - num ^ num ^ num + num
注シフトが生じるときは「∼(トークン）をシフト」，還元が生じると
きは「∼(生成規則）で還元」とし，状態は考慮しなくてよい．
問題 3 ：次の文法について答えよ．
0 S
1 P
2 P
→ P $
→ d
→ T EP
3 E
4 E
→
→ c
5 T
6 T
→
→
E
a
1. 各非終端記号の，nullable，FIRST，FOLLOW を求めなさい．
2. LR(0) の遷移図を示しなさい．
3. SLR 構文解析表を示しなさい．

Download Report