Pseudocode dan Code Generator berdasarkan kasus:

input titik pusat dari lingkaran beserta dengan jari-jarinya, input titik lain, lalu program akan mencari apakah titik lain tersebut terletak di luar, di dalam atau persis di titik jari-jari lingkaran.

Pseudocode:
float distance, distanceX, distanceY;
input Xa, Ya, Ra;
input Xb, Yb;
distanceX = Xa-Xb;
distanceY = Ya-Yb;
distance = sqrt(pow(distanceX,2) + pow(distanceY,2));
if(distance > Ra)
print ‘diluar lingkaran’;
else if (distance == Ra)
print ‘sama dengan jari-jari’;
else print ‘di dalam lingkaran’

Code Generator
Representatif Machine Language:
01. mov Xa, R0
02. mov Xb, R1
03. sub R1, R0
04. mov R0, distanceX
05. mov Ya, R2
06. mov Yb, R3
07. sub R3, R2
08. mov R2, distanceY
09. mov distanceX, R4
10. pow #2, R4
11. mov distanceY, R5
12. pow #2, R5
13. add R5, R4
14. sqrt #2, R4
15. mov Ra, R6
16. gt R6, R4
17. jmpF R4, (20)
18. prt , “diluar lingkaran”
19. jmp ,(25)
20. eq R6, R4
21. jmpF R4, (24)
22. prt , “sama dengan jari-jari”
23. jmp , (25)
24. prt , “di dalam lingkaran”
25. …

http://binus.ac.id

Nomor 1 :

S -> S+A | S-A  | A+S | A-S | B*A

B-> aB | B(a+B) | B*a | a(a+B) | b

A-> a

Tentukan First, Follow dan Table dari Production diatas!

Jawaban:

–          Left Recursive

S-> A+SS’ | A-SS’ | B*AS’

S’-> +AS’ | -AS’ | e

B-> aBB’ | a(a+B)B’ | bB’

B’-> (a+B)B’ | *aB’ | e

A->a

–          Left Factoring

S-> AS”  | B*AS’

S’-> +AS’ | -AS’ | e

S”-> +SS’ | -SS’

B-> aB” | bB’

B’-> (a+B)B’ | *aB’ | e

B”-> BB’ | (a+B)B’

A->a

First (S) = {a, b}

First (S’) = {+, -, e}

First (S”) = {+, -}

First (B) = {a, b}

First (B’) = {(, *, e}

First (B”) = {a, b, (}

First (A) = {a}

Follow (S) = {$, +, -}

Follow (S’) = {$, +, -}

Follow (S”) = {$, +, -}

Follow (B) = {), (, *}

Follow (B’) = {), (, *}

Follow (B”) = {), (, *}

Follow (A) = {$, +, -}

Nomor 2 :

S->if E the S|if E then S else S|v:=E

V->id|id[E]

E->E+T|E-T|T

T->T*F|T/F|F

F->V|(E)|const

Jawab:

S->if E then S S’ | V:=E

S’-> ε |else S

V->id V’

V’-> ε | [E]

E->T E’

E’-> +TE’ | -TE’| ε

T’->FT’

T’-> *FT’|/FT’| ε

F->V|(E)|const

First (S)= {if , id}

First (S’)= {ε , else}

First (V)= {id}

First (V’)= {ε , [ }

First (E)= {id, ( , const}

First (E’)= {+, -, ε}

First (T)= {id, (, const}

First (T’)= {* , / , ε}

First (F)={id, (, const}

Follow (S)={ $ , else }

Follow (S’)= { $ , else }

Follow (V)= { : , * , / }

Follow (V’)= {  [ , : , * , / }

Follow (E)= { then, $ , else }

Follow (E’)= { then, $ , else }

Follow (T)= { + , – }

Follow (T’)= { + , – }

Follow (F)= { * , / }

Nomor 3 :

S ->  a = A

A -> aA’ | bA’

A’ -> +AA’ | є

First :

First (S) = { a }

First (A) = {a , b}

First (A’) = {+ , є }

Follow :

Follow (S) = { $ }

Follow (A) = { $ , +}

Follow (A’) = { $ , + }

Table :

	$	+	a	b
S			S ->  a = A
A			A -> aA’	A -> bA’
A’	A’ -> e	A’ -> +AA’ | e

Nomor 4 :

be -> bt be’

be’ -> or bt be’

be’ -> e

bt -> bf bt’

bt’ -> and bf bt’

bt’ -> e

bf -> not bf

bf -> ( be)

bf -> true

bf -> false

Periksalah input sebagai berikut : not (true or false) and true and true and false not (false) true

a.       Menentukan First

First (be)              : not, (, true, false

First (be’)            : or, e

First (bt)               : not, (, true, false

First (bt’)             : e, and

First (bf)               : not, (, true, false

b.      Menentukan follow

Follow (be)         : { $, ) }

Follow (be’)        : { $, ) }

Follow (bt)          : { or, $, ) }

Follow (bt’)         : { or, $, ) }

Follow (bf)          : { or, $, ), and }

c.       Tabel

	not	true	false	or	and	(	)	$
be	be -> bt be’	be -> bt be’	be -> bt be’			be -> bt be’
be’				be’ -> or bt be’
bt	bt -> bf bt’	bt -> bf bt’	bt -> bf bt’
bt’				bt’ -> e	bt’ -> and bf bt’
bf	bf -> not bf	bf ->true	bf ->false

d.      Pemeriksaan Input

No.	Stack	Input	Output
1.	be $	not (true or false) and true and true and false not (false) true $	be -> bt be’
2.	bt be’ $	not (true or false) and true and true and false not (false) true $	bt -> bf bt’
3.	bf bt’ be’ $	not (true or false) and true and true and false not (false) true $	bf -> not bf
4.	notbfbt’ be’ $	not (true or false) and true and true and false not (false) true $	pop not
5.	bf bt’ be’ $	(true or false) and true and true and false not (false) true $	bf -> (be)
6.	(be) bt’ be’ $	(true or false) and true and true and false not (false) true $	pop (
7.	be) bt’ be’ $	true or false) and true and true and false not (false) true $	be -> bt be’
8.	bt be’) bt’ be’ $	true or false) and true and true and false not (false) true $	bt -> bf bt’
9.	bf bt’ be’) bt’ be’ $	true or false) and true and true and false not (false) true $	bf -> true
10.	truebt’ be’) bt’ be’ $	true or false) and true and true and false not (false) true $	pop true
11	bt’ be’) bt’ be’ $	or false) and true and true and false not (false) true $	bt’ -> ε
12	be’) bt’ be’ $	or false) and true and true and false not (false) true $	be’ ->or bt be’
13.	orbt be’ ) bt’ be’ $	or false) and true and true and false not (false) true $	pop or
14.	bt be’) bt’ be’ $	false) and true and true and false not (false) true $	bt -> bf bt’
15.	bf bt’ be’) bt’ be’ $	false) and true and true and false not (false) true $	bf -> false
16.	falsebt’ be’) bt’ be’ $	false) and true and true and false not (false) true $	pop false
17.	bt’ be’) bt’ be’ $	) and true and true and false not (false) true $	bt’ -> ε
18.	be’) bt’ be’ $	) and true and true and false not (false) true $	be’ -> ε
19.	)bt’ be’ $	) and true and true and false not (false) true $	pop )
20.	bt’ be’ $	and true and true and false not (false) true $	bt’ -> and bf bt’
21.	and bf bt’ be’ $	and true and true and false not (false) true $	pop and
22.	bf bt’ be’ $	true and true and false not (false) true $	bf -> true
23.	truebt’ be’ $	true and true and false not (false) true $	pop true
24.	bt’ be’ $	and true and false not (false) true $	bt’ -> and bf bt’
25.	and bf bt’ be’ $	and true and false not (false) true $	pop and
26.	bf bt’ be’ $	true and false not (false) true $	bf -> true
27.	truebt’ be’ $	true and false not (false) true $	pop true
28.	bt’ be’ $	and false not (false) true $	bt’ -> and bf bt’
29.	and bf bt’ be’ $	and false not (false) true $	pop and
30.	bf bt’ be’ $	false not (false) true $	bf -> false
31.	falsebt’ be’ $	false not (false) true $	pop false
32.	bt’ be’ $	not (false) true $	ditolak

Mengapa dalam top down parsing tidak boleh ada left recursive atau  left factoring?

Metode Top Down Parsing ada 2 jenis metode:

1. Backtrack/Backup: Brute Force

2. No Backtrack: Recursive Descent Parser

Metode Brute Forcer

Dalam metode Brute Forcer, grammar yang memiliki Left Recursion tidak bisa diperiksa, karena Left Recursion akan mengalami loopng atau perulangan secara terus-menerus atau tak terhingga. Sehingga perlu diubah terlebih dahulu menjadi grammar yang tidak mengandung Left Recursion.

Contoh:

E -> T | T + E | T – E

T -> F | F * T | F / T

F -> i

Grammar ini diterima karena tidak mengalami left recursive.

E -> E+T | E-T  | T

T -> T* F | T / F | F

F -> i

Grammar ini tidak diterima karena mengalami left recursive.

Dalam Top Down Parsing kita harus melakukan left factoring karena jika tidak melakukan left factoring, maka akan ada kemungkinan grammar tersebut mengalami ambiguitas. Left Factoring ini akan memperbaiki grammar yang ambigu (bila digambar dengan tree akan menghasilkan lebih dari 1 sintaks). Pada case – case tertentu, jika kita sudah melakukan eliminasi left recursion dan grammarnya sudah tidak ambigu tetapi kita masih tidak dapat menentukan “first” dari symbol tertentu, maka kita harus melakukan factorial.

Contoh:

–          Grammar sebelum melakukan left factoring

–           Grammar Sesudah melakukan left factoring

Source : http://cse.spsu.edu/clo/teaching/cs4713/lecture/node28.html

www.binus.ac.id