LL Grammar First dan Follow - Teknik Kompilasi

LL Grammar

Grammar LL(1) singkatan dari scanning the input from Left to right for Leftmost derivation using 1 (one) input symbol of lookahead at each step to making parsing action decision. Grammar yang bagus adalah grammar yang mempunyai nilai tunggal untuk setiap sel M(A,a) pada Parsing Table. Tetapi sayangnya tidak semua grammar bersifat bagus. LL Grammar memiliki beberapa sifat, yaitu :

Grammar G adalah LL(1) jika dan hanya jika untuk setiap dua produksi yang berbeda A→α|β pernyataan berikut dipenuhi:

1.     α dan β kedua-duanya tidak akan menderivasi string yang awalnya adalah terminal a.

2.     Paling banyak hanya satu dari α dan β dapat menderivasi string kosong.

3.     Jika B ->  , maka a tidak akan menderivasi string yang awalnya merupakan suatu terminal di FOLLOW(A).

Ø  First

First(X) adalah himpunan simbol terminal yang merupakan simbol pertama dari X atau merupakan simbol pertama dari simbol-simbol yang dapat diturunkan dari X.

Ø  Follow

Follow(Y) adalah himpunan simbol terminal yang dapat muncul tepat disebelah kanan Y melalui nol atau lebih derivasi.

Contoh First dan Follow:

First :

First S = First(A) – ε, First(B) – ε       (1)

            = b, a, c, ε                                (5)

First A = First(C) – ε, a, ε                   (2)

            = b, a, ε                                   (6)

First B = c                                           (3)

First C = b, ε                                       (4)

Follow :

Follow S         = $                                                                                           (1)

Follow A         = First(B) – ε, First(C) – ε, First(B’) – ε, Follow(B’)            (2)

                        = c, b, a, $                                                                               (8)

Follow B         = Follow(B)                                                                            (3)

                        = $                                                                                           (6)

Follow B’        = Follow(B), Follow(B’)                                                        (4)

                        = $                                                                                           (7)

Follow C         = a, First(B’) – ε, Follow(B’)                                                 (5)

                        = a, $                                                                                       (8)

# Jika tidak ada yang follow maka hasilnya “$”

# Untuk menentukan tabel First dilihat dari huruf terminal apa saja yang dihasilkan dan diisi mengikuti produknya.

# Sedangkan follow diubah menjadi “ε”