Teknik Kompilasi Notasi Bahasa
TATA BAHASA z
z z
Tata bahasa / Grammar dalam OTOMATA adalah kumpulan dari himpunan variabel (non-terminal), simbol-simbol awal dan terminal yang dibatasi oleh aturan-aturan produksi. Grammar digunakan untuk mendefinisikan bahasa. Aturan produksi menspesifikasikan bagaimana suatu tata bahasa mentransformasikan suatu string ke bentuk lainnya. Biasanya aturan produksi diberi simbol: z α→β z z z
z
dimana α adalah aturan produksi sebelah kiri dan β adalah aturan produksi sebelah kanan aturan produksi sebelah kir menghasilkan aturan produksi sebelah kanan.
Simbol-simbol dalam aturan produksi dapat berupa simbol terminal maupun non terminal.
TATA BAHASA (2) z z z
z z
Simbol terminal sudah tidak dapat diturunkan lagi. Simbol non-terminal dapat diturunkan lagi sampai menjadi simbol terminal. Simbol terminal biasanya ditulis dalam huruf kecil, sedangkan simbol non-terminal biasanya ditulis dalam huruf besar. Contoh simbol terminal : a,b,c,d,e, dan seterusnya. Contoh simbol non-terminal : A,B,C,D,E, dan seterusnya.
OTOMATA Untuk memodelkan hardware dari komputer diperkenalkanlah otomata / automata. Otomata adalah suatu sistem yang memiliki fungsi-fungsi komputer digital. Karaketeristik Otomata :
z
z z z z z
Menerima input. Menghasilkan output. Mempunyai penyimpanan sementara (buffer) Mampu membuat keputusan dalam mentransformasikan input ke output.
OTOMATA (2) z
Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana setiap state menyatakan informasi tentang input sebelumnya, dan dapat dianggap sebagai memori mesin. Contoh:
OTOMATA (3) Jika mesin mendapat string :
z z z z
“ada” maka diterima “adu” maka diterima “add” maka ditolak
Aturan: input string diterima jika dan hanya jika mencapai state akhir yang disimbolkan dengan lingkaran ganda. Keterangan:
z
z z z z z
Mesin diatas memiliki 6 state {q1,q2,q3,q4,q5,q6}. Mesin memiliki state awal q1 Mesin memiliki state akhir {q4,q6} Mesin memiliki himpunan input contohnya : {a,d,d}
Contoh Automata lain z
Contoh pada bahasa C: int a,b; type
q2
Q1
var
;
Q3
var
,
Q4
State awal: Q1, State akhir: Q1
Hirarki Chomsky Pada tahun 1959 Noam Chomsky menggolongkan tingkatan bahasa menjadi empat yaitu:
Hirarki Chomsky (2) Catatan : z ε → Abc adalah ilegal karena ε adalah himpunan kosong dan tidak bisa diturunkan lagi. z a → bd atau ab → Bd adalah ilegal karena ruas kiri berupa simbol terminal, padahal seharusnya ruas simbol terminal sudah tidak bisa diturunkan lagi.
Token, Lexem, Diagram z
z
Lexem adalah substring dari suatu string besar, menjadi satu bagian tertentu yang memiliki arti Token adalah suatu nama (identifier) yang sudah didefinisikan fungsionalitasnya dan merupakan kumpulan dari lexem-lexem. token
Intermediate representation
Parse tree
source
Lexical analyzer
Parser/scanner
program Get next token
Symbol Table
Rest of front end
Token & Lexem z z z
z z
Contoh non-token: White space character : space, tab, end-of-line Comments Contoh input : If distance >= rate*(end_time – start_time) then distance:= maxdist;
Output Lexem :
z z
if, distance, >= , rate, *, (, end_time, - , start_time, ), then, distance, :=, maxdist, ;
Output Token :
z z
If_op, id_var (distance,rate,end_time, start_time, maxdist), gt_op (>=), optr (*, -), assig_op (:=), block_op ( (, ) ), then_op, end_op
Scanner z
z
Token dan source code akan menjadi input bagi proses berikutnya, yaitu parser. Parser akan menerima hasil analisis lexical dalam bentuk: z
z
If_op id_var1 gt_op id_var2 optr_1 block_op1 id_var2 optr_2 id_var3 block_op2 then_op id_var3 assig_op id_var3 end_op
Scanner lebih mudah diimplementasikan pada Finite State Automata dan aturan-aturan tokennya ditulis dengan menggunakan RE.
Lexem, Operator, dan Delimiter z
Jenis-jenis Lexem: z
z
z
Identifier z Bisa berupa keyword atau nama variabel. z Keywords adalah kata-kata yang sudah didefinisikan oleh program, sedangkan variabel adalah kata-kata yang didefinisikan oleh programmer. Nilai konstanta z Adalah nilai yang bersifat konstan. Dapat berupa integer, real, boolean, karakter, ataupun string. Contoh: N := 0.333; kata := ‘malam’; selesai := TRUE; A := 1 * 2 + 3; Operator dan Delimitter z Operator : + , - , * , / , < , <= , >=, >, = dan lain-lain. z Delimiter : ( , ) , ; , dan lain-lain.
