Chomsky Hierarchy
Grammar tipe 0 : α → β α tidak boleh string kosong.
γ A δ → γ β δ A = non terminal, γ dan δ konteks
dari kiri dan kanan dari A
Grammar tipe 0 disebut juga Unrestrected grammars atau
Phrasestructure grammars atau
Semi-thue grammars.
Grammar tipe 1 - Context-sensitive grammars : γ A δ → γ β δ α tidak boleh kosong (β).
Grammar tipe 2 - Context free grammars (CFG) : A → β ruas kiri harus non-terminal tunggal.
Grammar tipe 3 - Regular grammars : ruas kanan dari produksi mungkin berupa
a. hanya 1 terminal, atau
b. 1 non-terminal dan 1 terminal
Top-Down Parser
Dikenal dua macam parser, yaitu Top-down parser dan Bottom-up parser. Top-down parser dimulai dengan root dari parse tree ke bawah.
Left Recursions
Left recursion menimbulkan masalah pada top-down parser.
Misalnya ada grammar:
E→E + T | T
T→T * F | F
F→I | (E)
dan misalnya di-parse ekspresi i+i*i
maka parse tree nya adalah:
Cara mengatasi left recursion:
Untuk setiap non-terminal dalam grammar:
Pisahkan produksi yang berbentuk left-recursion dari yang lain.
Misalnya:
A→ Aα1 | Aα2 | Aα3 | ... (left-recursion)
A→δ1 | δ2 | δ3| ...
Masukkan non-terminal baru A'
Ubah produksi non-left-recursion di A menjadi:
A→δ1A' | δ2 A' | δ3A'| ...
Ganti produksi left-recursion di A dengan:
A→ ε | αA'| α'2| αA'| ...
Contoh Soal -1:
Diketahui grammar (ditulis dalam bentuk produksinya saja):
A→Ac |Ad | e | f
Pisahkan yang left-recursion dan yang non-left-recursion
Left recursion: A→ Ac | Ad
Non-left recursion: A→ e | f
Tambahkan non-terminal A'. Pada produksi yang non-left-recursion, ubahlah e menjadi eA' dan f dengan fA'. Pindahkan produksi yang left recursion ke A' dengan ruas kanan dari A' adalah e, cA' dan dA'.
Produksi yang telah diperbaiki adalah sebagai berikut:
A→ eA' | fA'
A→ ε | cA' | dA'
Walau ada dua produksi A yang left-recursion namun dapat digabung dengan hanya menambahkan satu non-terminal yang baru.
Contoh Soal-2:
Hilangkan semua left-recursion dari grammar berikut ini:
S→ aA | b | cS
A→ Sd | e
Produksi S tidak memerlukan penanganan karena non-left-recursion. Pada ruas kanan produksi A dimulai dengan non-terminal S. Inilah left-recursion. Untuk itu S disubstitusi dengan ruas kanan dari produksi S sehingga menjadi:
A→ aAd | bd | cSd | e
Perhatikanlah bahwa yang tercetak tebal berasal dari produksi S yang disubstitusikan ke A. Dengan produksi yang baru ini left recursion telah dapat dihindari. Hal ini dapat terjadi karena kita dapat menelusuri bentuk sentensial dari A berikut ini:
Produksi yang baru mengabaikan Sd.
Recursive-Descent Parsing.
Ruas kanan dari produksi biasanya berupa campuran antara terminal dan non-terminal. Fungsi recursive-decent adalah menelusuri grammar di ruas kanan sesuai dengan masukkannya, sampai ditemukan token yang cocok. Tetapi jika ditemukan non-terminal maka akan dipanggil fungsi lain yang bersesuaian dengan non-terminal tersebut. Dengan kata lain setiap non-terminal memiliki fungsi sendiri-sendiri.
Contoh:
S - > bA | c
A-> dS | e
Fungsi S mengecek b; untuk A akan ditelusuri melalui fungsi A. Jadi jika ada 2 non-terminal maka dibutuhkan 2 fungsi. Fragmen dari fungsi-fungsi tersebut adalah:
Fungsi S:
1. function S:boolean;
2. begin
3. S:=true;
4. if token_is('b') then
if A then {mencoba fungsi S -> bA}
writeln(S->bA')
else
S:=false
else
if token_is('c' then
writeln('S->c')
else
begin
error('S');
S:=false
end;
end; {S}
Fungsi A:
1. function A:boolean;
2. begin
3. A:=true;
4. if token_is('d') then
5. begin
6. if S then
7. if token_is('d') then
8. writeln('A->dSd')
9. else
10. begin {error, string masukan tdk diakhiri dengan 'd')
11. error('A')
12. A :=false
13. end
14. else
15. A:=false {error, token tengahnya tidak S}
16. end
17. else
18. if token_isi('e') then
19. writeln('A->e')
20. else
21. begin {seluruh bagian kanan fungsi A tidak terpenuhi}
22. error('A');
23. A:=false
24. end
25. end; {A}
Misalnya string masukkannya adalah bdcd