Parsing

Context Free Grammar (CFG)

Grammar bebas yang bisa menghasilkan apa saja
Komponen:

• Variabel:
  Huruf besar (A, B, C, D)
• Terminal:
  Huruf kecil atau angka (a, b, 0, 1, 2, id, num, char, int, dll)
• Symbol:
  Semua tanda baca dan operasi matematika (!@#$%^&*()_+)

	 A       -->  ε | B | 1 | C+0 
pemproduksi        hasil produksi 
(1 variabel)        '|' pemisah

RE to CFG

jika ada + yang setara pada regex maka itu adalah OR

Left Recursion

Grammar yang memiliki 1 α dan 1 β

A --> Ab | cd
       α    β 
A  --> cdA'
A' --> bA' | ε

D  --> bd | De | ba
       β     α   β
D  --> bdD' | baD'
D' --> eD' | ε

F  --> aFc | Fde | a
        β     α    β
F  --> aFcF' | aF'
F' --> deF' | ε

P --> Pq | RQ
Q --> ab|cd
R --> Ra | F
F --> ε

P  --> RQP'
P' --> qP' | ε
Q  --> ab|cd
R  --> FR'
R' --> aR' | ε
F  --> ε

Left Factoring

5X + 5Y
= 5(X + Y)
---
A  --> Ba | Bcd | ef
    B (a | cd) | ef
A  --> B A' | ef
A' --> a | cd

B  --> abc | ad | eq
       a (bc | d) | eq
B  --> aB' | eq
B' --> bc | d

D  --> abd | bc | abc
       ab (d | c) | bc
D  --> abD' | bc
D' --> d | c

E   --> bad | bac | b
        b (ad | ac | ε)
E   --> bE'
E'  --> ad | ac | ε
        A (d | c) | ε
E'  --> AE'' | ε
E'' --> d | c
Conclusion
E   --> bE'
E'  --> AE'' | ε
E'' --> d | c

P --> ab | ac | dE
E --> a | c | ε | F
F --> Pq | Pe | d

P  --> aP' | dE
P' --> b | c
E  --> a | c | ε | F
F  --> PF' | d
F' --> q | e

Top Down Parsing

Langkah:

1. Pastikan tidak ada left recursion dan left factoring pada grammar
2. Tentukan nilai First (karakter pertama pada setiap hasil produksi)
3. Tentukan nilai Follow

Algoritma (Hanya bisa berdasarkan grammar di atasnya)
1.   if (S -> ab | c) and (S is start) then $ is the follow
2.   if (A -> αBβ) then first of β is the follow of B, excluding empty
3 a. if (A -> αB) then the follow of A is the follow of B
  b. if (A -> αBβ) and (first β is empty) then the follow of A is the follow of B

`note`: 
- β is the rest of the grammar 
- if there is only one character then pad left with ε

Cheat
Cari dari semua hasil produksi yang berada di belakang (kanan) `X` dan bukan variabel.

1. Buatlah tabel parsing
   1. Lihat nilai First
   2. Jika ada empty di first maka lihat follow

E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' | ε
F -> (E)id

Remove L-Recursion and L-Factoring
E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' | ε
F -> (E) | id

Determine First
First E -> (, id
First E' -> +, ε
First T -> (, id
First T' -> *, ε
First F -> (, id

Determine Follow 
Follow E -> $, )
Follow E' -> $, )
Follow T -> +, $, )
Follow T' -> +, $, )
Follow F -> *, +, $, )