TEKNIK KOMPILASI
Sekolah Manajemen Informatika dan Komputer (STMIK) Palangkaraya
2012
Konsep & Notasi Bahasa
KonsepKonsep dandan NotasiNotasi bahasabahasa Teknik Kompilasi merupakan kelanjutan dari konsep-
konsep yang telah kita pelajari dalam teori bahasa danotomata
Thn 56-59 Noam Chomsky melakukan penggolongantingkatan dalam bahasa, yaitu menjadi 4 class
Penggolongan tingkatan itu disebut dengan hirarkiChomsky
1959 Backus memperkenalkan notasi formal baru untuksintaks bahasa yang lebih spesifik
Peter Nour (1960) merevisi metode dari sintaks. Sekarangdikenal dengan BNF (Backus Nour Form)
KonsepKonsep dandan NotasiNotasi bahasabahasa Tata bahasa (grammar) adalah sekumpulan dari
himpunan variabel-variabel, simbol-simbol terminal, simbol
non-terminal, simbol awal yang dibatasi oleh aturan-aturan
produksi
Aturan produksi adalah pusat dari tata bahasa yang
menspesifikasikan bagaimana suatu tata bahasa melakukan
transformasi suatu string ke bentuk lainnya
KonsepKonsep dandan NotasiNotasi bahasabahasa
Sintaks : suatu aturan yang memberitahu apakah sesuatu
kalimat (string) adalah valid dalam program atau tidak
Semantic : suatu aturan-aturan yang memberikan arti kepada
program
Sebuah simbol : suatu entitas abstrak yang tidak kita definisikan secara formal. Contoh: huruf dan digit.
String (kata/untai): suatu deretan berhingga dari simbol-simbol. Contoh: ‘abcd’ adalah sebuah string, yang terdiri dari simbol ‘a’, ‘b’, ‘c’ dan ‘d’. Panjang string merupakan jumlah simbol yang membentuk string.
String kosong dinyatakan dengan simbol ɛ. Panjang string = 0.
Penggolongan ChomskyBahasa Mesin Automata Aturan Produksi
Konsep dan Notasi bahasa
Tipe 3 Atau Regular
Finite state automata (FSA) meliputi; deterministic Finite Automata (DFA) & Non Deterministic Finite Automata (NFA)
adalah sebuah simbol variabel maksimal memiliki sebuah simbol variabel yang bila ada terletak diposisi paling kanan
Tipe 2 Atau Contex Free
Push Down Automata adalah sebuah simbol variabel
Tipe 1 Atau Contex Sensitive
Linier Bounded Automata || <= ||
Tipe 0 Atau Unrestricted/ Phase Structure/ natural language
Mesin Turing Tidak ada Batasan
Keterangan menyatakan simbol – simbol yang berada di ruas kiri aturan
produksi menyatakan simbol – simbol yang berada di ruas kanan aturan
produksi Simbol-simbol terdiri dari simbol terminal dan non
terminal/variabel (masih bisa diturunkan lagi) Simbol terminal biasanya dinyatakan dengan huruf kecil, contoh :
‘a’, ’b’, ‘c’ Sementara non terminal dengan huruf besar, contoh : ‘A’, ‘B’, ‘C’
Aturan Produksi Aturan produksi dinyatakan dalam bentuk :
“ ” dibaca : menghasilkan , atau menurunkan
Dengan menerapkan aturan produksi, suatu tata bahasa bisamenghasilkan sejumlah string.
Himpunan string tersebut adalah bahasa yang didefinisikanoleh tata bahasa tersebut.
Aturan Produksi Contoh aturan produksi :
T a dibaca : “T menghasilkan a”
E T | T + Edibaca : “E menghasilkanT atau E menghasilkanT + E”Merupakan pemendekan dari :E TE T+E
Simbol ‘|’ menyatakan ‘atau’
Aturan ProduksiAturan Produksi Tipe O / Unrestricted: Tidak ada batasan pada aturan produksi
Abc De
Tipe 1 / Context sensitive: Panjang string ruas kiri harus lebih kecil atau sama dengan ruas kanan(|α| ≤ |β|)
Ab DeFCD eFS ɛ
Tipe 2 / Context free grammar: Ruas kiri haruslah tepat satu simbol variableB CDeFgD BcDe
Tipe 3 / Regular: Ruas kiri hanya 1 simbol variabel, Ruas kanan hanya memiliki maksimal 1 simbolnon terminal / variabel dan diletakkan paling kanan sendiri
A eA efgA efgHC D
Aturan produksi yang tidak legal !!!
Simbol ɛ tidak boleh berada pada ruas kirimisal ɛAbdɛ merupakan string kosong
Aturan produksi yang ruas kirinya hanya memuat simbolterminal sajamisal : a bd atau ab bd
Bahasa manusia/bahasa alami termasuk ke dalam tata bahasa Tipe 0/unrestricted, tidak ada batasa pada aturan produksinya.
Batasan context sensitive biasanya turut digunakan dalam prosesanalisis semantik pada tahapan kompilasi
Bahasa context free menjadi dasar dalam pembentukan suatuparser / proses analisis sintaksis, dideskripsikan dengan notasiBNF (Backus Normal Form)
Hirarki Chomsky
RegularRegular
Context free
Context Sensitive
Unrestricted
NotasiNotasi BNF (Backus Normal Form)BNF (Backus Normal Form) Aturan Produksi bisa dinyatakan dengan notasi BNF
BNF menggunakan abstraksi untuk struktur syntax
::= sama identik dengan simbol
| sama dengan atau
< > pengapit simbol non terminal
{ } Pengulangan dari 0 sampai n kali
Misalkan aturan produksi sbb:
E T | T+E | T-E
T a
Notasi BNF-nya adalah
<E> ::= <T> | <T> + <E> | <T> - <E>
<T>::= a
Contoh Tata Bahasa SederhanaContoh Tata Bahasa Sederhana <program> ::= BEGIN <statement-list> END
<statement-list> ::= <statement> | <statement>; <statement-list> <statement> ::= <var> := <expression> <expression> ::= <term> | <term><op1> <expression> <term> ::= <factor> | <factor> <op2> <term> <factor> ::= <var> | <constant>
<var> ::= A|B| ….| Z <op1> ::= + | - | = <op2> ::= ^ | * | / <constant> ::= <real_number> | <integer_part>
<real_number> ::= <integer_part> . <fraction> <integer_part> ::= <digit> | <integer_part> < digit> <fraction> ::= <digit> | <digit> <fraction> <digit> ::= 0|1|….|9
ContohContoh
BEGIN
A := 1;
B := A + 2
END
Latihan ! TBO, Firrar Utdirartatmo hal 13-15…
Diagram StateDiagram State
Digunakan untuk mendapatkan token, mempermudah
melakukan analisis lexical
Token adalah simbol terminal dari teori bahasa dan
automata
S
ID
INT
PLUS
MINUS
+
-
huruf
Digit
Huruf, Digit
DigitBlank
Contoh : suatu tata bahasa memiliki himpunan simbolterminal/token berikut (ID, PLUS, MINUS, dan INT)token ID untuk karakter huruf a-z, 0-9, token INT untuk digit, token PLUS untuk Penjumlahan dan token MINUS untuk Pengurangan
Diagram SyntaxDiagram Syntax Alat bantu (tools) dalam pembuatan parser/ analisis sintaksis
Menggunakan simbol persegi panjang untuk non terminal
Lingkaran untuk simbol terminal
Misalnya
E T | T+E | T-ET
+
-
E
BNF: <Block> ::= BEGIN <statement> { SEMICOL <statement>} END
BEGIN Statement END
;
Latihan!