Teknik Kompilasi_Pertemuan 11materi baru.pptx

Tentang pembelajaran

1. Recursive Descent Parser

2. Parsing Top Down ( Lanjutan ) NOTE DERIVASI --> LM DAN RM PARSING --> TOP DOWN & BOTTOM UP TOP DOWN --> BACKUP (BACKTRACK) ---> METODE BRUTE FORCE --> NO BACKUP --> RECURSIVE DESCENT PARSER --> Predictive parser Parsing top down Recursive Descent Dimulai simbol awal dicoba memproduksi kalimat menggunakan produksi yang tepat . Syarat grammar yang dapat diparse dengan recursive descent parsing adalah : Context-free grammar Tidak mempunyai left recursion Menerapkan dulu alternatif aturan produksi yang terpanjang ( bila terdapat lebih dari satu aiternatif aturan produksi )

3. Recursive Descent Parser Recursive Descent Parsing  adalah salah satu bentuk parsing yang masuk dalam  Top Down Parsing , di mana kita melakukan parsing secara menurun dari atas ke bawah . Parsing itu sendiri adalah sebuah proses penentuan apakah sebuah string dari token dapat di hasilkan oleh sebuah grammar.  Ciri dari  Recursive Descent Parsing  yang menonjol adalah secara rekursif menurunkan semua variabel dari awal sampai bertemu terminal dan tidak pernah mengambil token secara mundur ( No Backtrack ). Recursive Descent Parsing  adalah sangat bergantung pada algoritma scan dalam mengambil token.

4. Contoh <factor> => (< expr >) | i <term> => <factor> * <term> | <factor> < expr > => <term> + < expr > | <term> Tentukan kalimat berikut ini termasuk dalam aturan produksi tersebut i+I i+I * 1

5. Algoritma Recursive Descent 1. [ Inisialisasi ] Read (INPUT) 2. [Loop sampai semua string masukan ] Repeat while masih terdapat string masukan Repeat for i = 1, 2,.., LENGTH (INPUT) STRING[i ]  SUB (INPUT, i,1) CURSOR  1 NEXT  GET_CHAR if EXPR Then if NEXT ='#' Then Wr'te (INPUT,'VALID') Else Write (INPUT,'INVALID') Else Write (INPUT,'INVALID') Read (INPUT) Function EXPR [< expr > => <term> + < expr > ] <term>] if Not TERM Then Return (False) If NEXT ='+' Then NEXT  GET_CHAR if NEXT = '#' Then Return (False) If Not EXPR Then Return (False) Else Return (True)

6. Lanjutan Function TERM 1. [<term> => <factor > * <term> | <factor>] if Not FACTOR Then Return (False) If NEXT =’*’’ Then NEXT  GET_CHAR If NEXT  '#’ Then Return (False) If Not TERM Then Return (False) Else Return (True) Else Return (True) Function FACTOR 1. [<factor> ::= (< expr >) | i] If NEXT = '#' Then Return (False) lfNEXT ='(' Then NEXT  GET.CHAR If NEXT = '#' Then Return (False) If Not EXPR Then Return (False) If NEXT ≠')' Then Return (False) Else NEXT  GET.CHAR Return (True) It NEXT ≠'i' Then Return (False) Else NEXT  GET_CHAR Return (True)

7. Function GET_CHAR [ Mengembalikan karakter berikutnya dari string masukan ] CHAR  STRING [CURSOR] CURSOR  CURSOR + 1 Return (Char)

8. Predictive Parsing Model Predictive parser

9. Parsing ini disebut top-down parsing without backup atau deterministic top down parsing, menggunakan kelas grammar LL(k) sehingga disebut LL(k) parser. Kelas grammar LL(k) dapal diparse secara delerministik dengan melihat simbol masukan berikutnya yang akan diparse . Algoritma parsing untuk kelas grammar ini efisien . Kinerja algoritma ini fungsi linear panjang string masukan . Teknik deteksi dan pemulihan kesalahan dapat secara mudah ditambahkan ke algoritma parsing ini . Deterministik Pada situasi tidak diperbolehkan backup, masalahnya adalah satu yaitu menentukan produksi mana yang harus diterapkan pada simbol non-terminal yang akan diekspan dan awal string masukan mana yang akan secara sukses diparse pada saat itu .

10. Predictive parser mempunyai masukan , tumpukan ( stack), parsing table, dan keluaran . Masukan berupa deretan token yang diikuti dengan tanda $. Tanda $ ini untuk menyatakan akhir masukan . Tumpukan berisi deretan lambang tata bahasa dengan pangkal tumpukan berisi tanda $. Mula-mula , deretan lambang tata bahasa dalam tumpukan hanya terdiri dari starting symbol. Parsing table berupa deret dua dimensi M[A, a], di mana A adalah lambang non-terminal, dan a adalah lambang terminal atau tanda $. Parser dikendalikan oleh sebuah program yang sifat-sifatnya sebagai berikut : Program membaca X, lambang pada puncak tumpukan , dan a, token pada masukan . Kedua lambang ini menentukan aksi dari parser.

11. Ada empat kemungkinan , yaitu : Jika X = a = $, parser berhenti dan memberitahukan bahwa kerja parser telah selesai tanpa kesalahan sintaksis . Jika X = a ≠$, parser akan mengeluarkan X dari tumpukan , kemudian membaca token berikutnya . Jika X adalah lambang terminal dan tidak sama dengan a, berarti terjadi kesalahan sintaksis . Routine penanganan kesalahan sintaksis dipanggil untuk menangani kesalahan ini . Jika X adalah lambang non-terminal, program membaca isi sel pada parsing table. Isi sel ini dapat berupa produksi -X atau tanda kesalahan . Produksi -X adalah produksi dengan ruas kiri berupa lambang X. Jika M[ X,a ] berupa produksi X  UVW, parser mengganti X dengan WVU (U pada puncak tumpukan ). Sebagai keluaran , parser mengerjakan aksi yang bersesuaian dengan produksi ini.Jika M[X, a] berupa tanda kesalahan , parser memanggil routine guna menangani kesalahan sintaksis .

12. Konfigurasi