Hacked By TeaM_CC :: 0x0 WAS HERE
Your Security breached ….
No security is perfect
Facebook.com/cyber.command0s
[+]Team_CC[+]
Your Security breached ….
No security is perfect
Facebook.com/cyber.command0s
[+]Team_CC[+]
Jawab :
dihilangkan left recursive dan left-factoring sebelum melakukan top down parsing karena berbagai alasan dibawah ini antara lain :
(left recursive)
(Left Factoring)
Jika tidak dilakukan , akan terjadi ambigu karena terdapat non-terminal yang sama muncul 2 kali pada sisi kanan produksi.
References :
Alfred V. Aho
Ravi Sethi
Jeffrey D. Ullman
Compilers, Principles, Techniques, and Tools
1986(Reprinted 1988)
Addison-wesley publishing company
Perbedaan antara Top Down Parsing dan Bottom Up Parsing:
Top Down Parsing menggunakan asumsi untuk mengecek kebenaran parsing (parsing dilakukan dari root)) sedangkan Bottom Up mencocokkan rules dengan string, bila terjadi kesalahan maka akan dilakukan backtrack (Parsing dilakukan dari leaves).
Top Down memiliki kelebihan:
– Menemukan hasil lebih cepat jika pencarian tepat.
– Tidak perlu mengecek setiap node.
Top Down memiliki kelemahan:
– Jika terjadi Left Rekursif akan looping forever.
– Tidak efadalahien karena harus menyimpan hasil pencarian sebelumnya.
– Algoritma lebih sulit.
Bottom Up memiliki kelebihan:
– Semua kemungkinan pasti ditelusuri.
– Mendapatkan hasil yang lebih akurat.
– Lebih mudah dimengerti oleh manusia.
– Tidak akan terjadi looping forever (pasti berhenti).
Bottom Up memiliki kelemahan:
– Lambat karena harus mengecek satu per satu jika salah satu maka harus backtrack.
– Time complexity besar.
– Menggunakan memori besar.
Jadi Bottom Up lebih baik dibandingkan dengan Top Down sehingga parser generator lebih banyak menggunakan Bottom Up
Pembuktian pekerjaan yang dilakukan oleh Top Down dan Bottom Up:
Grammar:
Top Down Parsing
String : acddf.
Dengan Top Down Parsing kita mengasumsikan string cocok dengan S. Kita tahu bahwa string akan mungkin cocok dengan xyz atau aBC. Dalam kasus ini kita tahu string acddf tidak cocok dengan xyz tetapi akan cocok dengan aBC, sehingga kita perlu membuktikannya.
Langkah-langkah:
Bottom Up Parsing
Bottom Up Parsing mulai melakukan parse tree dari leaves (nodes). Pada akhir string, semuanya harus digabungkan menjadi S dan hanya S yang hanya tersisa. Jika tidak, maka harus dilakukan backtrack dan mencoba mengkombinasikan dalam cara yang lain. Dengan Bottom Up Parsing, kita mengurangi sebanyak mungkin node untuk menjadi token yang lebih besar.
Contoh
String : acddf.
Langkah-langkah:
References :
J. P. Bennett
Introduction to Compiling Techniques
1996
McGraw-Hill(A Division of The McGraw-Hill Companies)
Syntax Analyzer Application Source code dowload link : http://willypt.com/YkZQDqCpvV.file
Syntax Analyzer Application : http://willypt.com/tekkom/
References :
Compilers – Principles, Techniques, and Tools
by Alfred V.Aho , Ravi Sethi , Jeffrey D.Ullman
Thanks for the teamwork guys,
www.binus.ac.id
Soal
Buatlah DFA dengan aturan minimal 6 state dan maksimum 8 state, dan minimal ada 3 final state serta ada 5 final state untuk maksimalnya, lalu selisih dari state dengan final state minimal harus 2.
Keseluruhan state
Min : 6
Max : 8
Final State
Min : 3
Max : 5
RE (Regular Expression)
RE = a*b(b|a)*(a|b)+a(a|b)*
Ɛ-NFA
Ɛ-NFA -> DFA
Ɛ-Closure({0}) = {0,1,3} = S0
Ɛ-Closure(move(S0,a))=Ɛ-Closure({2})
=> {1,2,3} = S1
Ɛ-Closure(move(S0,b))=Ɛ-Closure({4})
=> {4,5,6,8,11,12,13,15} = S2
Ɛ-Closure(move(S1,a))=Ɛ-Closure({2})
=> S1
Ɛ-Closure(move(S1,b))=Ɛ-Closure({4})
=> S2
Ɛ-Closure(move(S2,a))=Ɛ-Closure({9,14})
=> {5,6,8,9,10,11,12,13,14,15,17,18} = S3
Ɛ-Closure(move(S2,b))=Ɛ-Closure({7,16})
=>{5,6,7,8,10,11,12,13,15,16,17,18} = S4
Ɛ-Closure(move(S3,a))=Ɛ-Closure({9,14,19})
=> {5,6,7,8,9,10,11,12,13,14,15,17,18,19,20,21,23,26} = S5*
Ɛ-Closure(move(S3,b))=Ɛ-Closure({7,16})
=> S4
Ɛ-Closure(move(S4,a))=Ɛ-Closure({9,14,19})
=>S5*
Ɛ-Closure(move(S4,b))=Ɛ-Closure({7,16})
=> S4
Ɛ-Closure(move(S5,a))=Ɛ-Closure({9,14,19,22})
=> {5,6,8,9,10,11,12,13,14,15,17,18,19,20,21,22,23,25,26} = S6*
Ɛ-Closure(move(S5,b))=Ɛ-Closure({7,16,24})
=>{5,6,7,8,10,11,12,13,15,16,17,18,20,21,23,24,25,26} = S7*
Ɛ-Closure(move(S6,a))=Ɛ-Closure({9,14,19,22})
=> S6*
Ɛ-Closure(move(S6,b))=Ɛ-Closure({7,16,24})
=>S7*
Ɛ-Closure(move(S7,a))=Ɛ-Closure({9,14,19,22})
=> S6*
Ɛ-Closure(move(S5,b))=Ɛ-Closure({7,16,24})
=>S7*
Minimized DFA
Welcome to Binusian blog.
This is the first post of any blog.binusian.org member blog. Edit or delete it, then start blogging!
Happy Blogging 🙂