TEKNIK KOMPILASI Konsep & Notasi Bahasa

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)


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


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 :

Ta 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 Ae A  efg A  efgH CD

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 Ta 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!

TEKNIK KOMPILASI Konsep & Notasi Bahasa

Recommend Documents