Representasi Bahasa Automata

REPRESENTASI BAHASA Bahasa tidak dapat dispesifikasikan dengan mendaftarkan kalimat-kalimat yang terdapat di bahasa itu bila jumlah kalimat di bahasa itu tak berhingga. Spesifikasi terhadap bahasa tidak dapat dilakukan dengan cara mendaftarkan semua kalimat atau string yang termasuk di bahasa, melainkan harus dengan cara mengemukakan syaratsyarat yang menyatakan suatu kalimat atau string termasuk string di bahasa itu. 1.

Metode Pendefinisian Bahasa

Bahasa dapat mempunyai karakteristik sebagai berikut : a. Finite (berhingga), untuk kompilasinya dapat dilakukan dengan mendaftarkan semua kalimat dan arti dari masing-masing kalimat tersebut. b. Infinite (tak berhingga), diperlukan cara agar kita dapat menspesifikasikan bahasa. Dalam hal cara menspesifikasikan bahasa ini haruslah terbatas. Diinginkan menspesifikasikan bahasa secara berhingga, walau bahasa itu tak berhingga. Terdapat dua cara menspesifikasikan bahasa dengan memenuhi syarat tersebut, yaitu : a. Grammar, yaitu sistem pembangkitan. Tiap kalimat pada bahasa dapat dibangun dengan metode-metode yang terdefinisi baik menggunakan aturan-aturan grammar. b. Recognizer atau finite automata. Finite automata menggunakan prosedur yang saat diberikan masukan string berhingga akan berhenti dan menyatakan “ya” dengan sejumlah berhingga komputasi jika string tersebut merupakan elemen bahasa. Masing-masing cara tersebut mempunyai keunggulan dan kelemahan, yaitu : a. Grammar, lebih berfokus pada pembangkitan. Grammar lebih berfungsi untuk membangkitkan string yang akan memenuhi syarat-syarat yang ditentukan bahasa. Bila kita hendak membuat pernyataan IF-THEN bahasa Pascal, maka kita harus mengikuti grammar IF-THEN di bahasa Pascal. Bilamana kita mengikuti aturan-aturan grammar pembentukan IF-THEN dengan benar maka string yang dihasilkan dipastikan termasuk string di bahasa Pascal.

1

b. Recognizer, lebih berfokus pada pengenalan. Recognizer adalah bila diberikan suatu program (string) akan menyatakan apakah string termasuk di bahasa atau tidak. Teori bahasa mulai memperoleh perhatian sejak tahun 1950. Metode parsing menjadi lebih sistematik setelah mengembangkan teori konteks free grammar lebih matang. Beberapa teknik umum untuk parsing terhadap conteks free grammar telah ditemukan diantaranya adalah : - Gagasan operator procedence dan function precedence dimulai Floyd. - Simple precedence dari Wirth dan Webeer. - Bounded Context dari Floyd dan Graham. - Mixed strategy precedence dari McKeeman, Horning dan Worthman. - Weak precendence dari Ichbiah dan Morse. 2.

Grammar

Grammar mendefinisikan bahasa secara rekursif. Grammar adalah sistem matematis untuk mendefinisikan bahasa. Bahasa yang mendefinisikan oleh grammar adalah himpunan string yang hanya berisi terminal dan dapat diturunkan mulai dari simbol tertentu yang berisi terminal dan dapat diturunkan mulai dari simbol tertentu yang disebut S atau simbol mula. Grammar mendefinisikan bahasa secara formal Grammar didefinisikan oleh 4 tupel G = (VN, VT, S, φ), dimana VN adalah himpunan simbol non-terminal, VT adalah simbol terminal, S adalah sebuah eleman dari VN yang khusus yang disebut dengan simbol awal. Dan φ adalah himpunan bagian tak kosong dari relasi (VT ∪ VN)* VN(VT ∪ VN)* ke (VT ∪ VN)*. Secara umum dapat ditulis (α,β) yang disebut aturan produksi. Grammar adalah 4 tupel G = (VN, VT, P, S) 1. VN adalah himpunan berhingga simbol non-terminal (disebut variabel atau kategori sintaks), kumpulan kelas sintaks. Elemen VN dilambangkan dengan huruf kapital. 2. VT adalah himpunan berhingga simbol terminal, disjoint dengan VN Elemen VT dilambangkan dengan huruf kecil. 2

3. P adalah himpunan bagian berhingga dari : (VN ∪ VT) * VN(VN ∪ VT) * X (VN ∪ VT)* 4. S adalah simbol terbedakan pada VN disebut simbol kalimat (mula). Vocabulary = VT ∪ VN String-string pada vocabulary dilambangkan dengan α, β,γ, … panjang string dinyatakan dengan |α|. 1.2.2 Definisi Bentuk Kalimat (Sentential Form) Penurunan Langsung Bila G = (VN, VT, S, φ) adalah grammar . Untuk σ, ψ ∈ V*, σ dikatakan penurunan langsung dari ψ, ditulis dengan ψ ⇒ σ, jika terdapat string φ1 dan φ2 sehingga ψ = φ1 α φ2 dan σ = φ1 β φ2 dan α  β merupakan produksi dari G. Produksi String Bila G = (VN, VT, S, φ) adalah sebuah grammar. String ψ menghasilkan σ (σ dapat direduksi ke ψ, atau σ adalah penurunan dari ψ), ditulis dengan ψ ⇒ σ, jika terdapat string-string φ1, φ2, … , φn) (n>0) sehingga ψ = φ0 ⇒ φ1, φ1⇒ φ2, φ2 ⇒ φ3, …, φn-1 = …φn = σ. Tanda ⇒ adalah relasi tansitif ⇒ tertutup. Bentuk Kalimat Bentuk kalimat (sentential form) adalah tiap penurunan nonterminal S unik. Bahasa L yang dihasilkan grammar G adalah kumpulan semua bentuk kalimat yang simbol-simbolnya adalah simbol terminal. Atau dilambangkan dengan L(G) = {σ | s ⇒ σ ∈ VT}, dengan demikian bahasa adalah himpunan bagian dari semua string-string terminal pada VT. Bentuk kalimat pada grammar G = (VN, VT, P, S) 1. S adalah bentuk kalimat. 2. Jika αβγ adalah bentuk kalimat dan α→δ adalah terdapat pada P, maka αβγ juga merupakan bentuk kalimat.

3

Bentuk kalimat G tanpa simbol non terminal disebut kalimat hasil G. Bahasa hasil grammar G disebut L(G) yaitu himpunan kallimat (string) dihasilkan grammar G. 3.

Recognizer (Finite Automata) Bagian recognizer, yaitu tape masukan, kendali berstatus berhingga, dan memori

Recognizer beroperasi dengan suatu barisan gerak. Di awal gerak, simbol masukan dibaca dan memori dicocokan dengan fungsi fecth bersama state saat itu dan menentukan grakan apa yang harus terjadi. Pergerakan berisi : •

Geser (shifting), menggeser head masukan satu ke kiri, kanan, atau tetap.

•

Simpan (storing), menyimpan informasi ke memori.

•

Ubah (changing), mengubah keadaan kendali.

Perilaku recognizer dapat dideskripsikan dengan konfigurasi recognizer. Konfigurasi recognizer yang mendeskripsikan : •

State kendali berhingga

•

Isi tape masukan, bersama dengan lokasi head masukan

•

Isi memori sementara

Kendali berhingga recognizer dapat berupa deterministik atau non-deterministik. Jika kendali adalah non-deterministik, maka dalam suatu konfigurasi dapat terdapat satu himpunan gerak yang mungkin berjumlah berhingga. Konfigurasi mula (initial configuration)recognizer adalah konfigurasi dimana kendali berhingga dalam satu keadaan yang dispesifikasikan, head masukan sedang men-scan (memindai) simbol terkiri tape masukan, dan memori mempunyai satu isi mula yang dispesifikasikan. Konfigurasi akhir (final configuration) adalah konfigurasi dimana kendali berhingga pada salah satu himpunan keadaan akhir yang dispesifikasikan dan head masukan sedang men-scan penanda akhir, atau telah mencapai akhir tape masukan. Sering, memori harus juga memnuhi syarat tertentu agar konfigurasi dimasukan sebagai akhir.

4

Kita nyatakan recognizer menerima (accept) string masukan jika, dimulai dari konfigurasi mula dengan w pada tape masukan, recognizer dapat membuat satu barisan gerak dan berakhir pada konfigurasi akhir. Bahasa yang didefinisikan oleh recognizer adalah himpunan string masukan yang diterimanya. Karakteristik bahasa yang diterima recognizer adalah : 1. Bahasa L adalah right linear jika dan hanya jika L didefinisikan oleh finite automaton secara deterministik (one way deterministik finite automaton). 2. Bahasa L adalah context-free jika dan hanya jika L didefinisikan oleh pushdown-automaton searah non-deterministik. 3. Bahasa L adalah context-sensitif jika dan hanya jika L didefinisikan oleh pushdown-bounded automaton linear dua arah nondeterministik. 4. Bahasa yang secara rekursif terdaftarkan jika dan hanya jika L didefinisikan oleh mesin Turing (Turing Machine). 4.

Translasi Bahasa Translasi adalah himpunan pasangan string. Kompilator mendefinisikan translasi

sebagai pasangan (program sumber, program objek). Jika kita anggap kopilator berisi tiga tahap, yaitu : •

Analisis leksik adalah translasi string-string yang merepresentasikan program sumber dipetakan menjadi string-string token.

•

Analisis sintaks memetakan string-string token menjadi string-string yang merepresentasikan pohon sintaks.

•

Pembangkit kode kemudian mengambil string-string yang dihasilkan analisis menjadi bahasa atau assembly.

a.

Translator Translator adalah sistem yang membaca program yang ditulis dalam suatu

bahasa da menterjemahkannya ke suatu program target yang ekivalen dalam bahasa lain. Program Sumber

TRANSLATOR

Program Target

Gambar 4.1 Skema Blok Translator 5

Translator untuk bahasa assembly disebut assembler, sedangkan translator untuk bahasa tingkat tinggi disebut kompilator. Saat ini terdapat ribuan kompilator mulai dari bahasa pemograman umum seperti Fortran. Pascal sampa bahasa spesialis yang digunakan pada beragam bidang aplikasi komputer. Meskipun demikian sesungguhnya tugas-tugas yang perlu dilakukan kompilator adalah serupa tak peduli bahasa sumber dan target mesin. Satu kumpulan prinsip dan teknik kompilator yang sama diperlukan dalam pengembangan translator/kompilator apapun. Terdapat dua metode untuk mendefinisikan translasi, yaitu : 1. Skema translasi (grammar). Mekanisme untuk memproduksi keluaran untuk kalimat yang dihasilkan. 2. Transducer, adalah recognizer yang dapat mengeluarkan string dengan panjang berhingga dari simbol-simbol keluaran pada tiap gerak. Semantik kadang digunakan untuk menunjukkan asosiasi dengan kalimat-kalimat keluaran dimana string keluaran mendefinisikan “arti” kalimat masukan. b.

Penerjemahan Asumsi yang dilakukan adalah penerjemahan sebagai pemetaan, maka

spesifikasi kompilator adalah sebagai himpunan pasangan string (x,y), dimana : •

x adalah program bahasa sumber.

•

y adalah program bahasa target dimana x diterjemahkan.

Kompilator mendefinisikan penerjemah yang merupakan pasangan (program sumber, program objek). Bila kompilator terdiri dari lexical analysis, syntactic analysis, dan code generation maka masing-masing fase ini mendefinisikan penerjemahan. Lexical analysis merupakan penerjamahan string yang merepresentasikan program sumber dipetakan menjadi string token. Syntatic analysis memetakan string token menjadi string yang merepresentasikan pohon parse. Code generation memetakan string yang merepresentasikan pohon parse menjadi string dalam bahasa mesin atau assembly.

6

Masalah yang dihadapi adalah upaya menghasilkan perangkat (device) yang efisien dalam melakukan penerjemahan yaitu yang bila diberikan x sebagai masukan akan menghasilkan y sebagai keluaran secara efisien. c.

Formalisasi Penerjemahan

Terdapat dua metode pendefinisian penerjemahan, yaitu : 1. skema translasi yaitu grammar dengan mekanisme untuk menghasilkan keluaran untuk masing-masing kalimat yang dibangkitkan. 2. Transducer, adalah recognizer yang mengeluarkan string dengan panjang berhiongga simbol-simbol keluaran untuk masing-masing pergerakan. Banyak translasi yang tidak dapat dispesifikasikan dengan homomorphism. Kita memerlukan spesifikasi translasi yang lebih ampuh dan formal sehingga translasi dapat dispesifikasikan dengan nyaman. Masalah menspesifikasikan penerjemahan tidak berhingga adalah serupa dengan masalah menspesifikasikan bahas dengan tidak berhingga. Terdapat beberapa pendekatan untuk menspesifikasikan translasi. d.

Sytax-directed Translasion Schemata Secara intutif, syntax directed translasion schema adalah grammar yang elemen-

elemen penerjemahannya dicantolkan ke masing-masing produksi. Kapanpun produksi digunakan di penururnan kalimat masukan, elemen translasi digunakan untuk membantu komputasikalimat pengeluaran yang diasosiasikan dengan bagian kalimat masukan yang dihasilkan oleh produksi itu. e.

Transducer

Transducer adalah recognizer yang mengeluarkan string selama dilakukan pergerakan. Keluaran dapat berupa e. •

Finite transducer adalah finite automata yang dapat mengeluarkan string simbol keluaran pada setiap pergerakan.

•

Pushdown transducer merupakan kelas translator penting. Pushdown transducer adalah pushdown automata dengan keluaran.

7

5.

BNF dan Diagram Sintaks Sintaks bahasa pemrograman dan bahasa komputer sering dispesifikasikan atau

didefinisikan menggunakan notasi BNF (Backus Naur Form) atau diagram sintaks. Baik aturan produksi, notasi BNF dan diagram sintaks disebut meta-language. Meta-language adalah bahasa untuk mendeskripsikan bahasa yang lain dalam abstraksi yang lebih tinggi. a.

BNF (Backus Naur Form) BNF (Backus Naur Form) adlah bahasa formal yang dikembangkan oleh Johan

Backus dan Peter Naur untuk mendeskripsikan grammar bahasa. BNF merupakan notasi berbasis teks murni. Notasi BNF (Backus Naur Form) untuk menghilangkan ambigu menggunakan notasi-notasi sebagai berikut: <..>

untuk non-terminal (kelas sintaks)

::=

untuk menggantikan 



memisahkan bagian kanan produksi berbeda yang berasal dari bagian kiri (non-terminal) yang sama.

b.

EBNF (Extended Backus-Naur Form)

Grammar EBNF berisi •

Simbol awal

•

Sekumpulan simbol terminal yang merupakan keyword dan penanda sintaks dari bahasa yang didefinisikan.

•

Sekumpulan simbol nonterminal yang berkorespondensi dengan kategori sintaks dan jenis-jenis kalimat bahasa pemrograman.

•

Serangkaian aturan yang disebut produksi yang menspesifikasikan cara masing-masing simbol nonterminal dapat diperluas menjadi frase berisi terminal dan nonterminal. Setiap nonterminal mempunyai satu aturan produksi yang dapat berisi alternatif-alternatif.

Perluasan EBNF antara lain menambahkan { ... } pengulangan, yaitu {z} berarti kemunculan z selama nol kali atau lebih. [ … ] elemen sintaks optional yaitu dipilih atau tidak. 8

c.

Diagram Sintaks Diagram sintaks dikembangkan Niklaus Wirth untuk mendefinisikan sintaks

Pascal. Diagram ini disebut diagram rel kereta (railroad diagram) karena bentuknya mirip jalur rel kereta api. Diagram sintaks dan EBNF sama-sama dapat mengekspresikan kelas bahasa yang sama. Diagram sintaks menyediakan cara grafis dan dua dimensi untuk komunikasi grammar sehingga mempermudah manusia dalam memahami hubungan gramatikal. EBNF digunakan untuk menulis grammar yang akan menjadi masukan bagi generator parser. Definisi diagram sintaks berelemen sama dengan EBNF yaitu : •

Simbol mula

•

Simbol terminal ditulis huruf tebal, sering berada di dalam kotak oval atau bulat. Namun untuk lebih mempermudah penulisan maka kotak oval atau bulat dapat dihilangkan, ditandai kata dengan huruf awal kapital.

•

Simbol nonterminal ditulis dengan huruf biasa.

•

Aturan produksi ditulis menggunakan anak panah (tanda alur) untuk mengindikasikan alternatif-alternatif, option-option, dan pengulangan yang tidak terdefinisi. Masing-masing aturan dimulai dengan simbol nonterminal yang ditulis di kiri dan akhir dimana anak panah bararah ke kanan.

Berikut adalah tabel dan diagram sintaks untuk aturan penulisan komentar dalam bahasa Java.

Jenis Komentar

Penggunaan

/* komentar */

Semua karakter yang berada diantara /* dan */ akan diabaikan.

// komentar

Semua karakter setelah // sampai akhir baris akan diabaikan.

/** komentar */

Serupa dengan /* */, kecuali bahwa komentar akan digunakan tool javadoc untuk menciptakan dokumentasi otomatis.

Diagram sintaks komentar :

9

/

•

•

/

NotStar NotSlash

/

NotCrOrlf

Line Terminator

Komentar // akan berlaku satu baris sampai akhir baris. Ketika lebih banyak komentar yang diperlukan. Kita dapat menandai baris diawali //. Tipe komentar (/** komentar */) digunakan kakas pembangkit dokumentasi (Java documentation generator tool), javadoc untuk menciptakan dokumentasi otomatis terhadap kode sumber. Kakas javadoc akan membangkitkan dokumentasi secara otomatis.

10

TEORI BAHASA OTOMATA DAN KOMPUTASI BESERTA PENERAPANNYA SUB JUDUL REPRESENTASI BAHASA

Di Susun Oleh : 1. Epri Nurdiana 2. Rahmatika 3. Tria Hadi K INFORMATIKA PAGI

UNIVERSITAS INDRAPRASTA PGRI JAKARTA 2007