Download - Tekom Kelompok Bab 3
![Page 1: Tekom Kelompok Bab 3](https://reader036.vdokumen.com/reader036/viewer/2022082320/5571fb74497959916994ee61/html5/thumbnails/1.jpg)
KELOMPOK 3 DEPOK
TEKNIK KOMPILASI
Nama Anggota :
DAFTAR ANGGOTA :
NAMA NIM
Husni D.J 0844190060
Eko Kuncoro 0844190033
Lilik Wahyudi 0844190066
![Page 2: Tekom Kelompok Bab 3](https://reader036.vdokumen.com/reader036/viewer/2022082320/5571fb74497959916994ee61/html5/thumbnails/2.jpg)
BAB 3
Konsep dan Notasi Bahasa
3.1 HIRARKY CHOMSKY
Pada bagian ini akan dibahas beberapa konsep pada Teori Bahasa yang akan kita
perlukan nanti. Teknik Kompilasi sebenarnya bias dianggap sebagai kelanjutan dari
konsep – konsep yang dipelajari dalam Teori Bahasa, dan dalam implementasinya
mengambil sebagian dari konsep – kosep tersebut.
Tata Bahasa (grammar) bisa didefinisikan secara formal sebagai kumpulan dari
himpunan – himpunan variable , symbol – symbol terminal. Symbol awal, yang dibatasi
oleh aturan – aturan produksi. Pada tahun 1959 seorang ahlo yang bernama Noam
Chomsky melakukan penggolongan tingkatan bahasa menjadi empat, yang disebut
Hirarki Chomsky. Penggolongan tersebut bisa dilihat pada table berikut.
Bahasa Mesin Otomata Batasan Aturan Produksi
Regular / Tipe 3 Finite State Automata
(FSA) meliputi
Deterministic Finite
Automata (DFA) & Non
deterministic Finite
Automata (NFA)
α adalah sebuah symbol
variable
β maksimal memiliki
sebuah symbol variable
yang bila ada terletak di
posisi paling kanan
Bebas Kontes / Context free
Tipe 2
Push Down Automata
(PDA)
α adalah sebuah symbol
variable
Context Sensitive / Tipe 1 Linier Bounded Automata | α | ≤ | β |
Unrestricted/ Phase
Structure / Natural
Language
Mesin Turing Tidak ada batasan
![Page 3: Tekom Kelompok Bab 3](https://reader036.vdokumen.com/reader036/viewer/2022082320/5571fb74497959916994ee61/html5/thumbnails/3.jpg)
Bisa kita lihat penggolongan di atas berdasarkan pembatasan yang dilakukan pada
aturan produksinya. Aturan produksi merupakan pusat dari tata bahsa, yang
menspesifikasikan bagaimana suatu tata bahasa melakukan transformasi suatu string ke
bentuk lainnya, dan melalui aturan produksi tersebut didefinisikan suatu bahasa yang
berhubungan dengan tata bahasa tersebut. Disini semua tata bahasa dinyatakan dalam
bentuk “ a b “ (bisa dibaca: a menghasilkan b, atau dibaca a menurunkan b), dimana a
menyatakan symbol – symbol oada ruas kiri aturan produksi (sebelah kiri tanda “” )
dan b menyatakan symbol – symbol pada ruas kanan aturan produksi (sebelah kanan
tanda “”, dan bisa disebut juga sebagai hasil produksi). Simbol – symbol tersebut bisa
berupa symbol terminal atau symbol non terminal / variable. Symbol variable / non
terminal adalah symbol yang masih bisa diturunkan, symbol terminal sudah tidak bisa
diturunkan lagi. Symbol terminal biasanya ( dan pada buku ini) dinyatakan dengan huruf
kecil. misal ‘a’,’b’,’c’. symbol non terminal / variable biasanya dinyatakan dengan huruf
besar misal ‘A’, ‘B’, ‘C’.
Dengan menerapkan aturan produksi suatu tata bahasa bisa menghasilkan
sejumlah string. Himpunan semua string tersebut adalah bahasa yang didefinisikan oleh
tata bahasa tersebut.
Contoh aturan produksi :
T a
Bisa dibaca : “T menghasilkan a”
E T | T+ E
Bisa dibaca : “E menghasilkan T atau E menghasilkan T + E “
Simbol ‘|’ menyatakan ‘atau’, biasa digunakan untuk mempersingkat penulisan
aturan produksi yang mempunyai ruas kiri yang sama. Pada contoh di atas :
![Page 4: Tekom Kelompok Bab 3](https://reader036.vdokumen.com/reader036/viewer/2022082320/5571fb74497959916994ee61/html5/thumbnails/4.jpg)
E T | T+ E
Merupakan pemendekan dari aturan produksi :
E T
E T + E
Bahasa manusia / bahasa alami termasuk kedalam grammar (tata bahasa). Tipe 0 /
unrestricted, dimana tidak ada batasan pada aturan produksinya . misalkan saja :
Abc De
Pada bahasa Context Sensitive, panjang string pada ruas kiri ≤ panjang ruas kanan (| α |
≤ | β | ) . Contoh aturan produksi yang context sensitive :
Ab Def
CD eF
Perhatikan aturan produksi seperti :
S ε
Kita ketahui |S| = 1, sedang | ε | = 0, menurut aturan context sensitive aturan
produksiitu tidak diperkenankan, tetapi di sini kita buat suatu pengecualian, sehingga
S ε dianggap memenuhi context sensitive grammar.
Batasan context sensitive biasanya turut digunakan dalam proses analisis semantic
pada tahapan kompilasi.
Pada bahasan bebasa konteks, batasannya bertambah lagi dengan ruas kiri
haruslah tepat satu symbol variable. Misalnya :
B CDeFg
D BcDe
![Page 5: Tekom Kelompok Bab 3](https://reader036.vdokumen.com/reader036/viewer/2022082320/5571fb74497959916994ee61/html5/thumbnails/5.jpg)
Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser / proses
analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam
tata bahasa bebas konteks ( context free grammar). Yang dideskripsikan secara formal
dengan notasi BNF (Backus Naur Form atau Backus Normal Form).
Pada bahasa regulear, batasannya bertambah dengan ruas kanan maksimal
memiliki sebuah symbol variable yang terletak di paling kanan Artinya, bisa memiliki
symbol terminal saja dalam jumlah tidak dibatasi, tetapi bila terdapat symbol variable.
Maka symbol variable tersebut hanya berjumlah 1 (satu) dan terletak di posisi paling
kanan Misalnya
A e
A efg
A efgH
C D
Bisa kita lihat batasannya makin bertambah dari tipe 0 ke tipe 3. Berdasarkan
keterkaitannya antar tipe bahasa tersebut, bisa pula dilihat secara sederhana pada gambar
3.1
Gambar 3.1 Keterkaitan bahasa pada Hirarki Chomsky
![Page 6: Tekom Kelompok Bab 3](https://reader036.vdokumen.com/reader036/viewer/2022082320/5571fb74497959916994ee61/html5/thumbnails/6.jpg)
*Perhatikan :
Aturan Produksi seperti
ε Abd
bukan aturan produksi yang legal, karena symbol ε tidak boleh berada pada ruas kiri
Aturan produksi yang ruas kirinya hanya memuat symbol terminal saja seperti
a bd
ab bd
bukan aturan produksi legal (untuk unrestricted grammar sekalipun), karena ruas
kiri haris juga memuat symbol yang bisa diturunkan, sementara contoh di atas ruas kiri
hanya terdiri dari symbol terminal saja padahal sesuai definisinya symbol terminal sudah
tidak bisa diturunkan lagi, berbeda dengan aturan produksi seperti L
aA bd
3.2 DIAGRAM KEADAAN
Diagram keadaan ( state Transition Diagram ) digunakan untuk mendapatkan
token (token adalah symbol terminal pada teori bahasa), yaitu melakukan analisis
leksikal terhadapa program sumber. Misalkan suatu bahasa memiliki himpunan symbol
terminal / token (berikut, (t_PLUS, t_MIN, t_ID, t_INT). Token t_ID (identifier) bisa
berupa nama atau keyword (kata kunci yang sudah didefinisikan oleh suatu bahasa).
Misal terdapat statement :
VAR jumlah : integer
Maka VAR dan integer adalah keyoword , jumlah adalah sebuah nama yang
dideklarasikan sendiri oleh pemrogram. Token t_ID harus diawali dengan karakter huruf
(A-Z, a-z), dan bisa diikuti digit (0-9) atau huruf. Token t_INT harus diawali dengan digit
dan bisa diikuti dengan digit. Blank merupakan bagian program sumber yang diabaikan
(dilewati) saja, misalkan spasi kosong.
![Page 7: Tekom Kelompok Bab 3](https://reader036.vdokumen.com/reader036/viewer/2022082320/5571fb74497959916994ee61/html5/thumbnails/7.jpg)
Gambar 3.2 Diagram keadaan untuk bahasa di atas
Bisa dilihat diagram keadaan memiliki kemiripan dengan finite state automata. Dengan
menggunakan Diagram keadaan akan mempermudah kita dalam melakukan analisis
leksikal.
3.3 NOTASI BNF
Aturan – aturan produksi dapat dinyatakan dalam bentuk BNF (Backus Naur
Form / Backus Norm Form). Notasi BNF telah banyak dipakai untuk melakukan definisi
formal bahasa pemograman. Beberapa symbol yang dipakan dalam notasi BNF
::= Identik dengan symbol pada aturan produksi
| Idem dengan symbol serupa pada aturan produksi
< > Mengapit symbol variable / non terminal
{ } Pengulangan 0 sampai n kali
![Page 8: Tekom Kelompok Bab 3](https://reader036.vdokumen.com/reader036/viewer/2022082320/5571fb74497959916994ee61/html5/thumbnails/8.jpg)
T T
*
/
F
Contoh :
Terdapat aturan produksi :
E T | T + E | T- E , T a
Notasi BNF :
E ::= <T> | <T> + <E> | <T> - <E>, T ::= a
3.3 DIAGRAM SINTAKS
Diagram sintaks merupakan alat Bantu dalam pembentukan parser / analisis
sintaksis. Notasi yang terdapat pada diagram sintaks :
Empat persegi panjang melambangkan symbol variable / non terminal
Bulatan melambangkan symbol terminal
Misal terdapat aturan produksi :
T F*T | F/T |F
Diagram sintaksnya dapat dilihat pada gambar 3.3
![Page 9: Tekom Kelompok Bab 3](https://reader036.vdokumen.com/reader036/viewer/2022082320/5571fb74497959916994ee61/html5/thumbnails/9.jpg)
S
S
S
S
S
S
TAMBAHAN CATATAN DARI BU DIAN
Contoh Diagram Keadaan
Program Hitung Luas_segitiga;Var A,T,Luas : Integer;Begin
Readln (A);Readln (T);Luas := (A*T)*0.5;Write (Luas);
End
Gambar diagram keadaan :
Keyword (Program var, int, begin, readln, end, write)
A, T, luas huruf Huruf (A,T,luas)
Int digit (A,T,luas)
* operan (*) ;
:= Titik dua sama dengan
Gambar diagram Sintaks :
- Simbol VN (Variabel non Terminal)
- Simbol VT (Variabel Terminal)
S
t_id
t_int
t_mul
t_titik dua sama dgn
T_titik
koma dua
sama dgn
![Page 10: Tekom Kelompok Bab 3](https://reader036.vdokumen.com/reader036/viewer/2022082320/5571fb74497959916994ee61/html5/thumbnails/10.jpg)
Simbol Terminal (VT) Simbol Non Terminal (VN)1) Huruf Kecil 1) Huruf besar 2) Tanda baca 2) huruf s3) Operator 3) Ekspresi / statement4) Keyword
Diagram sintaks merupakan alat bantu dalam pembentukan parser / analisis sintaks. Notasi yang terdapat dalam diagram sintaks :
• Empat persegi panjang melambangkan simbol variabel / non terminal.
• Bulatan melambangkan simbol terminal
Contoh : Terdapat aturan produksi sbb :
T --> F * T \ F / T / FDiagram Syntax :
Contoh :
Begin
If
Ekspresi then
Statement 1;
Else
Statement 2;
End
T T
*
/
F
![Page 11: Tekom Kelompok Bab 3](https://reader036.vdokumen.com/reader036/viewer/2022082320/5571fb74497959916994ee61/html5/thumbnails/11.jpg)
Diagram Syntax :
Notasi BNF :
Aturan-aturan produksi dapat dinyatakan dalam bentuk BNF (Backus naur Form)
Beberapa simbol yang digunakan dalam notasi BNF
;:= Identik dengan simbol pada aturan produksi
| Menyatakan “atau”
< > Mengapit simbol variabel
{ } Pengulangan 0 sampai n kali
Contoh, terdapat aturan produksi sebagai berikut :
E T | T+E | T-E, T a
Notasi BNF :
E ::= <T> | <T> + <E> | <T> - <E>, T ::= a
EkspresiBegin
else
end
Statement
Statement
Then
if
;
:.