言語処理系（９） 金子敬一.

Presentation on theme: "言語処理系（９） 金子敬一."— Presentation transcript:

1 言語処理系（９） 金子敬一

2 ６ 構文主導型翻訳 ６．１ 構文主導型翻訳方式 ６．２ 構文主導型翻訳系の実現 ６．３ 中間コード ６．４ 後置記法 ６．５ 解析木と構文木
６　構文主導型翻訳 ６．１　構文主導型翻訳方式 ６．２　構文主導型翻訳系の実現 ６．３　中間コード ６．４　後置記法 ６．５　解析木と構文木 ６．６　 ３番地コード，４つ組および３つ組 ６．７　代入文の翻訳 ６．８　論理式 ６．９　制御の流れを変える文

3 ６．８ 論理式 式の形 E → E or E | E and E | not E | ( E ) | id | id relop id
６．８　論理式 式の形 E → E or E | E and E | not E | ( E ) | id | id relop id ただしrelopは，＜，≦，＝，≠，＞，≧のいずれか 　or, andは左結合 　not, and, orの順に優先順位

4 ６．８ 論理式 論理式の翻訳方法 基本的には次の２つ trueを1，falseを0などと数値的に符号化 制御の流れを用いる goto L
６．８　論理式 論理式の翻訳方法 基本的には次の２つ trueを1，falseを0などと数値的に符号化 制御の流れを用いる goto L if A goto L if A relop B goto L

5 ６．８　論理式 数値による表現 A or B and C T1 := B and C T2 := A or T

6 ６．８ 論理式 数値による表現 A < B or C (1) if A < B goto (4) (2) T1 := 0
６．８　論理式 数値による表現 A < B or C (1) if A < B goto (4) (2) T1 := 0 (3) goto (5) (4) T1 := 1 (5) T2 := T1 or C

7 ６．８ 論理式 数値による表現 E → E(1) or E(2) {T := N( ); E.P := T;
６．８　論理式 数値による表現 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) GEN(if id(1).P relop id(2).P goto NQ+3); GEN(T := 0); GEN(goto NQ+2); GEN(T := 1);}

8 ６．８ 論理式 制御の流れによる論理式の表現 A < B or C (1) if A < B goto (4)
６．８　論理式 制御の流れによる論理式の表現 A < B or C (1) if A < B goto (4) (2) T1 := 0 (3) goto (5) (4) T1 := 1 (5) T2 := T1 or C T2 := C T2 := 1

9 ６．８ 論理式 制御の流れによる論理式の表現 if E then S(1) else S(2) Eに対する コード S(1)に対する コード
６．８　論理式 制御の流れによる論理式の表現 if E then S(1) else S(2) Eに対する コード TRUE: S(1)に対する コード FALSE: S(2)に対する コード

10 ６．８　論理式 制御の流れによる論理式の表現 while E do S Eに対する コード TRUE: Sに対する コード FALSE:

11 ６．８ 論理式 制御の流れによる論理式の表現 分岐点の生成時には分岐先は未定 後埋め
６．８　論理式 制御の流れによる論理式の表現 分岐点の生成時には分岐先は未定 後埋め MAKELIST(i): アドレスiのみからなるリストを生成 MERGE(p1, p2): アドレスリストp1とp2を併合したリストを返す BACKPATCH(p, i): アドレスリストpが指定する４つ組の分岐先がiとなるように更新

12 ６．８ 論理式 制御の流れによる論理式の表現 翻訳属性 E.T: Eが真のときの未定の分岐先を持つ４つ組のアドレスリスト
６．８　論理式 制御の流れによる論理式の表現 翻訳属性 E.T: Eが真のときの未定の分岐先を持つ４つ組のアドレスリスト E.F: Eが偽のときの未定の分岐先を持つ４つ組のアドレスリスト

13 ６．８ 論理式 制御の流れによる論理式の表現 (1) E → E(1) or M E(2) {BACKPATCH(E(1).F, M.Q);
６．８　論理式 制御の流れによる論理式の表現 (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)}

14 ６．８ 論理式 制御の流れによる論理式の表現 (3) E → not E(1) {E.T := E(1).F; E.F := E(1).T}
６．８　論理式 制御の流れによる論理式の表現 (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}

15 ６．８ 論理式 制御の流れによる論理式の表現 (5) E → id {E.T := MAKELIST(NQ);
６．８　論理式 制御の流れによる論理式の表現 (5) E → id {E.T := MAKELIST(NQ); E.F := MAKELIST(NQ + 1); GEN(if id.P goto _); GEN(goto _)}

16 ６．８ 論理式 制御の流れによる論理式の表現 (6) E → id(1) relop id(2) {E.T := MAKELIST(NQ);
６．８　論理式 制御の流れによる論理式の表現 (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}

17 ６．８ 論理式 制御の流れによる論理式の表現 100: if P < Q goto _ 101: goto _
６．８　論理式 制御の流れによる論理式の表現 100: if P < Q goto _ 101: goto _ 102: if R < S goto _ 103: goto _ 104: if T < U goto _ 105: goto _ 102 T={100,104} F={103,105} 104 E E T={104} F={103,105} T={100} F={101} T={102} F={103} Q=102 T={104} F={105} E M E M E Q=104 P < Q or e R < S and e T < U

18 ６．８　論理式 混合型の式 算術式⊂論理式ならば論理式を数値として扱ったほうが便利；論理式を制御の流れとして表現する方法も利用可能

19 ちょっと休憩 （雑談）

20 写真（プラハ）

21 写真（プラハ）

22 写真（プラハ）

23 写真（プラハ）

24 写真（プラハ）

25 写真（プラハ）

26 写真（プラハ）

27 写真（プラハ）

28 写真（プラハ）

29 写真（プラハ）

30 写真（プラハ）

31 写真（プラハ）

32 写真（プラハ）

33 写真（プラハ）

34 写真（プラハ）

35 写真（プラハ）

36 写真（プラハ）

37 写真（プラハ）

38 写真（マドリッド）

39 写真（マドリッド）

40 写真（マドリッド）

41 写真（マドリッド）

42 写真（マドリッド）

43 写真（トレド）

44 写真（トレド）

45 写真（トレド）

46 写真（トレド）

47 写真（プラハ土産）

48 写真（マドリッド土産）

49 休憩おわり

50 ６．９ 制御の流れを変える文 無条件飛越し goto文の翻訳 後方分岐：ラベルの検索，３番地文生成
６．９　制御の流れを変える文 無条件飛越し goto文の翻訳 後方分岐：ラベルの検索，３番地文生成 前方分岐：ラベルの登録，３番地文生成，ラベルに番地を登録

51 ６．９ 制御の流れを変える文 構造的制御文 S → if E then S | if E then S else S
６．９　制御の流れを変える文 構造的制御文 S → if E then S | if E then S else S | while E do S | begin L end | A L → L; S | S

52 ６．９ 制御の流れを変える文 翻訳を実現するための方法 S → if E then M(1) S(1) N else M(2) S(2)
６．９　制御の流れを変える文 翻訳を実現するための方法 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 _)}

53 ６．９ 制御の流れを変える文 翻訳を実現するための方法 M → e {M.Q := NQ}
６．９　制御の流れを変える文 翻訳を実現するための方法 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)}

54 ６．９ 制御の流れを変える文 翻訳を実現するための方法 S → while M(1) E do M(2) S(1)
６．９　制御の流れを変える文 翻訳を実現するための方法 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}

55 ６．９ 制御の流れを変える文 翻訳を実現するための方法 S → A {S.N := MAKELIST()} L → L(1); M S
６．９　制御の流れを変える文 翻訳を実現するための方法 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}

56 ６．９ 制御の流れを変える文 翻訳を実現するための方法 while (A < B) do
６．９　制御の流れを変える文 翻訳を実現するための方法 while (A < B) do if (C < D) then X := Y + Z 100: if (A < B) goto 102 101: goto 107 102: if (C < D) goto 104 103: goto 100 104: T := Y + Z 105: X := T 106: goto 100: