Tata Bahasa Kelas Tata Bahasa. Konsep Bahasa (1)

Tata Bahasa Kelas Tata Bahasa Risnawaty 2350376 Jurusan Teknik Informatika Institut Teknologi Bandung

IF-ITB/RS/7 Des'03 IF6151 – Matematika Informatika

Page 1

Konsep Bahasa (1) • String(kata) adalah suatu deretan berhingga dari simbol-simbol. • Panjang string adalah jumlah simbol yang membentuk string tersebut. • String kosong dinyatakan dengan ε , didefinisikan panjangnya = 0, atau |ε| = 0 – Contoh simbol : ‘a’,’b’,’c’,’d’ – Contoh string : ‘abad’ , panjang string 4

• Alphabet adalah himpunan berhingga dari simbolsimbol IF-ITB/RS/7 Des'03 IF6151 – Matematika Informatika

Page 2

1

Konsep Bahasa (2) • Bahasa adalah himpunan string-string dari simbol-simbol untuk suatu alphabet atau rangkaian simbol-simbol yang mempunyai makna • Bahasa Kosong adalah bahasa yang tidak terdiri dari string-string, dinotasikan dengan ∅ • Bahasa kosong berbeda dengan bahasa yang terdiri dari string kosong {ε}


Page 3

Otomata (1) • Otomata adalah suatu bentuk yang memiliki fungsi-fungsi dari komputer digital • Menerima input, menghasilkan output, bisa memiliki penyimpanan sementara, dan mampu membuat keputusan dalam mentransformasikan input ke output • Sebuah bahasa formal adalah abstraksi terdiri dari himpunan simbol-simbol dan aturan-aturan yang mana simbol-simbol tersebut bisa dikombinasikan kedalam entitas yang disebut kalimat. IF-ITB/RS/7 Des'03 IF6151 – Matematika Informatika

Page 4

2

Otomata (2) • Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yang lalu,dan dapat pula dianggap sebagai memori mesin. • Input pada mesin otomata diangap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya mesin otomata membuat keputusan yang mengindikasikan apakah input itu diterima atau tidak. Page 5


Mesin Otomata Sederhana Start

q0

a

q1

d

q2 d

a

q3 u

q5

q4

• Sebuah string input diterima bila mencapai state akhir/final state yang digambarkan dengan lingkaran ganda • Pada gambar diatas, mesin mendapat string input berikut : – ada : diterima – adu : diterima – add : ditolak

• Mesin diatas memiliki 6 state {qo, q1, q2, q3, q4, q5} • State awal : q0, State akhir : {q3, q4} • Himpunan simbol input : {a,d,u} IF-ITB/RS/7 Des'03 IF6151 – Matematika Informatika

Page 6

3

Tata Bahasa (1) • Tata Bahasa (grammar) bisa didefinisikan secara formal sebagai kumpulan dari himpunan-himpunan variabel, simbolsimbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. • Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi 4 berdasarkan aturan produksinya yang disebut dengan Hierarki Chomsky (1959) IF-ITB/RS/7 Des'03 IF6151 – Matematika Informatika

Page 7

Tata Bahasa (2) • Aturan produksi menspesifikasikan bagaimana suatu tatabahasa melakukan transformasi suatu string ke bentuk lainnya • Melalui aturan produksi didefinisikansuatu bahasa yang berhubungan dengan tata bahasa tersebut • Aturan produksidinyatakan dalam bentuk : “α β” (bisa dibaca α menghasilkan β) dimana α menyatakan simbol pada ruas kiri aturan produksi, dan β menyatakan simbol pada ruas kanan aturan produksi (hasil produksi)


Page 8

4

Tata Bahasa (3) • Simbol terminal adalah simbol yang tidak dapat diturunkan lagi – Dinyatakan dengan huruf kecil , misal: ‘a’,’b’,’c’

• Simbol variabel /non terminal adalah simbol yang masih bisa diturunkan – Dinyatakan dengan huruf besar,misal:’A’,’B’,’C’

• Contoh aturan produksi : – T a , dibaca : T menghasilkan a – E T| T+E , dibaca : E menghasilkan T atau E menghasilkan T+E merupakan pemendekan dari aturan produksi : • E T • E T+E IF-ITB/RS/7 Des'03 IF6151 – Matematika Informatika

Page 9

Hierarki Chomsky (1) • Bahasa Regular (Tipe 3) – Mesin Otomata : FSA meliputi DFA & NFA – Aturan Produksi : • α adalah sebuah simbol variabel, • β maksimal memiliki sebuah simbol variabel yang bila ada terletak di posisi paling kanan

• Bahasa Bebas Konteks (Tipe 2) – Mesin Otomata : PDA – Aturan Produksi : α berupa sebuah simbol variabel IF-ITB/RS/7 Des'03 IF6151 – Matematika Informatika

Page 10

5

Hierarki Chomsky (2) • Bahasa Context Sensitive (Tipe 1) – Mesin Otomata : Linier Bounded Automata – Aturan Produksi : |α|≤ |β|

• Bahasa Unrestricted / Natural Language (Tipe 0) – Mesin Otomata : Mesin Turing – Aturan Produksi : tidak ada batasan


Page 11

Keterkaitan Bahasa

regular Bebas konteks Konteks sensitive Unrestricted


Page 12

6

Contoh Bahasa (1) • Bahasa manusia/bahasa alami termasuk ke dalamgrammar Tipe 0, yaitu unrestricted – Contoh : Abc De

• Pada Bahasa Conteks Sensitive, panjang string ruas kiri ≤ panjang string ruas kanan – Contoh : • Ab DeF • CD eF • S ε

– |s| = 1, |ε| = 0, ada perkecualian sehingga S ε dianggap memenuhi context sensitive grammar


Page 13

Contoh Bahasa (2) • Batasan context sensitive digunakan dalam proses analisis semantik pada tahap kompilasi • Bahasa bebas konteks : batasan ruas kiri haruslah tepat satu simbol variabel – Contoh : • B CDeFg • D BcDe

• Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis yang dideskripsikan secara formal dengan notasi BNF (Backus Normal Form) IF-ITB/RS/7 Des'03 IF6151 – Matematika Informatika

Page 14

7

Contoh Bahasa (2) • Bahasa regular, batasan ruas kanan maksimal memiliki sebuah simbol variabel yang terletak di paling kanan • Bahasa regular bisa memiliki simbol terminal saja dalam jumlah tidak dibatasi, tetapi bila terdapat simbol variabel,maka simbol tersebut hanya berjumlah 1 dan terletak di posisi paling kanan – Contoh : • • • •

A A A C

e efg efgH D IF-ITB/RS/7 Des'03 IF6151 – Matematika Informatika

Page 15

Aturan produksi yang perlu diperhatikan • simbol ε tidak boleh berada pada ruas kiri – contoh : ε Abd , bukan aturan produksi yang legal

• Aturan produksi sebelah kiri harus memuat simbol yang bisa diturunkan – ab bd , bukan aturan produksi yang legal karena ruas kirinya hanya memuat simbol terminal – aA bd , masih legal karena ruas kirinya masih mengandung simbol non terminal. IF-ITB/RS/7 Des'03 IF6151 – Matematika Informatika

Page 16

8

Tata Bahasa Kelas Tata Bahasa. Konsep Bahasa (1)

Recommend Documents