Jumat, 26 November 2010

Grammar Context Free (CFG)

 Review Hal-hal Penting dari CFG
a.         Pola umum CFG : A α,  A Vα (V| V)*
b.         Sifat ambigu (ambiguity) :
Sebuah kalimat adalah ambigu jika terdapat lebih dari satu pohon sintaks yang dapat dibentuk oleh kalimat tersebut. Secara gramatikal kalimat ambigu dihasilkan oleh grammar ambigu yaitu grammar yang mengandung beberapa produksi dengan ruas kiri yang sama sedangkan dua atau lebih ruas kanan-nya mempunyai string terkiri  (prefix) yang sama. Contoh :
               S if E then S|if E then S else S,                        
dengan S : statement dan E : expression, mempunya dua produksi dengan ruas kiri sama (S) sedangkan kedua ruas kanannya dimulai dengan string sama (if E then S).
Grammar ambigu dapat diperbaiki dengan metoda faktorisasi kiri (left factorization). Prefix dari produksi di atas adalah sentensial if E then S sehingga faktorisasi akan menghasilkan :
               S if E then S T,        T ε|else S                {ε : simbol hampa}
c.         Sifat rekursi kiri (left recursion) :
Sebuah grammar dikatakan bersifat rekursi kiri jika untuk sebuah simbol nonterminal A terdapat derivasi non hampa A ⇒…⇒ Aα. Produksi berbentuk A Aα disebut produksi yang bersifat immediate left recursion.
Rekursi kiri dapat dieliminir dengan transformasi berikut :
                       A Aα|β transformasi menjadi : A βR, R αR
Transformasi ini dapat diperluas sehingga :
                       A Aα|Aα|... |Aα|...
bertransformasi menjadi :
                       A βRR|...R,     R αRR|..R

Contoh 1 : Diketahui : E E + T| T,  T T * F | F,  F (E)| I
yang jelas mengandung immediate left recursion untuk simbol E dan T.

Transformasi menghasilkan :
       E TR, R +TR ,   T FR, R*FR ,        F (E)| I

Tidak ada komentar:

Posting Komentar