言語処理系（８）
金子敬一
６ 構文主導型翻訳
６．１ 構文主導型翻
訳方式
６．２ 構文主導型翻
訳系の実現
６．３ 中間コード
６．４ 後置記法
６．５ 解析木と構文
木
６．６ ３番地コード，
４つ組および３つ組
６．７ 代入文の翻訳
６．８ 論理式
６．９ 制御の流れを
変える文
６．１ 構文主導型翻訳方式
• 意味動作
生成規則にプログラムを付加
構文解析しながら中間コードを生成
このプログラムを
−意味動作
−出力動作
−意味規則
などと呼ぶ
６．１ 構文主導型翻訳方式
• 翻訳属性
プログラムの扱うデータ
文法記号に付随させる
翻訳属性
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→digit {E.VAL:=digit}
E
3
1
E
3
2
E
1
6
E
+
2
E
+
3
６．２ 構文主導型翻訳系の実現
• スタックによる実現
A→XYZ
{A.VAL:= f (X.VAL, Y.VAL, Z.VAL)}
状態
Z
Y
X
値
Z.VAL
Y.VAL
X.VAL
状態
値
A
A.VAL
６．２ 構文主導型翻訳系の実現
• 電卓の実現
S →E$
(1)
(2)
→
+
E E E
(1)
(2)
→
*
E E E
(1)
→(
E E )
E→ I
I→I(1) digit
I→digit
意味動作
{print E.VAL}
(1)
(2)
{E.VAL:=E .VAL+E .VAL}
(1)
(2)
{E.VAL:=E .VAL*E .VAL}
(1)
{E.VAL:=E .VAL}
{E.VAL:=I.VAL}
{I.VAL:=10*I(1).VAL+LEXVA
L}
{I.VAL:=LEXVAL}
６．２ 構文主導型翻訳系の実現
• 電卓の実現
S →E$
(1)
(2)
→
+
E E E
(1)
(2)
→
*
E E E
(1)
→(
E E )
E→ I
I→I(1) digit
I→digit
2 3 * 5 + 4 $
3
-
2
I
23
-2
６．２ 構文主導型翻訳系の実現
• 電卓の実現
S →E$
(1)
(2)
→
+
E E E
(1)
(2)
→
*
E E E
(1)
→(
E E )
E→ I
I→I(1) digit
I→digit
2 3 * 5 + 4 $
5I
E
-5
*
-
EI
115
23
６．２ 構文主導型翻訳系の実現
• 電卓の実現
S →E$
(1)
(2)
→
+
E E E
(1)
(2)
→
*
E E E
(1)
→(
E E )
E→ I
I→I(1) digit
I→digit
2 3 * 5 + 4 $
4I
E
-4
+
-
E
119
115
６．２ 構文主導型翻訳系の実現
• 電卓の実現
2 3 * 5 + 4 $
S →E$
(1)
(2)
→
+
E E E
(1)
(2)
→
*
E E E
答えは１１９
(1)
E→(E )
E→ I
$
I→I(1) digit
E
S
I→digit
119
-
６．３ 中間コード
• 中間コード
プログラ
ミング言語
中間コード
機械に依存しない
機械語
６．３ 中間コード
• よく用いられる中間コード
− 後置記法
−構文木
− ４つ組
− ３つ組
６．４ 後置記法
• 後置記法
e1, e2, ..., ek : 後置記法の式
q : k項演算子
e1 e2 ... ek q : e1, ..., ekで表された値にq を
適用した結果
(a + b) * c
a * (b + c)
(a + b) * (c + d)
a b + c *
a b c + *
a b + c d + *
６．４ 後置記法
• 後置式の評価
1
4
20
3
+
5
*
６．５ 解析木と構文木
• 構文木
解析木
構文木
/
被演算子
*
a * (b + c) / d
a
d
+
b
c
演算子
６．５ 解析木と構文木
• 構文木への構文主導型翻訳
(1) E → E op E
(1)
(2)
op
{E.VAL := NODE( , E .VAL, E .VAL}
(1)
(1)
(
)
(2) E → E
{E.VAL := E .VAL}
(3) E → -E(1)
(1)
{E.VAL := UNARY( , E .VAL}
(4) E → id
{E.VAL := LEAF(id)}
(1)
(2)
６．６ ３番地コード，４つ組および３つ組
• ３番地コード
算術・論理演算子
A := B op C
名前，定数，一時名
X + Y * Z
T1 := Y * Z
T2 := X + T1
６．６ ３番地コード，４つ組および３つ組
• その他の３番地文
−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
(0)
(1)
OP
uminus
+
ARG1
B
C
ARG2
_
D
RESULT
T1
T2
(2)
(3)
*
:=
T1
T3
T2
T3
A
_
６．６ ３番地コード，４つ組および３つ組
• ３つ組
T1 := - B
T2 := C + C
T3 := T1 * T2
A := T3
(0)
(1)
OP
uminus
+
ARG1
B
C
ARG2
_
D
(2)
(3)
*
:=
(0)
A
(1)
(2)
６．６ ３番地コード，４つ組および３つ組
• ３つ組
A[I] := B
(0)
(1)
OP
[]=
ARG2
I
_
ARG1
A
B
OP
=[]
:=
ARG1
B
A
ARG2
I
_
A := B[I]
(0)
(1)
(0)
６．６ ３番地コード，４つ組および３つ組
• 間接３つ組
T1 := - B
T2 := C + C
T3 := T1 * T2
A := T3
(0)
(1)
ST
(14)
(15)
(2)
(3)
(16)
(17)
(14)
(15)
OP
uminus
+
ARG1
B
C
ARG2
_
D
(16)
(17)
*
:=
(14)
A
(15)
(16)
６．６ ３番地コード，４つ組および３つ組
• 表現法の比較
４つ組
３つ組
間接３つ組
記憶域
文の順序の変更
△
◎
○
○
×
○
６．６ ３番地コード，４つ組および３つ組
• 単一の配列による表現
T1 := - B
T2 := C + C
T3 := T1 * T2
A := T3
ARG1
B
ARG2/RES
(0)
OP
uminus
(1)
+
C
D
T2
(2)
*
:=
T1
T3
T2
A
T3
(3)
RESULT
T1
ちょっと休憩
（雑談）
学会旅行
•
•
•
•
•
•
•
•
長岡（９８．８）
高知（９８．１２）
サン・フランシスコ（９９．１）
サン・ファン（９９．４）
鶯宿温泉（９９．５）
香港（９９．１２）
サン・ディエゴ（００．１）
ペナン（００．１１）
★★★
★★★
★★★
★★★
★
★★
★★★
★★
学会旅行
•
•
•
•
•
•
•
•
★
京都（０１．３）
★
台北（０１．７）
★★★
那覇（０１．７）
★
倉敷（０１．１２）
★★★
サン・アントニオ（０２．１）
★★★
プラハ（０２．６）
★★
マドリッド（０２．６）
湯布院（０２．８），金沢（０２．９），…
休憩おわり
６．７ 代入文の翻訳
• 整数型の代入文
A → id := E
E → E + E | E * E | - E | ( E ) | id
６．７ 代入文の翻訳
• 抽象的な水準での翻訳方式
−E.P : 式Eの値を保持する名前
− E.C : 式Eの値を計算する３番地文の列
−N( ) : 新しい一時名の生成関数
６．７ 代入文の翻訳
• 抽象的な水準での翻訳方式
A → id := E {A.C := E.C++[id.P := E.P]}
(1)
(2)
+
E → E E {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)}
E → E(1)+E(2) {E.P:=N( ); GEN(E.P:=E(1).P+E(2).P)}
(1)
(2)
(1)
(2)
*
E → E E {E.P:=N( ); GEN(E.P:=E .P*E .P)}
E → -E(1) {E.P:=N( ); GEN(E.P:=-E(1).P)}
(1)
(1)
(
)
E→ E
{E.P:=E .P}
E → id {E.P:=id.P}
６．７ 代入文の翻訳
• 混合型の代入文
式Eの翻訳属性として型を表すE.Mを導入
X:=Y+I*J
実数型 整数型
T1 := I int* J
T2 := inttoreal T1
T3 := Y real+ T2
X := T3

Document