PERTEMUAN
2
TAHAPAN KOMPILASI
Compiler
adalah suatu program yang dapat membaca suatu Bahasa pemrograman (source
language) dan kemudian diterjemahkan ke dalam Bahasa pemrograman lain (target
language).
Phase Analysis :
- Lexical
Analyzer
Pada
Compiler, lexical analyzer biasa disebut juga sebagai scanner. Lexical analyzer
adalah tahapan pertama yang dilakukan pada compiler. Proses yang dilakukan pada
tahapan ini adalah membaca program sumber karakter per karakter. Satu atau
lebih (deretan) karakter karakter ini dikelompokkan menjadi suatu kesatuan
mengikuti pola kesatuan kelompok karakter (token) yang ditentukan dalam bahasa
sumber dan disimpan dalam table simbol, sedangkan karakter yang tidak mengikuti
pola akan dilaporkan sebagai token tak dikenal.
- Syntax
Analyzer
Setelah
tahapan lexical analyzer selesai berikutnya adalah tahapan syntax analyzer atau
biasa juga disebut Parser. Pada tahapan ini token yang didapatkan dari hasil
lexical analysis diurutkan atau disusun
lalu dikelompokkan ke dalam suatu struktur tertentu secara spesifik.
-
Semantic Analyzer
Setelah
tahapan syntax analyzer selesai berikutnya adalah tahapan semantic analyzer.
Tahapan semantic analyzer merupakan tahapan yang penting karena merupakan pusar
dari tahapan kompilasi, dan juga merupakan jembatan antara fase analysis dan
fase synthesis pada compiler. Pada tahapan ini program sumber akan diperiksa
untuk mencari kemungkinan kesalahan semantic dengan cara memanfaatkan struktur
hirarkikal yang dihasil dari tahapan syntax analyzer. Pada tahapan ini akan
dihasilkan suatu kode yang executable pada kompilasi yang sederhana lalu
dimanipulasi dengan berbagai optimization dari translator sampai nanti
benar-benar executable dihasilkan.
Phase Synthesis :
- Intermediate
Code Generator
Intermediate
code generator merupakan tahapan awal dari phase synthesis. Proses yang
dilakukan pada tahapan ini me-generate atau membangkitkan suatu code
berdasarkan parsing tree, lalu selanjutnya diterjemahkan ke dalam bentuk three
address code, quadruples atau triples.
- Code
Optimizer
Setelah
melakukan tahapan intermediate code generator berikutnya yang dilakukan adalah
tahapan code optimizer. Adapun yang dilakukan pada tahapan ini adalah
mengoptimisasi code sehingga menjadi code yang executable. Tahapan ini
dilakukan untuk mempercepat waktu eksekusi dari suatu program dengan cara
menghilangkan redudansi pada code.
- Code
Generator
Tahapan
code generator ini merupakan tahapan terakhir pada proses kompilasi. Pada
tahapan ini akan dilakukan penentuan register untuk masing-masing variable lalu
instruksi-instruksi dalam bentuk antara akan diterjemahkan ke dalam Bahasa
mesin, dan akhirnya akan menghasilkan relocatable machine code atau assembly
code.
- Symbol
Table Manager
Symbol Table adalah sebuah
struktur data dengan record-record untuk setiap identifier dengan field-field
untuk setiap atribut dari identifier tersebut.
- Error
Handler
Error handler merupakan bagian
dari compiler untuk menangani dan melaporkan jika ditemukan suatu error.
PERTEMUAN
3
Translator
Melakukan pengubahan
source code/program sumber ke dalam target code/object code. Source code
ditulis dalam sumber sedangkan object code bisa dalam bahasa pemrograman lain
atau bahasa mesin pada suatu komputer.
Macam – macam Translator:
1. Assembler
Source code
adalah bahasa assembly, object code adalah bahasa mesin contoh : Turbo
Assembler dan Macro Assembler
2. Kompilator ( Compiler)
Source code adalah
bahasa tingkat tinggi, object code adalah bahasa mesin atau bahasa assembly.
Source code dan data diproses pada waktu yang berbeda. Contoh ; Turbo Pascal.
Compile time adalah saat pengubahan dari source code ke object code sedangkan
Run Time adalah saat eksekusi object code.
3. Interpreter
Interpreter
tidak membangkitkan object code, hasil translasi hanya dalam bentuk internal.
Contoh: BASICA/GW-BASIC,LIPS,SMALLTALK.
Source code dan data diproses pada saat yang sama.
Model Kompilator
Kompilator umumnya mempunyai dua tugas pokok :
1. Fungsi Analisis, biasa disebut Front-end à
melakukan dekomposisi program sumber menjadi bagian-bagian dasarnya.
2. Fungsi Sintesis, biasa disebut Back-end
àmelakukan pembangkitan dan optimasi program objek.
-
Scanner : Memecah program sumber
menjadi besaran Leksik/Token
-
Parser : memeriksa kebenaran
dan urutan kemunculan Token
-
Analisis Semantik : melakukan analisis semantik,biasanya
dalam realisasi kan
digabungkan dengan
Intermediate code generator (bagian
yang berfungsi
membangkitkan kode antara
-
Code Generator : membangkitkan kode objek
-
Code Optimizer : memperkecil hasil dan mempercepat
proses
-
Tabel Simbol : menyimpan semua informasi yang
berhubungan dengan
proses kompilasi
Mutu Kompilator
Mutu dari suatu kompilator tergantung dari
beberapa faktor :
1. Kecepatan dan waktu
proses
Tergantung dari :
-
Penulisan Algoritma
Kompilator
-
Kompilator
pengkompilasi
2. Mutu
program objek
mutu suatu program objek
ditentukan oleh ukuran dan kecepatan eksekusi dari program objek.
3.
Integrated Environment
Merupakan fasilitas terintegrasi yang dimiliki
oleh kompilator.
Pembuatan Kompilator
Dapat dilakukan dengan cara :
1.
Mempergunakan bahasa
mesin
2.
Mempergunakan bahasa
tingkat tinggi
3.
Mempergunakan bahasa
tingkat tinggi lain pada mesin yang sama
4.
Mempergunakan bahasa
tingkat tinggi yg sama pada mesin yang berbeda.
5.
Bootstrap ( gagasan
dari Nirklaus Wirth : membangun suatu yang besar dengan terlebih dahulu membuat
bagian intinya).
PERTEMUAN
4
Analisis Leksikal merupakan
antarmuka antara kode program sumber dan analisis sintaktik (parser). Scanner
melakukan pemeriksaan karakter perkarakter.
Rangkuman Analisis
Leksikal / Scanner.
- Analisis Leksikal
merupakan antarmuka antara kode program sumber dan analisis sintaktik (parser).
Scanner melakukan pemeriksaan karakter per karakter pada teks masukan, memecah
sumber program menjadi bagian-bagian disebut Token.
Analisis Leksikal
mengerjakan pengelompokkan urutan-urutan karakter ke dalam komponen pokok:
identifier, delimeter, simbol-simbol operator, angka, keyword, noise word,
blank, komentar, dan seterusnya menghasilkan suatu Token Leksikal yang akan
digunakan pada Analisis Sintaktik.
Rangkuman Analisis Leksikal / Scanner
Model dasar buat membentuk sesuatu Analisis Leksikal
adalah Finite- State Automata, 2 aspek berarti pembuatan Analisis Leksikal
merupakan:
-
Memastikan token- token bahasa.
-
Mengidentifikasi token- token bahasa dari
program sumber.
Token-
token dihasilkan dengan metode memisahkan program sumber tersebut dilewatkan ke
parser. Analisis Leksikal wajib mengirim token ke parser. Buat mengirim token,
scanner wajib mengisolasi barisan kepribadian pada bacaan sumber yang ialah 1
token valid.
Scanner
pula menghilangkan data semacam pendapat, blank, batas- batas baris serta lain-
lain yang tidak berarti( tidak memiliki makna) untuk parsing serta Code
Generator. Scanner pula wajib bisa mengenali token secara lengkap serta
membedakan keyword serta identifier. Buat itu scanner membutuhkan tabel simbol.
Scanner memasukkan identifier ke tabel simbol, memasukkan konstanta literal
serta numerik ke tabel simbol sendiri sehabis konversi jadi wujud internal.
Analisis
Leksikal ialah komponen kompilasi independen yang berbicara
dengan parser melalui antarmuka yang terdefinisi bagus serta simpel sehingga
pemeliharaan analisis leksikal jadi lebih gampang dimana perubahan- perubahan
terhadap analisis leksikal tidak berakibat pada pengubahan kompilator secara
totalitas. Supaya bisa mendapatkan fitur ini, hingga antarmuka wajib tidak
berganti. Mayoritas kode yang menyusun analisis leksikal merupakan sama buat
segala kompilator, tidak hirau Bahasa.
PERTEMUAN
5
Definisi DFA dan NFA
Finite
Automata adalah mesin automata dari suatu
Bahasa regular. Finite Automata memiliki jumlah state yang banyaknya berhingga
dan dapat berpindah-pindah dari suate state ke state yang lainnya. Finite
Automata dibagi menjadi Deterministic Finite Automata (DFA) dan Non
Deterministic Finite Automata (NFA).
Deterministic
Finite Automaton atau Deterministic Finite Acceptor yang biasa disingkat DFA merupakan teori bahasa komputasi
dan cabang dari ilmu komputer teoritis, dimana mesin keadaan terbatas yang
menerima atau menolak string dari simbol dan hanya menghasilkan perhitungan
unik dari otomata untuk setiap string yang di masukan atau lebih ringkasnya FA
di dalam menerima input mempuyai tepat satu busur keluar. Pada contoh dibawah
ini Deterministic Finite Automata, jika suatu state diberi inputan maka state
tersebut akan selalu tepat menuju satu state.
Nondeterministic
Finite Automata atau disingkat NFA adalah salah satu bagian dari otomata
berhingga atau Finite State Automata (FSA). Pada Nondeterministic Finite
Automata (NFA) dimungkinkan satu simbol menimbulkan transisi ke lebih dari satu
kondisi dan memberikan beberapa kemungkinan gerakan sehingga keluarannya tidak
dapat dipastikan atau lebih singkatnya FA didalam menerima input mempuyai lebih
dari satu busur keluar atau tidak punya busur keluar. Pada Non Deterministic
Finite Automata, jika suatu state diberi inputan maka mungkin saja bisa menuju
ke beberapa state berikutnya. Dapat dilihat di S0, jika diberi inputan b bisa
menuju ke S1 dan S2.
Konversi
DFA ke NFA
Dapat dilihat dari gambar di atas ada suatu state
yang diberi inputan menuju ke beberapa state, yaitu S0 yang diberi inputan b
bisa menuju ke S0 dan S1 kemudian dikonversi menjadi DFA, dengan cara membuat
state baru berupa gabungan dari S0 dan S1. Lalu untuk state {S0,S1} jika diberi
inputan a maka hasilnya adalah gabungan dari hasil S0 dan S1 yang diberi
inputan a yaitu {S0,S1}. Berikutnya untuk state {S0,S1} jika diberi inputan b
maka hasilnya adalah gabungan dari hasil S0 dan S1 yang diberi inputan b yaitu
{S0,S1}.
PERTEMUAN
6
Contoh 5 soal beserta jawaban "Grammar
Chomsky"
1. Sebutkan
Langkah-langkah pembentukan bentuk normal Chomsky secara umum ?
Biarkan aturan produksi yang sudah dalam bentuk
normal Chomsky Lakukan penggantian aturan produksi yang ruas kanannya memuat
simbol terminal dan panjang ruas kanan > 1Lakukan penggantian aturan
produksi yang ruas kanannya memuat > 2 simbol variabel
Penggantian-penggantian tersebut bisa dilakukan berkali-kali sampai akhirnya
semua aturan produksi dalam bentuk normal Chomsky Selama dilakukan penggantian,
kemungkinan kita akan memperoleh aturan-aturan produksi baru, dan juga
memunculkan variabel baru
2.
Aturan produksi yang sudah dalam bentuk normal Chomsky?
A → a
B
→ b
Dilakukan
penggantian aturan produksi yang belum bentuk normal Chomsky (‘=>’ bisa
dibaca berubah menjadi):
S
→ bA => S → P1A
S
→ aB => S → P2B
A
→ bAA =>A → P1AA => A → P1P3
A
→ aS => A → P2S
B
→ aBB => B → P2BB => B → P2P4
B
→ bS => B → P1S
Terbentuk
aturan produksi dan simbol variabel baru:
P1
→ b
P2
→ a
P3
→ AA
P4
→ BB
Hasil
akhir aturan produksi dalam bentuk normal Chomsky :
A
→ a
B
→ b
S
→ P1A
S
→ P2B
A
→ P1P3
A
→ P2S
B
→ P2P4
B
→ P1S
P1
→ b
P2
→ a
P3
→ AA
P4
→ BB
P1
= P, P2 =Q, P3 =R, P4 =T
sehingga
aturan produksinya menjadi:
S
→ PA
S
→ QB
A
→ PR
A
→ QS
A
→ a
B
→ QT
B
→ PS
B
→ b
P
→ b
Q
→ a
R
→ AA
T
→ BB
3.
Sebutkan klasifikasi Grammar menurut Chomsky!
TATA
BAHASA (GRAMMAR)
Bahasa merupakan himpunan kalimat
(baik terhingga maupun tak terhingga). Bahasa dapat disajikan dengan menyebut
kalimatnya satu persatu. Untuk bahasa tak hingga, penyebutan seperti itu tidak
mungkin. Oleh karena itu diciptakan cara penyajian yang mendeskripsikan bahasa
secara efisien. Cara penyajian tersebut adalah Tata Bahasa atau Grammar.
Sebuah
Tata Bahasa (Grammar) didefinisikan sebagai 4 tupel :
G = (Vn, Vt, S, Q)
Vn
dan Vt adalah simbol Non Terminal dan Simbol Terminal.
S
adalah sebuah elemen anggota Vn yang disebut Simbol Start. Q merupakan himpunan
Produksi.
4.
Sebutkan salah satu pengelompokan Grammar menurut Chomsky
Tipe
nol : UnRestricted Grammar (Tata Bahasa Tidak Terbatasi)
Tata Bahasa UnRestricted yang
tidak merupakan anggota dari klasifikasi lainnya ditandai dengan aturan
produksi yang bagian sebelah kirinya lebih panjang dari bagian sebelah kanan.
Aturan produksi yang mengandung simbol hampa (^) pasti merupakan Tata Bahasa
UnRestricted dan tidak termasuk klasifikasi lainnya.
5.
Jelaskan pengertian chomsky
Chomsky adalah salah satu
pemrakarsa teori pemerolehan bahasa yang meyakini bahwa proses pemerolehan
bahasa adalah suatu proses mental atau sebuah hirarki penahanan kelas tata
bahasa formal. Yang digambarkan oleh Noam Chomsky pada tahun 1956. Hal ini juga
dinami Marcel-Paul Schutzenberger, yang memainkan peran penting dalam
pengembangan teori bahasa formal. Pada dasranya Chomsky Hierarchy ini
memungkinkan kemungkinan bagi pemahaman dan penggunaan model ilmu komputer yang
memungkinkan programmer untuk mencapai tujuan linguistik bermakna sistematis.
PERTEMUAN
7
HIRARKI CHOMSKY
Pada
tahun 1956-1959 Noam Chomsky melakukan penggolongan tingkatan dalam bahasa berdasarkan
aturan produksi,yaitu menjadi empat class yang disebut Hirarki Chomsky.
Penggolongan tingkatan yang dilakukan oleh Noam Chomsky ada 4 class yaitu:
Tipe 0 / 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
Tipe 2 / Context Free
Grammar : ruas kiri haruslah tepat satu symbol variabel, yaitu simbol non
terminal
B → CDeFg
D → BcDe
Tipe 3 / Regular : ruas
kanan hanya memiliki maksimal satu symbol non terminal dan diletakkan paling
kanan sendiri
A → e
A → efg
A → efgH
C → D
Contoh soal dan
pembahasan:
•Grammar G1
dengan Q1 = {S → aB, B → bB, B → b}
Penjelasan :
Ruas kiri
semua produksinya terdiri dari sebuah VN, maka, G1 kemungkinan tipe CFG atau
RG. Selanjutnya, karena semua ruas kanannya terdiri dari sebuah VT atau string
VT VN, maka G1 adalah RG.
•Grammar G2 dengan Q2 =
{S → Ba, B → bB, B → b}
Penjelasan :
Ruas kiri
semua produksinya terdiri dari sebuah VN, maka, G2 kemungkinan adalah tipe CFG
atau RG.
Selanjutnya,
karena ruas kanannya mengandung string VN VT (Ba), maka, G2 bukan RG. Dengan
kata lain G2 adalah CFG.
•Grammar G3 dengan Q3 =
{S → aAb, B → aB}
Penjelasan :
Ruas
kiri semua produksinya terdiri dari sebuah VN, maka, G3 kemungkinan tipe CFG
atau RG.Selanjutnya, karena ruas kanannya mengandung string yang panjangnya
lebih dari 2 (yaitu aAb) maka, G3 bukan RG. Dengan kata lain, G3 adalah CFG.
•Grammar G4 dengan Q4 =
{S → aA, B → aB, aAb → aBCb}
Penjelasan :
Ruas
kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G4
kemungkinan tipe CSG atau UG.Selanjutnya, karena semua ruas kirinya lebih
pendek atau sama dengan ruas kanannya maka G4 adalah CSG.
•Grammar G5 dengan Q5 =
{aS → aA, B → ab, SAc → bc}
Penjelasan :
Ruas
kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G5
kemungkinan tipe CSG atau UG.Selanjutnya, karena semua ruas kirinya yang lebih
panjang daripada ruas kanannya (yaitu SAc), maka G5 adalah UG.
DAFTAR
PUSTAKA
http://johanesadika.blog.binusian.org/2014/03/17/tahapan-teknik-kompilasi/
http://rukmini12.blogspot.com/2017/01/teknik-kompilasi-mengenal-translator.html#:~:text=TEKNIK%20KOMPILASI%20(MENGENAL%20TRANSLATOR%2C%20COMPILER%2C%20INTERPRETER%20DAN%20ASSEMBLER),-MENGENAL%20TRANSLATOR%2C%20COMPILER&text=Penterjemah%20atau%20translator%20adalah%20seseorang,atau%20perusahaan%20dimana%20dia%20bekerja.
https://id.wikipedia.org/wiki/Analisis_leksikal
https://farmysetiawan.wordpress.com/2012/05/09/analisis-leksikal-analisis-leksikalanalisis-linierpembacaan-sekilas-scanner/
https://fida.ump.ac.id/perbedaan-dfa-dan-nfa/
https://tbouad.files.wordpress.com/2010/02/pertemuan-4-dfa-dan-nfa-compatibility-mod.pdf
http://web.if.unila.ac.id/ilmukomputer/cnf-chomsky-normal-form/
http://chaetiefha.blogspot.com/2014/05/klasifikasi-grammar-menurut-chomsky.html?m=1
http://andimeapasdkteknikkompilasi.blogspot.com/2018/10/klasifikasi-chomsky-dan-contoh.html?m=1
https://alwihsite.wordpress.com/2017/04/19/hirarki-chomsky-finite-state-otomata-fsa-dan-context-free-grammar-cfg-resume/
http://linslt.blogspot.com/2018/04/contoh-soal-teori-bahasa-dan-otomata.html?m=1
0 Response to "Teknik Kompilasi UTS"
Post a Comment
Harap comment jika ada hal yang ingin ditanyakan dan tidak dimenegerti. :)