TEKNIK KOMPILASI Konsep & Notasi Bahasa Sekolah Manajemen Informatika dan Komputer (STMIK) Palangkaraya 2012
Konsep dan Notasi bahasa
Teknik Kompilasi merupakan kelanjutan dari konsepkonsep yang telah kita pelajari dalam teori bahasa dan otomata Thn 56-59 Noam Chomsky melakukan penggolongan tingkatan dalam bahasa, yaitu menjadi 4 class Penggolongan tingkatan itu disebut dengan hirarki Chomsky 1959 Backus memperkenalkan notasi formal baru untuk sintaks bahasa yang lebih spesifik Peter Nour (1960) merevisi metode dari sintaks. Sekarang dikenal dengan BNF (Backus Nour Form)
Konsep dan Notasi bahasa
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
Konsep dan Notasi bahasa
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 simbolsimbol. 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.
Konsep dan Notasi bahasa Penggolongan Chomsky Bahasa Mesin Automata
Aturan Produksi
Tipe 3 Atau Regular
Finite state automata (FSA) meliputi; deterministic Finite Automata (DFA) & Non Deterministic Finite Automata (NFA)
adalah sebuah simbol
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
variabel maksimal memiliki sebuah simbol variabel yang bila ada terletak diposisi paling kanan
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 bisa menghasilkan sejumlah string. Himpunan string tersebut adalah bahasa yang didefinisikan oleh tata bahasa tersebut.
Aturan Produksi Contoh aturan produksi :
Ta dibaca : “T menghasilkan a” E T | T+E dibaca : “E menghasilkanT atau E menghasilkanT + E” Merupakan pemendekan dari : E T E T+E Simbol ‘|’ menyatakan ‘atau’
Aturan 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 DeF CD eF Sɛ Tipe 2 / Context free grammar: Ruas kiri haruslah tepat satu simbol variable B CDeFg D BcDe Tipe 3 / Regular: Ruas kiri hanya 1 simbol variabel, Ruas kanan hanya memiliki maksimal 1 simbol non terminal / variabel dan diletakkan paling kanan sendiri Ae A efg A efgH CD
Aturan produksi yang tidak legal !!! Simbol ɛ tidak boleh berada pada ruas kiri
misal ɛ Abd ɛ merupakan string kosong Aturan produksi yang ruas kirinya hanya memuat simbol
terminal saja misal : 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 proses
analisis semantik pada tahapan kompilasi Bahasa context free menjadi dasar dalam pembentukan suatu
parser / proses analisis sintaksis, dideskripsikan dengan notasi BNF (Backus Normal Form)
Hirarki Chomsky
Unrestricted Context Sensitive Context free Regular Regular
Notasi 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 Ta Notasi BNF-nya adalah <E> ::=
| + <E> | - <E> ::= a
Contoh Tata Bahasa Sederhana
<program>
::= BEGIN <statement-list> END
<statement-list> <statement> <expression>
::= <statement> | <statement>; <statement-list> ::= := <expression> ::= | <expression> ::= | ::= |
::= A|B| ….| Z ::= + | - | = ::= ^ | * | / ::= |
::= . ::= | < digit> ::= | ::= 0|1|….|9
Contoh BEGIN A := 1; B := A + 2 END
Latihan ! TBO, Firrar Utdirartatmo hal 13-15…
Diagram State
Digunakan untuk mendapatkan token, mempermudah melakukan analisis lexical
Token adalah simbol terminal dari teori bahasa dan automata
Contoh : suatu tata bahasa memiliki himpunan simbol terminal/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
PLUS
huruf
+
Huruf, Digit
S MINUS
ID
Digit
-
INT Blank
Digit
Diagram 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-E
E
T
+ -
BNF: ::= BEGIN <statement> { SEMICOL <statement>} END
BEGIN
Statement
;
END
Latihan!