02 TBO_Grammar

Report
KONSEP GRAMMAR
& HIRARKI CHOMSKY
Oleh : Bagus Adhi Kusuma,
Program Studi Teknik Informatika
STMIK AMIKOM Purwokerto
 anggota alfabet dinamakan simbol
terminal atau token.
 Kalimat adalah deretan hingga
simbol-simbol terminal.
 Bahasa adalah himpunan kalimatkalimat. Anggota bahasa bisa tak
hingga kalimat.
Simbol-simbol Terminal:
 huruf kecil awal alfabet
misalnya : a, b, c
 simbol operator
misalnya : +, −, dan ×
 simbol tanda baca
misalnya : (, ), dan ;
 string yang tercetak tebal
misalnya : if, then, dan else.
Simbol-simbol Non Terminal:
 huruf besar awal alfabet
misalnya : A, B, C
 Huruf S sebagai simbol awal
 string yang tercetak miring
misalnya : expr dan stmt
 Huruf besar akhir alfabet melambangkan
simbol terminal atau non terminal
misalnya : X, Y, Z.
 Huruf kecil akhir alfabet melambangkan string
yang tersusun atas simbol-simbol terminal
misalnya : x, y, z.
 Huruf yunani melambangkan string yang
tersusun atas simbol-simbol terminal atau
simbol-simbol non terminal atau campuran
keduanya
misalnya : α, β, dan γ.
 Sebuah produksi dilambangkan sebagai α → β
artinya : dalam sebuah derivasi dapat dilakukan
penggantian simbol α dengan simbol β
Simbol α dalam produksi berbentuk α → β disebut
ruas kiri produksi
sedangkan simbol β disebut ruas kanan produksi.
 Derivasi adalah proses pembentukan sebuah
kalimat atau sentensial.
Lambang: α ⇒ β
 Sentensial adalah string yang tersusun atas
simbol-simbol terminal atau simbol-simbol non
terminal atau campuran keduanya.
 Kalimat adalah string yang tersusun atas
simbol-simbol terminal.
Kalimat adalah kasus khusus dari sentensial.
 Pengertian terminal berasal dari kata
terminate (berakhir), maksudnya derivasi
berakhir jika sentensial yang dihasilkan adalah
sebuah kalimat (yang tersusun atas simbolsimbol terminal itu).
 Pengertian non terminal berasal dari kata not
terminate (belum/tidak berakhir), maksudnya
derivasi belum/tidak berakhir jika sentensial
yang dihasilkan mengandung simbol non
terminal.
ATURAN PRODUKSI
Aturan produksi dinyatakan dalam bentuk α → β
 α menghasilkan atau menurunkan β
 α symbol-symbol untuk ruas kiri, β symbolsymbol untuk ruas kanan
 Symbol-symbol dapat berupa terminal dan non
terminal dimana non terminal dapat diturunkan
menjadi symbol yang lainnya
1
ATURAN PRODUKSI
 Umumnya symbol terminal disymbolkan
dengan huruf kecil (a,b,c, dsb), sedangkan
untuk symbol non terminal disymbolkan
dengan huruf besar (A,B,C, dsb)
Contoh :
T→a
E→T│T+E
T menghasilkan a
E menghasilkan T
atau
E menghasilkan T + E
2
Grammar & Klasifikasi Chomsky
Grammar G
didefinisikan sebagai pasangan 4 tuple :
VT, V N, S, dan Q
dituliskan sebagai G(VT, VN, S, dan Q)
VT : himpunan simbol-simbol terminal
(atau himpunan token -token, atau alfabet)
VN : himpunan simbol-simbol non terminal
S ∈ VN : simbol awal (atau simbol start)
Q : himpunan produksi
Hirarki Chomsky
Tipe sebuah grammar (atau bahasa) ditentukan
dengan aturan sebagai berikut :
A language is said to be type-i
(i = 0, 1, 2, 3) language if it
can be specified by a type-i
grammar but can’t be
specified any type-(i+1)
grammar.
1. Grammar tipe ke-0 :
Unrestricted Grammar (UG)
α, β ∈ (VT | VN)*, |α|> 0
• Ciri :
Tidak ada batasan pada aturan produksi
• Contoh :
Abc → De
2. Grammar tipe ke-1 :
Context Sensitive Grammar (CSG)
α, β ∈ (VT | VN)*, 0 < |α| ≤ |β|
• Ciri :
Panjang string ruas kiri harus < (lebih kecil)
atau = (sama dengan) ruas kanan
• Contoh :
Ab → DeF
CD → eF
3. Grammar tipe ke-2 :
Context Free Grammar (CFG)
α ∈ VN, β ∈ (VT|VN)*
• Ciri :
Ruas kiri haruslah tepat satu symbol variabel,
yaitu simbol non terminal
• Contoh :
B → CDeFg
D → BcDe
4. Grammar tipe ke-3 :
Regular Grammar (RG)
α ∈ VN, β ∈ {VT, VT VN}
atau α ∈ VN, β ∈ {VT, VN VT}
• Ciri :
Ruas kiri hanya memiliki maksimal satu
symbol non terminal
• Contoh :
A→e
A → gH
C→D
Contoh Analisa
Penentuan Type Grammar
1. Grammar G1 dengan
Q1 = {S → aB, B → bB, B → b}.
• Ruas kiri semua produksinya terdiri dari
sebuah VN maka G1 kemungkinan tipe CFG
atau RG.
• karena semua ruas kanannya terdiri dari
sebuah VT atau string V T VN maka G1
adalah RG.
Contoh Analisa
Penentuan Type Grammar
2. Grammar G2 dengan
Q 2 = {S → Ba, B → Bb, B → b}
• Ruas kiri semua produksinya terdiri dari
sebuah VN maka G2 kemungkinan tipe CFG
atau RG
•
karena semua ruas kanannya terdiri dari
sebuah VT atau string VN VT maka G2
adalah RG.
Contoh Analisa
Penentuan Type Grammar
3. Grammar G3 dengan
Q3 = {S → Ba, B → bB, B → b}
• Ruas kiri semua produksinya terdiri dari
sebuah VN maka G3 kemungkinan tipe CFG
atau RG
•
karena ruas kanannya mengandung string
VT VN (yaitu bB) dan juga string VN VT (Ba)
maka G3 bukan CFG, dengan kata lain G3
adalah RG.
Contoh Analisa
Penentuan Type Grammar
4. Grammar G4 dengan
Q 4 = {S → aAb, B → aB}.
• Ruas kiri semua produksinya terdiri dari
sebuah VN maka G4 kemungkinan tipe CFG
atau RG.
• karena ruas kanannya mengandung string
yang panjangnya lebih dari 2 (yaitu aAb)
maka G4 bukan RG, dengan kata lain G4
adalah CFG.
Contoh Analisa
Penentuan Type Grammar
5. Grammar G5 dengan
Q5 = {S → aA, S → aB, aAb → aBCb}.
•
Ruas kirinya mengandung string yang
panjangnya lebih dari 1 (yaitu aAb) maka G5
kemungkinan tipe CSG atau UG
•
karena semua ruas kirinya lebih pendek atau
sama dengan ruas kananya maka G5 adalah
CSG
Contoh Analisa
Penentuan Type Grammar
6. Grammar G6 dengan
Q6 = {aS → ab, SAc → bc}
•
Ruas kirinya mengandung string yang
panjangnya lebih dari 1 maka G6
kemungkinan tipe CSG atau UG
•
karena terdapat ruas kirinya yang lebih
panjang daripada ruas kananya (yaitu SAc)
maka G6 adalah UG.
Derivasi Kalimat
dan
Penentuan Bahasa
Tentukan Derivasi bahasa dari
masing-masing grammar berikut:
1.
Grammar G1 dengan
Q1 = {1. S → aAa, 2. A → aAa, 3. A → b}
2. Grammar G2 dengan
Q2 = {1. S → aS, 2. S → aB, 3. B → bC, 4. C → aC, 5. C → a}
Tugas Individu
1.
Grammar G2 dengan
Q2 = {1. S → aS, 2. S → aB, 3. B → bC, 4. C → aC, 5. C → a}
Email: [email protected]
Paling lambat hari minggu jam 24.00 tgl 13
Tugas Individu
1. Diketahui grammar G(VT , VN , S, Q) dimana :
VT = {a, b}
VN = {S, A, B}
S ∈ VN
Q = {1. S → aA; 2. A → aBb; 3. B → bS; }
a. G termasuk grammar tipe yg mn? Berikan
alasannya.
b. Buatlah 5 kalimat dengan panjang berbeda
yang dapat diturunkan dari grammar G.
c. Tentukan pola kalimat dari grammar G
Email: [email protected]
Paling lambat hari senin jam 24.00 tgl 14

similar documents