h5 _ desain kompiler
Post on 30-Sep-2015
39 Views
Preview:
DESCRIPTION
TRANSCRIPT
-
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
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
-
Context-Free Grammar
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
-
Context-Free Grammar
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
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
-
Context-Free Grammar
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
-
Context-Free Grammar
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
-
Context-Free Grammar
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
-
Context-Free Grammar
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
-
Context-Free Grammar
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
-
Context-Free Grammar
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
-
Context-Free Grammar
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
-
Context-Free Grammar
Contoh: Grammar untuk sentence sederhana
Contoh string dalam bahasa ini adalah:
KW506
Desain
Kom
pile
r O
pim
S. S
itom
pul
-
Context-Free Grammar
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
-
Context-Free Grammar
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
-
Context-Free Grammar
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
-
Abstract Syntax Tree
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
-
Abstract Syntax Tree
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
-
Abstract Syntax Tree
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
-
Abstract Syntax Tree
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
-
Abstract Syntax Tree
Contoh abstract syntax tree untuk C expression:
KW
506
Desain
Kom
pile
r O
pim
S. S
itom
pul
-
Abstract Syntax Tree
Contoh:
Parse tree untuk ekspresi:
if (0) other else other
KW
506
Desain
Kom
pile
r O
pim
S. S
itom
pul
-
Abstract Syntax Tree
Menggunakan grammar berikut:
Diperoleh parse tree dan syntax tree berikut:
KW
506
Desain
Kom
pile
r O
pim
S. S
itom
pul
-
Abstract Syntax Tree
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
-
Abstract Syntax Tree
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
top related