h5 _ desain kompiler

KW506 Desain Kompiler HO-5 Syntax Analysis: Context-Free Grammar

Opim S Sitompul

Contents

Pendahuluan

Context-Free Grammar

Dari RE ke CFG

Derivasi

Parse Tree

Abstract Syntax Tree

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Pendahuluan

Maksud dari lexical analysis adalah memisahkan input menjadi token.

Maksud dari syntax analysis (parsing) adalah menggabungkan kembali token-token tersebut.

Bukan untuk mengembalikannya menjadi daftar karakter, tetapi ke sebuah bentuk yang merefleksikan struktur teks tersebut.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Pendahuluan

Bentuk yang dimaksud adalah sebuah struktur data yang disebut syntax tree.

Dalam struktur tree ini, daun-daunnya adalah token-token yang ditemukan oleh lexical analysis.

Jika daun-daun ini dibaca dari kiri ke kanan, deretannya sama seperti yang terdapat pada teks input.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Pendahuluan

Selain untuk mencari struktur dari input teks, syntax analysis juga harus menolak teks yang tidak sah dengan melaporkan syntax error.

Lexical analysis dan syntax analysis menggunakan strategi dasar yang sama: Notasi yang sesuai untuk pemahaman

manusia diubah menjadi notasi tingkat-rendah seperti-mesin yang sesuai untuk eksekusi yang efisien (disebut parser generation).

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Pendahuluan

Sintaks bahasa pemrograman biasanya diberikan oleh aturan-aturan grammar dari context-free grammar (CFG).

Sama seperti RE yang menentukan struktur leksikal sebuah token yang dikenali oleh scanner.

Konvensi penamaan dan operasinya mirip seperti RE.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Context-free grammar (CFG) adalah sebuah notasi rekursif untuk menjabarkan himpunan-himpunan string dan mengenakan suatu struktur pada string tersebut.

Notasi ini sebagian hampir dapat diterjemahkan secara langsung ke dalam program-program rekursif, tetapi biasanya lebih efisien jika menggunakan stack automata. Mis.: LL(1) dan SLR

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Kelas struktur yang dapat dikenali oleh CFG jauh lebih besar daripada RE.

Algoritma yang digunakan untuk mengenali struktur ini juga sangat berbeda. (menggunakan pemanggilan rekursif dan pengelolaan stack untuk parsing)

Struktur data yang digunakan juga rekursif (disebut parse tree atau syntax tree).

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Sebuah bahasa didefinisikan pada suatu alfabet.

Mis.: himpunan token yang dihasilkan oleh lexer atau himpunan karakter-karakter alfanumerik.

Simbol-simbol dalam alfabet disebut terminal.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Context-free grammar secara rekursif mendefinisikan beberapa himpunan string.

Masing-masing himpunan diberi nama yang disebut nonterminal.

Himpunan nonterminal adalah himpunan disjoint dari himpunan terminal.

Salah satu dari nonterminal itu (disebut start symbol ) dipilih untuk menyatakan bahasa yang dijabarkan oleh grammar.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Himpunan-himpunan string dijabarkan oleh sejumlah production.

Tiap-tiap production menjabarkan string yang mungkin, yang termuat di dalam himpunan yang dinotasikan oleh sebuah nonterminal.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Bentuk umum production:

N X1 Xn dimana N adalah nonterminal dan X1 Xn

adalah nol atau lebih simbol, masing-masingnya bisa terminal atau nonterminal.

Makna notasi ini adalah bahwa himpunan yang dinotasikan oleh N memuat string-string yang diperoleh dengan menyambungkan (concatenating) string-string dari himpunan X1 Xn.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Contoh: RE: a+

A a

A a A

RE: a*

B

B a B

Production dengan di sisi kanan disebut empty productions.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Apabila digunakan beberapa nonterminal, haruslah jelas yang mana di antaranya adalah start symbol.

Contoh:

T R

T aTa

R b

R bR

dimana T adalah start symbol.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Dapat pula digunakan notasi singkat.

Contoh:

T R | aTa

R b | bR

dimana T adalah start symbol.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Contoh: Grammar G dengan aturan grammar tunggal

E ( E ) | a

Grammar di atas memiliki sebuah nonterminal E dan tiga terminal: (, ), dan a.

Menghasilkan bahasa:

L(G) = {a, (a), ((a)), (((a))), } = {(na)n | dimana n integer 0}

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Contoh: Grammar dengan aturan tunggal

E ( E )

L(G) = {}

Contoh 3: Grammar dengan aturan

E E + a | a

Grammar menghasilkan semua string yang terdiri dari a dipisahkan oleh +:

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Contoh: Grammar untuk sentence sederhana

Contoh string dalam bahasa ini adalah:

KW506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Contoh: Statement dengan -production

statement if-stmt | other

if-stmt if ( exp ) statement else-part

else-part else statement |

exp 0 | 1

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Contoh: Grammar dengan deretan sentence stmt-sequence stmt ; stmt-sequence | stmt stmt s

L(G) = { s, s;s, s;s;s, } Jika diizinkan empty statement: stmt-sequence stmt ; stmt-sequence | stmt s Atau stmt-sequence stmt-sequence ; stmt| stmt s L(G) = {, s, s;s, s;s;s, }

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Jika empty statement dibolehkan, tetapi masih menggunakan ; sebagai pemisah statement:

stmt-sequence nonempty-stmt-sequence | nonempty-stmt-sequence stmt ; nonempty-stmt-sequence

| stmt

stmt s

Grammar di atas memperlihatkan bagaimana perlunya memperhatikan peletakan -production pada waktu menggunakan struktur opsional.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Dari RE ke CFG

Sebuah RE secara sistematis dapat dituliskan sebagai sebuah CFG:

Satu nonterminal untuk setiap subekspresi dalam RE

Satu atau lebih productions untuk setiap nonterminal.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Dari RE ke CFG

Tiap-tiap subekspresi dari RE diberi nomor dan subekspresi si diberikan sebuah nonterminal Ni .

Production untuk Ni tergantung pada bentuk si.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Dari RE ke CFG Bentuk Si Production untuk Ni

Ni

a Ni a

sjsk Ni NjNk

sj |sk Ni Nj Ni Nk

sj * Ni NjNi Ni

sj + Ni NjNi Ni Nj

sj ?

Ni Nj Ni

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Dari RE ke CFG

Operasi pengulangan (*) pada RE, tidak diperlukan dalam BNF.

Contoh: Aturan grammar A A a | a (left recursive) Atau A a A | a (right recursive) Menghasilkan bahasa {an | n integer

1} Bahasa yang sama dihasilkan oleh RE:

a+

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Dari RE ke CFG

Secara umum,

A A |

Dimana dan adalah sembarang string dan tidak boleh mengandung A.

Aturan ini menghasilkan string berbentuk:

, , ,

Aturan grammar ini ekivalen dengan RE: *

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Dari RE ke CFG

Begitu pula aturan grammar A A | Menghasilkan semua string, RE: * , , , Grammar yang ekivalen dengan RE a*: A A a | atau A a A | Grammar ini disebut -production K

W506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Derivasi

Ide dasar derivasi adalah mempertimbangkan production sebagai aturan penulisan ulang:

Bilamana terdapat sebuah nonterminal, gantilah dengan sisi sebelah kanan dari production dimana nonterminal itu muncul di sisi sebelah kiri.

Lakukan dalam deretan simbol (terminal dan nonterminal).

Ulangi hingga hanya tinggal terminal saja.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Derivasi

Aturan grammar menentukan untaian token simbol-simbol yang sah dengan cara derivasi.

Derivasi adalah runtunan penggantian nama struktur dengan pilihan-pilihan pada sisi kanan aturan grammar.

Derivasi bermula dengan sebuah nama struktur dan berakhir dengan untaian token simbol-simbol.

Pada setiap langkah derivasi, dilakukan penggantian dengan menggunakan sebuah pilihan dari aturan grammar.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Derivasi

Relasi derivation didefinisikan oleh tiga rule: 1. N jika terdapat production N 2. (Reflexive) 3. jika terdapat sebuah sedemikian hingga

dan (Transitive) dimana , dan adalah sederetan (mungkin

kosong) simbol-simbol grammar (terminal dan nonterminal).

Anak panah yang digunakan berbeda dengan yang digunakan pada CFG CFG: menyatakan define. Derivasi: => menyatakan construct. K

W506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Derivasi

Contoh:

T R

T aTc

R

R RbR

Derivasi dari string aabbbcc:

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Derivasi

T aT c aaT cc aaRcc aaRbRcc aaRbcc aaRbRbcc aaRbRbRbcc aaRbbRbcc aabbRbcc aabbbcc

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Derivasi

Contoh: derivasi ekspresi ( 34 - 3 ) * 42

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Derivasi

Definisi:

Diberikan sebuah context-free grammar G dengan start symbol S, terminal symbol T dan production P , bahasa L(G) yang dihasilkan G didefinisikan berupa himpunan string terminal symbol yang dapat diperoleh dari derivasi S dengan menggunakan production P , yakni, himpunan

{w T | S w}

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Derivasi

Sebuah derivasi yang selalu menuliskan kembali nonterminal paling kiri disebut leftmost derivation.

Derivasi yang selalu menulskan kembali nonterminal paling kanan disebut rightmost derivation.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Derivasi memberikan metode untuk membangun string terminal tertentu dari sebuah awal nonterminal.

Tetapi derivasi tidak secara unik menyajikan struktur string yang dibangunnya.

Secara umum banyak derivasi untuk string yang sama.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Contoh:

( number number ) * number

Derivasi:

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Parse tree untuk sebuah derivasi adalah sebuah labeled tree dimana

interior node diberi label oleh non terminal,

leaf node diberi label oleh terminal

children dari internal node menyatakan penggantian dari nonterminal yang bersesuaian pada satu langkah derivasi K

W506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Contoh:

Parse tree:

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Langkah pertama dalam derivasi disesuaikan dengan ketiga children root node.

Langkah kedua berkorespondensi dengan number (satu anak paling kiri di bawah root) dan sama seperti dua langkah berikutnya.

Korespondensi dapat dilakukan secara eksplisit dengan menomori node internal parse tree dengan nomor langkah dimana nonterminalnya yang bersesuaian dietakkan di derivasi yang sesuai.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Contoh:

Internal node parse tree dinomori sebagai berikut:

Penomoran internal node parse tree sebenarnya merupakan preorder numbering.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Parse tree yang sama juga berkorespondensi dengan derivasi berikut:

Dan

Tetapi terdapat juga penomoran yang berbeda

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Kedua derivasi tersebut berkorespondensi dengan parse tree berikut:

Penomoran ini disebut postorder numbering.

Cat.: postorder traversal akan mendatangi internal node dengan urutan 4, 3, 2, 1. K

W506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Pada umumnya parse tree berkorespondensi dengan banyak derivasi, kesemuanya merepresentasikan struktur dasar yang sama untuk terminal-terminal string yang di-parse.

Akan tetapi ada kemungkinan untuk membedakan derivasi tertentu yang secara tunggal berkorespondensi dengan parse tree.

Left-most derivation adalah derivasi dimana nonterminal paling kiri diletakkan di tiap langkah derivasi. (Preorder numbering)

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Right-most derivation adalah derivasi dimana nonterminal paling kanan diletakkan di tiap langkah derivasi. (Preorder numbering terbalik).

Contoh parse tree, left-most, right-most dari (34 - 3) * 42

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Parse tree adalah representasi yang berguna tentang struktur string token, dimana token muncul sebagai leaf parse tree (dari

kanan ke kiri), dan internal node parse tree merepresentasikan

langkah-langkah dalam derivasi (dengan urutan tertentu).

Akan tetapi parse tree memiliki informasi yang jauh lebih banyak daripada yang dibutuhkan kompiler untuk menghasilkan executable code.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Parse Tree

Contoh: parse tree untuk ekspresi 3 + 4

Prinsip syntax-directed translation menyatakan bahwa arti atau semantic dari string 3+4 hendaklah langsung berkaitan dengan struktur sintaksis yang ditunjukkan oleh parse tree. nilai 3 dan nilai 4 akan ditambahkan

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Cara yang lebih sederhana untuk menyatakan informasi yang sama adalah dengan tree berikut:

Root merepresentasikan operasi penjumlahan nilai kedua child sub-ekspresi exp.

Sebaliknya masing-masing subtree menyajikan nilai dari child number-nya.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Ekspresi (34 3) * 42 dapat disajikan oleh tree berikut:

Abstract syntax tree dapat dipandang sebagai representasi tree dari notasi singkat abstract syntax.

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Contoh abstract syntax untuk expresi (34 3)*42 adalah:

OpExp(Times, OpExp(Minus, ConstExp(34), ConstExp(3)), ConstExp(42))

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Dengan notasi mirip BNF:

exp OpExp (op, exp, exp )

| ConstExp(integer)

op Plus | Minus | Times

Jika struktur abstract syntax tree aktual akan digunakan oleh parser, maka abstract syntax akan diberikan oleh sebuah deklarasi jenis data. K

W506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Contoh abstract syntax tree untuk C expression:

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Contoh:

Parse tree untuk ekspresi:

if (0) other else other

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Menggunakan grammar berikut:

Diperoleh parse tree dan syntax tree berikut:

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Contoh: grammar sentence, dipisahkan titik koma.

stmt-sequence stmt ; stt-sequence | stmt

stmt s

Parse tree string s;s;s

KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Abstract Syntax Tree Syntax tree

Semua node statement dapat disatukan dengan satu node saja

Masalahnya adalah node seq memiliki jumlah anak yang sembarang, sehingga sulit menyatakannya dengan jenis data tertentu. KW

506

Desain

Kom

pile

r O

pim

S. S

itom

pul


Alternatifnya, dapat digunakan representasi leftmost-child right-sibling untuk tree.

Pada representasi ini link fisik dari parent ke child hanya ada pada anak terkiri.

Children dihubungkan dari kiri ke kanan menggunakan linked-list standard yang disebut sibling link untuk membedakannya dari parent-child link. K

W506

Desain

Kom

pile

r O

pim

S. S

itom

pul

Abstract Syntax Tree Dengan susunan seperti ini kita dapat

membuang node seq, sehingga sintaks tree hanya menjadi:

Merupakan representasi paling sederhana dan paling mudah untuk sederetan benda dalam sebuah sytax tree.

Kesulitannya adalah bahwa link-link ini merupakan sibling link yang harus dibedakan dari child link, dan memerlukan field baru dalam deklarasi syntax tree. K

W506

Desain

Kom

pile

r O

pim

S. S

itom

pul

h5 _ desain kompiler

Documents