BOTTOM-UP PARSING



SYNTAX DIRECTED TRANSLATION

DEFENISI DAN KONSEP

Mengasosiasikan semantic rule deng-an produksi

Konsep syntax-directed translation

input parse dependency evaluasi

string tree graph semantic rule

3. Syntax-directed definition sebagai generalisasi CFG dimana setiap symbol grammar diasosiasikan suatu atribut

Atribut terdiri 2 bagian :

Synthesized attribute

inherited attribute

ATRIBUT SINTETIS

Annotated parse tree menunjukkan harga atribut pada setiap node.

Attribut simbol disebelah kiri produksi grammar dievaluasi berdasarkan attri-but simbol disebelah kanan, contohnya :

|Produksi |Sematik Rule |

|L ( E |Print (E.val) |

|E ( E + T |E.val := E.val + T.val |

|E ( T |E.val := T.val |

|T ( T * F |T.val := T.val * F.val |

|T ( F |T.val := F.val |

|F ( (E) |F.val := E.val |

|F ( digit |F.val := digit.lexval |

Attribut simbol terminal diberikan oleh lexical analyzer

INHERITED ATTRIBUTES

Attribute suatu node ditentukan oleh atrribut dari rootnya, contoh :

|Produksi |Sematik Rule |

|D ( TL |L.int := T.type |

|T ( int |T.type := integer |

|T ( real |T.type := real |

|L ( L1 , id |L1.type := L.in |

| |addtype(id.entry, L.in) |

|L ( id |addtype(id.entry, L.in) |

DEPENDENCY GRAPHS

Menunjukkan urutan evaluasi atribut suatu node. contoh atribut sintetis :

E( E1 + E2

Dependency graph :

E val

E1 val + E2 val

Dependency graph untuk atribut inheri-tansi adalah :

D

T 4 in 5 L 6

type

real in 7 L 8 , id3 3

entry

in 9 L 10 , id2 2 entry

Id1 1 entry

Dari graph diatas, urutan evaluasi adalah :

a4 := real;

a5 := a4;

addtype ( id3.entry, a5 );

a7 := a5;

addtype ( id2.entry, a7 );

a9 := a7;

addtype ( id1. entry, a9 );

SYNTAX TREE

Merupakan bentuk lebih sederhana parse tree

Operator atau keywords tidak akan muncul pada leaves tetapi muncul sebagai parent dari suatu node.

Semantic rules merupakan procedure untuk membuat node dan mengisi field dari node.

KONSTRUKSI POHON SINTAKS

Gunakan fungsi dibawah untuk membuat node ekspressi dengan operator binary dan mengembalikan suatu pointer ke node terbaru.

• mknode(op, left, right)

Membuat node operator dengan label op dan 2 field yang berisi pointer terhadap left dan right

• mkleaf(id, entry)

Membuat suatu node identifier dengan label id dan field yang berisi entry serta suatu pointer ke simbol table entry untuk identifier

• mkleaf(num, val)

Membuat suatu node bilangan dengan label num dan suatu field berisi val

Contoh :

Suatu ekspresi : a – 4 + c

Dalam sekuens ini bahwa : p1, p2, …, p5 adalah node pointer dan entrya, entryb adalah pointer entry simbol table untuk identifier a dan c, untuk jelasnya :

1) p1 := mkleaf (id, entrya);

2) p2 := mkleaf (num, 4);

3) p3 := mknode (‘-‘, p1, p2);

4) p4 := mkleaf (id, entryc);

5) p5 := mknode (‘+’, p3, p4)

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download