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

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

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

６．１ 構文主導型翻訳方式 翻訳属性 プログラムの扱うデータ 文法記号に付随させる E → E(1) + E(2) ６．１　構文主導型翻訳方式 翻訳属性 プログラムの扱うデータ 文法記号に付随させる 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} 解析木を構成しない場合は，スタックを利用

６．１ 構文主導型翻訳方式 解析木上の翻訳属性 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

６．２ 構文主導型翻訳系の実現 スタックによる実現 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

６．２ 構文主導型翻訳系の実現 意味動作 電卓の実現 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}

６．２ 構文主導型翻訳系の実現 2 3 * 5 + 4 $ 3 - 2 I I 23 - 2 電卓の実現 S→E$ E→E(1)+E(2) ６．２　構文主導型翻訳系の実現 電卓の実現 2 3 * 5 + 4 $ 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

６．２ 構文主導型翻訳系の実現 2 3 * 5 + 4 $ E 5 I - 5 * - E I 115 23 電卓の実現 S→E$ ６．２　構文主導型翻訳系の実現 電卓の実現 2 3 * 5 + 4 $ 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

６．２ 構文主導型翻訳系の実現 2 3 * 5 + 4 $ E 4 I - 4 + - E 119 115 電卓の実現 S→E$ ６．２　構文主導型翻訳系の実現 電卓の実現 2 3 * 5 + 4 $ 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

６．２ 構文主導型翻訳系の実現 2 3 * 5 + 4 $ 答えは１１９ $ - E S 119 - 電卓の実現 S→E$ ６．２　構文主導型翻訳系の実現 電卓の実現 2 3 * 5 + 4 $ 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 -

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

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

６．４ 後置記法 後置記法 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 + *

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

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

６．５ 解析木と構文木 (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)}

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

６．６ ３番地コード，４つ組および３つ組 その他の３番地文 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

６．６ ３番地コード，４つ組および３つ組 ４つ組 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

６．６ ３番地コード，４つ組および３つ組 ３つ組 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

６．６ ３番地コード，４つ組および３つ組 ３つ組 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

６．６ ３番地コード，４つ組および３つ組 間接３つ組 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

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

６．６ ３番地コード，４つ組および３つ組 単一の配列による表現 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

ちょっと休憩 （雑談）

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

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

休憩おわり

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

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

６．７ 代入文の翻訳 抽象的な水準での翻訳方式 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:=[ ]}

６．７ 代入文の翻訳 具体的な水準での翻訳方式 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}

６．７ 代入文の翻訳 混合型の代入文 式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 実数型 整数型