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

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

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

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

3 ６．１ 構文主導型翻訳方式 意味動作 生成規則にプログラムを付加 構文解析しながら中間コードを生成 このプログラムを 出力動作 意味規則
６．１　構文主導型翻訳方式 意味動作 生成規則にプログラムを付加 構文解析しながら中間コードを生成 このプログラムを 出力動作 意味規則 などと呼ぶ

4 ６．１ 構文主導型翻訳方式 翻訳属性 プログラムの扱うデータ 文法記号に付随させる E → E(1) + E(2)
６．１　構文主導型翻訳方式 翻訳属性 プログラムの扱うデータ 文法記号に付随させる E → E(1) + E(2) {E.VAL:=E(1).VAL+E(2).VAL} 上昇型構文解析を想定 葉に近い方が結びつきが強い 翻訳属性

5 ６．１ 構文主導型翻訳方式 解析木上の翻訳属性 意味動作で翻訳属性を計算可能
６．１　構文主導型翻訳方式 解析木上の翻訳属性 意味動作で翻訳属性を計算可能 E→E(1)+E(2)　{E.VAL:=E(1).VAL+E(2).VAL} E→digit　 {E.VAL:=digit} 解析木を構成しない場合は，スタックを利用

6 ６．１ 構文主導型翻訳方式 解析木上の翻訳属性 E→E(1)+E(2) {E.VAL:=E(1).VAL+E(2).VAL}
６．１　構文主導型翻訳方式 解析木上の翻訳属性 E→E(1)+E(2) {E.VAL:=E(1).VAL+E(2).VAL} E→digit　 {E.VAL:=digit} 6 E 3 1 E 2 3 E E E 1 + 2 + 3

7 ６．２ 構文主導型翻訳系の実現 スタックによる実現 A → X Y Z {A.VAL:= f (X.VAL, Y.VAL, Z.VAL)}
６．２　構文主導型翻訳系の実現 スタックによる実現 A → X Y Z {A.VAL:= f (X.VAL, Y.VAL, Z.VAL)} 状態 値 Z Z.VAL Y Y.VAL X X.VAL 状態 値 A A.VAL

8 ６．２ 構文主導型翻訳系の実現 意味動作 電卓の実現 S→E$ E→E(1)+E(2) E→E(1)*E(2) E→(E(1)) E→I
６．２　構文主導型翻訳系の実現 電卓の実現 意味動作 S→E$ E→E(1)+E(2) E→E(1)*E(2) E→(E(1)) E→I I→I(1) digit I→digit {print E.VAL} {E.VAL:=E(1).VAL+E(2).VAL} {E.VAL:=E(1).VAL*E(2).VAL} {E.VAL:=E(1) .VAL} {E.VAL:=I.VAL} {I.VAL:=10*I(1).VAL+LEXVAL} {I.VAL:=LEXVAL}

9 ６．２ 構文主導型翻訳系の実現 2 3 * 5 + 4 $ 3 - 2 I I 23 - 2 電卓の実現 S→E$ E→E(1)+E(2)
６．２　構文主導型翻訳系の実現 電卓の実現 2 3 * $ S→E$ E→E(1)+E(2) E→E(1)*E(2) E→(E(1)) E→I I→I(1) digit I→digit 3 - 2 I I 23 - 2

10 ６．２ 構文主導型翻訳系の実現 2 3 * 5 + 4 $ E 5 I - 5 * - E I 115 23 電卓の実現 S→E$
６．２　構文主導型翻訳系の実現 電卓の実現 2 3 * $ S→E$ E→E(1)+E(2) E→E(1)*E(2) E→(E(1)) E→I I→I(1) digit I→digit E 5 I - 5 * - E I 115 23

11 ６．２ 構文主導型翻訳系の実現 2 3 * 5 + 4 $ E 4 I - 4 + - E 119 115 電卓の実現 S→E$
６．２　構文主導型翻訳系の実現 電卓の実現 2 3 * $ S→E$ E→E(1)+E(2) E→E(1)*E(2) E→(E(1)) E→I I→I(1) digit I→digit E 4 I - 4 + - E 119 115

12 ６．２ 構文主導型翻訳系の実現 2 3 * 5 + 4 $ 答えは１１９ $ - E S 119 - 電卓の実現 S→E$
６．２　構文主導型翻訳系の実現 電卓の実現 2 3 * $ S→E$ E→E(1)+E(2) E→E(1)*E(2) E→(E(1)) E→I I→I(1) digit I→digit 答えは１１９ $ - E S 119 -

13 ６．３　中間コード 中間コード プログラ ミング言語 中間コード 機械語 機械に依存しない

14 ６．３　中間コード よく用いられる中間コード 後置記法 構文木 ４つ組 ３つ組

15 ６．４ 後置記法 後置記法 e1, e2, ..., ek : 後置記法の式 q : k項演算子
６．４　後置記法 後置記法 e1, e2, ..., ek : 後置記法の式 q : k項演算子 e1 e2 ... ek q : e1, ..., ekで表された値にq を 　適用した結果 (a + b) * c a b + c * a * (b + c) a b c + * (a + b) * (c + d) a b + c d + *

16 ６．４　後置記法 後置式の評価 1 3 + 5 * 20 4

17 ６．５　解析木と構文木 構文木 解析木　　　　構文木 演算子 / 被演算子 * d a * (b + c) / d a + b c

18 ６．５ 解析木と構文木 (1) E → E(1) op E(2)
６．５　解析木と構文木 構文木への構文主導型翻訳 (1) E → E(1) op E(2) {E.VAL := NODE(op, E(1).VAL, E(2).VAL} (2) E → ( E(1) ) {E.VAL := E(1).VAL} (3) E → -E(1) {E.VAL := UNARY(-, E(1).VAL} (4) E → id {E.VAL := LEAF(id)}

19 ６．６ ３番地コード，４つ組および３つ組 ３番地コード A := B op C 算術・論理演算子 名前，定数，一時名
６．６　３番地コード，４つ組および３つ組 ３番地コード A := B op C 算術・論理演算子 名前，定数，一時名 X + Y * Z T1 := Y * Z T2 := X + T1

20 ６．６ ３番地コード，４つ組および３つ組 その他の３番地文 A := B op C A := op B goto L
６．６　３番地コード，４つ組および３つ組 その他の３番地文 A := B op C A := op B goto L if A relop B goto L param A, call P, n A := B[I], A[I] := B A := addr B, A := *B, *A := B

21 ６．６ ３番地コード，４つ組および３つ組 ４つ組 T1 := - B T2 := C + C T3 := T1 * T2 A := T3
６．６　３番地コード，４つ組および３つ組 ４つ組 T1 := - B T2 := C + C T3 := T1 * T2 A := T3 OP ARG1 ARG2 RESULT (0) uminus B _ T1 (1) + C D T2 (2) * T3 (3) := A

22 ６．６ ３番地コード，４つ組および３つ組 ３つ組 T1 := - B T2 := C + C T3 := T1 * T2 A := T3
６．６　３番地コード，４つ組および３つ組 ３つ組 T1 := - B T2 := C + C T3 := T1 * T2 A := T3 OP ARG1 ARG2 (0) uminus B _ (1) + C D (2) * (3) := A

23 ６．６ ３番地コード，４つ組および３つ組 ３つ組 A[I] := B OP ARG1 ARG2 (0) []= A I (1) _ B
６．６　３番地コード，４つ組および３つ組 ３つ組 A[I] := B OP ARG1 ARG2 (0) []= A I (1) _ B A := B[I] OP ARG1 ARG2 (0) =[] B I (1) := A

24 ６．６ ３番地コード，４つ組および３つ組 間接３つ組 T1 := - B T2 := C + C T3 := T1 * T2 A := T3
６．６　３番地コード，４つ組および３つ組 間接３つ組 T1 := - B T2 := C + C T3 := T1 * T2 A := T3 ST (0) (14) (1) (15) (2) (16) (3) (17) OP ARG1 ARG2 (14) uminus B _ (15) + C D (16) * (17) := A

25 ６．６　３番地コード，４つ組および３つ組 表現法の比較 記憶域 文の順序の変更 ４つ組 △ ○ ３つ組 ◎ × 間接３つ組

26 ６．６ ３番地コード，４つ組および３つ組 単一の配列による表現 T1 := - B T2 := C + C T3 := T1 * T2
６．６　３番地コード，４つ組および３つ組 単一の配列による表現 T1 := - B T2 := C + C T3 := T1 * T2 A := T3 OP ARG1 ARG2/RES RESULT (0) uminus B T1 (1) + C D T2 (2) * T3 (3) := A

27 ちょっと休憩 （雑談）

28 学会旅行 ★★★ 長岡（９８．８） 高知（９８．１２） サン・フランシスコ（９９．１） サン・ファン（９９．４） ★ 鶯宿温泉（９９．５）
香港（９９．１２） サン・ディエゴ（００．１） ペナン（００．１１）

29 学会旅行 ★ 京都（０１．３） 台北（０１．７） ★★★ 那覇（０１．７） 倉敷（０１．１２） サン・アントニオ（０２．１）
プラハ（０２．６） マドリッド（０２．６） 湯布院（０２．８），金沢（０２．９），…

30 休憩おわり

31 ６．７　代入文の翻訳 整数型の代入文 A → id := E E → E + E | E * E | - E | ( E ) | id

32 ６．７ 代入文の翻訳 抽象的な水準での翻訳方式 E.P : 式Eの値を保持する名前 E.C : 式Eの値を計算する３番地文の列
６．７　代入文の翻訳 抽象的な水準での翻訳方式 E.P : 式Eの値を保持する名前 E.C : 式Eの値を計算する３番地文の列 N( ) : 新しい一時名の生成関数

33 ６．７ 代入文の翻訳 抽象的な水準での翻訳方式 A → id := E {A.C := E.C++[id.P := E.P]}
６．７　代入文の翻訳 抽象的な水準での翻訳方式 A → id := E {A.C := E.C++[id.P := E.P]} E → E(1)+E(2) {E.P:=N( ); E.C:=E(1).C++E(2).C++[E.P:=E(1).P+E(2).P]} （乗算も同じ） E → -E(1) {E.P:=N( ); E.C:=E(1).C++ [E.P:=-E(1).P]} E →(E(1)) {E.P:=E(1).P; E.C:=E(1).C} E → id {E.P:=id.P; E.C:=[ ]}

34 ６．７ 代入文の翻訳 具体的な水準での翻訳方式 A → id := E {GEN(id.P := E.P)}
６．７　代入文の翻訳 具体的な水準での翻訳方式 A → id := E {GEN(id.P := E.P)} E → E(1)+E(2) {E.P:=N( ); GEN(E.P:=E(1).P+E(2).P)} E → E(1)*E(2) {E.P:=N( ); GEN(E.P:=E(1).P*E(2).P)} E → -E(1) {E.P:=N( ); GEN(E.P:=-E(1).P)} E →(E(1)) {E.P:=E(1).P} E → id {E.P:=id.P}

35 ６．７ 代入文の翻訳 混合型の代入文 式Eの翻訳属性として型を表すE.Mを導入 X:=Y+I*J T1 := I int* J
６．７　代入文の翻訳 混合型の代入文 式Eの翻訳属性として型を表すE.Mを導入 X:=Y+I*J T1 := I int* J T2 := inttoreal T1 T3 := Y real+ T2 X := T3 実数型 整数型