Tugas Teknik Kompilasi [PDF]

Citation preview

TUGAS TEKNIK KOMPILASI SOAL DAN PEMBAHASAN ALGORITMA PARSER



Disusun Oleh: Recky



201543579062



Robby Pratama P. Maulana



201543579063



Saepul Hilal



201243500190



Linlin. N



201243500135



Iin Sumirat



201443579068



PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS TEKNIK, MATEMATIKA DAN IPA UNIVERSITAS INDRAPRASTA PGRI JAKARTA 2015



1. Algoritma Parser LR(0) Soal : S’  S S  aABe A  Abc Ab Bd a. Buatlah LR(0) Parsing Table berdasarkan grammar di atas! b. Buatlah pergerakan LR(0) Parser dengan input abbcbcde$! Jawaban : a. LR(0) Parsing Table State I0 I1 I2 I3 I4 I5 I6 I7 I8 I9 I



a s2



b



Action c d



e



$



S 1



Goto A



B



acc s4 s6 r4



3 s7 r4



5 s8



s9 r5 r2 r3



r3



Keterangan : si = shift dan push state i rj = reduksi dengan produksi nomor j acc = accept kosong = error



b. Pergerakan LR(0) parser dengan input abbcbcde$ State



Input



Action



0



abbcbcde$



shift



0a2



bbcbcde$



shift



0a2b4



bcbcde$



Ab



0a2A3



bcbcde$



shift



0a2A3b6



cbcde$



shift



0a2A3b6c9



bcde$



A  Abc



02A3



bcde$



shift



02A3b6



cde$



shift



0a2A3b6c9



de$



A  Abc



0a2A3



de$



shift



0a2A3d7



e$



Bd



0a2A3B5



e$



shift



0a2A3B5e8



$



S  aABe



0S1



$



accepted



2. Algoritma Parser SLR Soal : A’ –> A A –> A * B A –> B A –> m A d B –> b a. Buatlah Diagram Transisi Operasi Go To berdasarkan grammar diatas! b. Buatlah SLR Parsing Table berdasarkan diagram Transisi Operasi Go To!



Jawaban :



a. Diagram Transisi Operasi Go To



State 0 A’ –> .A A –> .A * B A –> .B A –> .m A d B –> .b



goto(S,1) goto(S,1) goto(B,2) action(0,m), Shift 3 action(0,b), shift 4



State 1 A –> A . * B A ‘ –> A.



action(1,*), shift 5 action(1,$),accept



State 2 A –> B .



Action(2,B) reduce 2



State 3 A –> m . A d A –> .B A –> . m A d B –> .b



goto(A,6) goto(B,2) action(0,m), Shift 3 action(0,b), shift 4



State 4



B –> b.



action(4,$) reduce 4



State 5 A –> A * . B B –> .b



goto(A,7) action(5,b) shift 5



State 6 A –> m A . d



action(8,d) shift 8



State 7 A –> A * B .



Action(7,$) reduce 7



State 8 A –> m A d .



Action(8,$) reduce 8



b. SLR Parsing Table State



R7 R8 3. Algoritma Parser LR(1) dan LALR(1) Soal : S’  S S  CC C  cC



Cd a. Buatlah LR(1) Parsing Table berdasarkan grammar di atas! b. Buatlah LALR(1) Parsing Table berdasarkan grammar di atas! Jawaban : a. LR(1) Parsing Table State 0 1 2 3 4 5 6 7 8 9



Actions c



d



S3



S4



S6 S3 R3



S7 S4 R3



Goto $



S



C



1



2



acc 5 8 R1 S6



S7



9 R3



R2



R2 R2



b. LALR(1) Parsing Table State 0 1 2 36 47 5 89



Actions C



D



S36



S47



S36 S36 R3



S47 S47 R3



R2



R2



E→TX X→+E|ε



$



S



C



1



2



Acc



4. Algoritma Parser LL(1) Soal :



Goto



5 89 R3 R1 R2



T → ( E ) | int Y Y→*T|ε Buatlah Buatlah LL(1) Parsing Table berdasarkan grammar di atas! Jawaban : T E X Y



int Int Y TX



Follow( E ) = {), $} Follow( X ) = {$, ) } Follow( Y ) = {+, ) , $} Follow( T ) = {+, ) , $} First( T ) = {int, ( } First( E ) = {int, ( } First( X ) = {+} First( Y ) = {*}



*



+



*T



+E ε



( (E) TX



)



$



ε ε



ε ε



DAFTAR PUSTAKA http://www.facweb.iitkgp.ernet.in/~niloy/Compiler/notes/LRP.doc http://www.facweb.iitkgp.ernet.in/~niloy/Compiler/notes/LALRP.doc http://mikeryan.blog.binusian.org/2014/04/08/tugas-3-teknik-kompilasi http://people.cs.pitt.edu/~mock/cs1622/lectures/lecture10.pdf