Document

言語処理系（９）
金子敬一
６構文主導型翻訳
６．１構文主導型翻
訳方式
６．２構文主導型翻
訳系の実現
６．３中間コード
６．４後置記法
６．５解析木と構文
木
６．６３番地コード，
４つ組および３つ組
６．７代入文の翻訳
６．８論理式
６．９制御の流れを
変える文
６．８論理式
• 式の形
E → E or E | E and E | not E | ( E )
| id | id relop id
ただしrelopは，＜，≦，＝，≠，＞，≧の
いずれか
or, andは左結合
not, and, orの順に優先順位
６．８論理式
• 論理式の翻訳方法
基本的には次の２つ
−trueを1，falseを0などと数値的に符
号化
− 制御の流れを用いる
goto L
if A goto L
if A relop B goto L
６．８論理式
• 数値による表現
A or B and C
T1 := B and C
T2 := A or T
６．８論理式
• 数値による表現
A < B or C
(1)
(2)
(3)
(4)
(5)
if A < B goto (4)
T1 := 0
goto (5)
T1 := 1
T2 := T1 or C
６．８論理式
• 数値による表現
E → E(1) or E(2)
{T := N( ); E.P := T;
GEN(T := E(1).P or E(2).P)}
E → id(1) relop id(2)
{T := N( ); E.P := T;
GEN(if id(1).P relop id(2).P
goto NQ+3); GEN(T := 0);
GEN(goto NQ+2); GEN(T := 1);}
６．８論理式
• 制御の流れによる論理式の表現
A < B or C
(1)
(2)
(3)
(4)
(5)
if A < B goto (4)
T1 := 0
T2 := C
goto (5)
T1 := 1
T2 := 1
T2 := T1 or C
６．８論理式
• 制御の流れによる論理式の表現
if E then S(1) else S(2)
Eに対する
コード
TRUE: S(1)に対する
コード
FALSE: S(2)に対する
コード
６．８論理式
• 制御の流れによる論理式の表現
while E do S
Eに対する
コード
TRUE:
FALSE:
Sに対する
コード
６．８論理式
• 制御の流れによる論理式の表現
分岐点の生成時には分岐先は未定
後埋め
MAKELIST(i): アドレスiのみからなるリス
トを生成
MERGE(p1, p2): アドレスリストp1とp2を併
合したリストを返す
BACKPATCH(p, i): アドレスリストpが指
定する４つ組の分岐先がiとなるように更
新
６．８論理式
• 制御の流れによる論理式の表現
翻訳属性
E.T: Eが真のときの未定の分岐先を持つ４
つ組のアドレスリスト
E.F: Eが偽のときの未定の分岐先を持つ４
つ組のアドレスリスト
６．８論理式
• 制御の流れによる論理式の表現
(1) E → E(1) or M E(2)
{BACKPATCH(E(1).F, M.Q);
E.T := MERGE(E(1).T, E(2).T);
E.F := E(2).F}
(2) E → E(1) and M E(2)
{BACKPATCH(E(1).T, M.Q);
E.T := E(2).T;
E.F := MERGE(E(1).F, E(2).F)}
６．８論理式
• 制御の流れによる論理式の表現
(3) E → not E(1)
{E.T := E(1).F;
E.F := E(1).T}
(4) E → ( E(1) )
{E.T := E(1).T;
E.F := E(1).E}
６．８論理式
• 制御の流れによる論理式の表現
(5) E → id
{E.T := MAKELIST(NQ);
E.F := MAKELIST(NQ + 1);
GEN(if id.P goto _);
GEN(goto _)}
６．８論理式
• 制御の流れによる論理式の表現
(6) E → id(1) relop id(2)
{E.T := MAKELIST(NQ);
E.F := MAKELIST(NQ + 1);
GEN(if id(1).P relop id(2).P goto_);
GEN(goto _)}
(7) M → e
{M.Q := NQ}
６．８論理式
• 制御の流れによる論理式の表現
T={100,104}
E F={103,105}
T={100}
F={101}
E
P
<
T={102}
Q=102 F={103}
E
M
Q
or
e
R
<
100:
101:
102:
103:
104:
105:
if P
goto
if R
goto
if T
goto
< Q goto _
_
102
< S goto 104
_
_
< U goto _
_
E T={104}
F={103,105}
T={104}
M
E F={105}
Q=104
S and e
T
<
U
６．８論理式
• 混合型の式
算術式⊂論理式ならば論理式を数値として
扱ったほうが便利；論理式を制御の流れとし
て表現する方法も利用可能
ちょっと休憩
（雑談）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（プラハ）
写真（マドリッド）
写真（マドリッド）
写真（マドリッド）
写真（マドリッド）
写真（マドリッド）
写真（トレド）
写真（トレド）
写真（トレド）
写真（トレド）
写真（プラハ土産）
写真（マドリッド土産）
休憩おわり
６．９制御の流れを変える文
• 無条件飛越し
goto文の翻訳
後方分岐：ラベルの検索，３番地文生成
前方分岐：ラベルの登録，３番地文生成，ラ
ベルに番地を登録
６．９制御の流れを変える文
• 構造的制御文
S → if E then S
| if E then S else S
| while E do S
| begin L end
|A
L → L; S
|S
６．９制御の流れを変える文
• 翻訳を実現するための方法
S → if E then M(1) S(1) N else M(2) S(2)
{BACKPATCH(E.T,M(1).Q);
BACKPATCH(E.F,M(2).Q);
S.N := MERGE(S(1).N, N.N, S(2).N)}
N→e
{N.N := MAKELIST(NQ);
GEN(goto _)}
６．９制御の流れを変える文
• 翻訳を実現するための方法
M→e
{M.Q := NQ}
S → if E then M S(1)
{BACKPATCH(E.T,M.Q);
S.N := MERGE(E.F, S(1).N)}
６．９制御の流れを変える文
• 翻訳を実現するための方法
S → while M(1) E do M(2) S(1)
{BACKPATCH(S(1).N, M(1).Q);
BACKPATCH(E.T, M(2).Q);
S.N := E.F;
GEN(goto M(1).Q)}
S → begin L end
{S.N := L.N}
６．９制御の流れを変える文
• 翻訳を実現するための方法
S→A
{S.N := MAKELIST()}
L → L(1); M S
{BACKPATCH(L(1).N, M.Q);
L.N := S.N}
L→S
{L.N := S.N}
６．９制御の流れを変える文
• 翻訳を実現するための方法
while (A < B) do
if (C < D) then X := Y + Z
100:
101:
102:
103:
104:
105:
106:
if (A < B) goto 102
goto 107
if (C < D) goto 104
goto 100
T := Y + Z
X := T
goto 100:

Download Report