Syntax Directed Translation

Merupakan cara untuk mengasosiasikan semantic rule dengan produksi. Berikut konsep syntax-directed translation.

Syntax-directed definition. Merupakan generalisasi CFG dimana setiap simbol grammar diasosiasikan dengan suatu atribut.

Atribut terdiri dari 2 bagian:

• Synthesized attribute → jika nilai pada node parse tree diperoleh dari atribut anaknya.
• Inherited attribute → jika nilainya didefinisikan olah atribut induk atau saudara kandung node tersebut.

Annoted parse tree. Parse tree yang menunjukkan harga dari atribut pada setiap node. Atribut symbol di sebelah kiri produksi dievaluasi berdasar atribut symbol di sebelah kanan.

Atribut terminal symbol diberikan oleh lexical analyzer.

Inherited attributes

Atribut dari suatu node ditentukan oleh atribut dari ayah atau yang di atau node tersebut.

Dependency graphs. Menunjukkan urutan evaluasi atribut suatu node.

E1 -> E2 + E3		{E1:= E2 + E3}
E1 -> E2 * E3		{E1:= E2 * E3}
E1 -> (E2)		{E1:= E2}
E ->i		{E := i, lexeme}

Interpretasi dari E1 -> E2+E3 adalah bahwa untuk mendapatkan E1 maka harus menjumlahkan nilai yang ada di E2 dan E3.

Misalnya digunakan Bottom-up parsing untuk pernyataan i+i*i, dan untuk membedakan tiap leksemes dan agar produksi tersebut mempunyai arti maka digunakan nilai, a, b dan c. Hasil parsingnya adalah sebagai berikut:

Stack	Input	Produksi	Aksi
$	i+i*i$
$i	+i*i$	E1->i	E1:=a
$E1	+i*iS
$E1+	i*i$
$E1+E2	*i$	E2->i	E2:=b
$E1+E2*	*i$
$E1+E2*i	i$
$E1+E2*i	$	E3->i	E3:=c
$E1+E2*E3	$	E4->E2*E3	E4:=E2*E3
$E1+E4	$	E5->E1+E4	E5:=E1+E4
$E5	$

Hasil terjemahan yang diperoleh untuk mengevaluasi instruksi a+b*c adalah 

E1:=a

E2:=b

E3:=c

E4:=E2*E3

E5:=E1+E4

Syntax Tree 

• Merupakan bentuk lebih sederhana parse tree
• Operator atau keywords tidak akan muncul pada leaves tetapi muncul sebagai parent dan suatu node.
• Semantic rules merupakan prosedur untuk membuat node dan mengisi field dari node.

Hasil penerjemahan di atas dalam bentuk syntax tree adalah sebagai berikut:

Representasi Antara (Intermediate Representation)

• Pohon sintaks
• Directed acyclic graph
• Notasi Posfix
• Three-address code

Pohon Syntax (Syntax Tree)

Untuk menyatakan pernyataan x=a*b+a*b, maka bentuk parse tree nya adalah:

Pohon sintaks untuk pernyataan yang sama adalah:

Direct Asyclic Graph

Notasi Posfix

Operator diletakkan setelah operand.

A+b*c -> abb*+

if C then A else B -> C A B ?

if C then if P then Q else R else B -> C P Q R ? B ?

Three-address code (3AC)

Pernyataan x = a+b*b diterjemahkan dalam 3AC menjadi

T:=b*b

X:=a + T

Dalam hal ini T adalah variabel temporer.

Kedua perintah di atas diterjemahkan dalam bahasa assembly untuk mesin IBM S/370 menjadi

L		3,B
M		2,B		{T:=b*b}
ST		3,T
L		3,A
A		3,T		{x:+a+T}
ST		3,X

Berbagi