Computer Science

Soal Kuis 20 Mei 2014 :

Tentukan apakah dari sebuah titik sembarangan ada didalam, bersinggungan atau diluar lingkaran yang dihasilkan dari sebuah titik sembarang dengan jari-jari R

Misalkan :

Titik pertama berkoordinat x1, y1

Titik kedua berkoordinat x2,y2

Jari-jari untuk titik pertama adalah R

 

PseudoCode :

//inisialisasi variabel

float selisihx

float selisihy

float totalselisih

input x1,y1,x2,y2,R

 

//perhitungan jarak antar 2 titik

selisihx=(x1-x2)^2

selisihy=(y1-y2)^2

totalselisih=selisihx + selisihy

 

//syarat titik dalam bersinggungan atau di luar lingkaran

if (R>totalselisih) then

print “Titik didalam lingkaran”

else if (R<totalselisih) then

print “Titik diluar lingkaran”

else

print “Titik bersinggungan dengan lingkaran”

 

Code Generator untuk soal diatas :

1. Mov x1, r0
2. Mov x2, r1
3. Sub r1, r0
4. Mul r0, r0
5. Mov r0, selisihx
6. Mov y1, r2
7. Mov y2, r3
8. Sub r3, r2
9. Mul r2, r2
10. Mov r2, selisihy
11. Add selisihy, selisihx
12. Mov selisihx, totalselisih
13. Mov R, r4
14. Mul r4, r4
15. Gt totalselisih, r4
16. Jmpf totalselisih, 19
17. Prt “Titik di dalam lingkaran”
18. Jmp , 24
19. Lt totalselisih, r4
20. Jmpf , 23
21. Prt “Titik di luar lingkaran”
22. Jmp 24
23. Prt “Titik bersinggungan dengan lingkaran”
24. ……

 

www.binus.ac.id

Soal :

Mengapa Top Down Parsing harus menghilangkan left-recursion & left-factoring?

Jawab :

Pada top down parsing tidak diperbolehkan adanya left recursive serta grammar yang akan di parsing harus di left-factored (menggunakan metode left-factoring) karena :

1. Grammar yang memiliki left recursive tidak bisa diperiksa, sehingga harus diubah dulu agar tidak left recursive lagi. Karena left recursive akan mengakibatkan loop yang terus-menerus dan akan bersifat ambigu.

Contoh grammar yang memiliki left recursive :

Dari contoh di atas, dapat kita lihat bahwa grammar tersebut mengalami loop yang terus menerus. Oleh karena itu, untuk menghindari penurunan kiri yang looping, perlu dihilangkan sifat rekursif, dengan langkah-langkah sebagai berikut :

– Pisahkan Aturan produksi yang rekursif kiri dan yang tidak.
Aturan produksi yang rekursif kiri
A -> A α1 | A α2 | … | A αn
Aturan produksi yang tidak rekursif kiri
A -> β1 | β2 | … | βn

– Lakukan pergantian aturan produksi yang rekursif kiri, sebagai berikut :
1. A -> β1 Z | β2 Z | … | βn Z
2. Z -> α1 | α2 | … | αn
3. Z -> α1 Z | α2 Z | … | αn Z

– Pergantian dilakukan untuk setiap aturan produksi dengan simbol ruas kiri yang sama, bisa diganti dengan variabel Z1, Z2 dst, sesuai dengan variabel yang menghasilkan rekurisif kiri.

Contoh :

S -> Sab | aSc | dd | ff | Sbd
– Pisahkan aturan produksi yang rekursif kiri
S -> Sab | Sbd

Ruas Kiri untuk S: α1=ab , α2=bd
– Aturan Produksi yang tidak rekursif kiri
S -> aSc | dd | ff
Dari situ didapat untuk Ruas Kiri untuk S: β1 = aSc, β2 = dd, β3= ff

– Langkah berikutnya adalah penggantian yang rekursif kiri
S -> Sab | Sbd, dapat digantikan dengan
1. S -> aScZ1 | ddZ1 | ffZ1
2. Z1 -> ab | bd
3. Z1 -> abZ1 | bdZ1

– Hasil akhir yang didapat setelah menghilangkan rekursif kiri adalah sebagai Berikut :
S -> aSc | dd | ff
S -> aScZ1 | ddZ1 | ffZ1
Z1 -> ab | bd
Z1 -> abZ1 | bdZ1

2. Grammar yang belum di left-factored menggunakan left-factoring maka akan mengakibatkan konflik First-first yaitu konflik dimana susah untuk menentukan First dari suatu variable dalam grammar karena memiliki 2 produksi yang dimulai dengan terminal yang sama (mengakibatkan suatu grammar ambigu). Sehingga dapat digunakan left-factoring untuk menghilangkan keambiguan dalam grammar tersebut.

Contoh grammar yang memiliki konflik first-first :

E → T + E | T
T → int | int * T | ( E )

Penjelasan :

First(E) adalah T dimana ada 2 produksi E yang dimulai dengan T yang sama sehingga susah untuk diprediksi T yang mana merupakan First dari E. (T + E | T)
First(T) adalah int dan ( tetapi untuk int ada 2 sehingga juga susah diprediksi int yang mana merupakan first dari T. (int | int * T)

Penyelesaian dengan Left Factoring :

Mengeluarkan prefix yang sama dalam produksi yang bisa mengakibatkan munculnya ε-productions:

E → T + E | T menjadi E → T (+ E | ε ) => (dalam hal ini mengeluarkan T) sehingga membentuk:
E → T X
X → + E | ε

T → int | int * T | ( E ) menjadi T → int (* T | ε ) | ( E ) => (dalam hal ini mengeluarkan int) sehingga membentuk:
T → int Y | ( E )
Y → * T | ε

Setelah di left factoring maka untuk menentukan First dari suatu grammar akan tidak keliru dan lebih mudah diprediksi dan diparsing.

Sumber :

http://asanisembiring.files.wordpress.com/2012/02/pertemuan-7.doc

http://cecs.wright.edu/~tkprasad/courses/cs780/L101TDP.pdf

https://webdosen.budiluhur.ac.id/dosen/930011/buku_tekom2010.pdf

http://pages.cs.wisc.edu/~cs536-1/readings/5b.TOP-DOWN-PARSING.html

http://en.wikipedia.org/wiki/LL_parser#Left_Factoring

www.binus.ac.id

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 🙂