Mencari First Set dan Follow Set (Top-Down Parsing)

Penulis : D4985 – Novita Hanafiah, S.Kom.,M.Sc.

First (a) adalah sekumpulan simbol terminal yang muncul sebagai simbol pertama dalam string yang berasal dari a dimana a adalah string simbol dari grammar yang ada. Jika a diturunkan ke e, maka e juga di FIRST (a).

Follow (A) adalah himpunan terminal yang terjadi segera setelah (mengikuti) non-terminal A dalam string yang diderivasi dari start symbol.

First set dan follow set diperlukan untuk membantu dalam pembuatan parsing table pada metode top-down parsing. Sebagai contoh diberikan sebuah rule sebagai berikut:

S -> ABCDE

A -> a | E

B -> b | E

C -> c

D -> d | E

E -> e | E

Jika ingin mencari first set maka tips nya adalah dapat dimulai dari grammar yang berada paling bawah, dan memperhatikan sisi LHS dari grammar. Contohnya ketika mencari first(E) maka dapat dilihat pada sisi LHS E dimana E dapat diderivasi menjadi e atau e. Terminal yang dapat muncul sebagai simbol pertama dari grammar ini adalah {e, E}. Kemudian dilanjutkan kembali pencarian First(D) dimana bila D diderivasi maka bisa mempunyai symbol terminal {d, E} sebagai awal string. Dilanjutkan kembali dengan First(C) dimana bila C diderivasi hanya dapat menghasilkan string {c} yang juga merupakan terminal awal dari produksi grammar tersebut. Demikian juga untuk First(B) dan First(A) dimana First(B) = {b, E} dan First(A) = {a, E}.

Berikutnya perhatikan dalam pencarian First(S). S dapat diderivasi menjadi ABCDE dimana A merupakan awalan dari derivasi yang dihasilkan. Karena A merupakan sebuah variable bukan terminal, maka ini berarti bahwa apapun awalan terminal dari A nantinya juga merupakan awalan terminal dari S, sehingga First(S)=First(A)={a, E}. Karena first dari A mengandung E yang berarti bahwa variable A dapat bernilai e (atau berarti empty string), maka hal ini sama dengan grammar S -> BCDE (ketika A bernilai e) sehingga First(S)=First(B)={b, E}. Ketika nilai B adalah e maka sama dengan sebelumnya bahwa S dapat diderivasi menjadi CDE (dimana A dan B bernilai E) sehingga awalan terminal yang dapat diproduksi sama dengan awalan terminal C (First(S)=First(C)={c}). Ketika diketahui bahwa terminal dari First(C) hanya ada {c} dan tidak mengandung E, hal ini berarti produksi dari grammar S akan selalu berawalan c (Bila kondisi A dan B adalah E). Jadi, First(S) adalah {a, b, c} dimana nilai E tidak termasuk dari terminal yang bisa dihasilkan oleh S lagi.

Jika mencari Follow set maka akan lebih mudah dicari dari grammar paling atas (start simbol) dan dengan memperhatikan sisi RHS dari kemunculan Variable yang dicari. Untuk Follow set dari start symbol akan selalu ada terminal {$} dimana symbol $ menandakan akhir dari string. Contoh pada grammar diatas, ketika melakukan pencarian Follow(S) maka kita akan mencari apakah variable S muncul pada sisi RHS. Dalam kasus ini S tidak muncul kembali di sisi RHS, dan S merupakan start symbol, maka Follow(S)={$}.

Ketika mencari Follow(A) maka kita akan melihat dimana letak kemunculan dari variable A dan ternyata pada kasus ini A hanya muncul pada grammar S -> ABCDE. Jika S diderivasi, maka setelah variable A akan diikuti oleh variable B, sehingga Follow(A)=First(B)={b, c}. Terminal set yang mungkin dapat muncul setelah produksi dari variable A akan sama saja dengan awalan set yang mungkin muncul sebagai awalan set dari B. Untuk mencari Follow(B) juga sama konsepnya, yaitu dari aturan kemunculan variable C tersebut yaitu di bagian S -> ABCDE, maka Follow(B)=First(C)={c}.

Mencari Follow set dari C dapat dilihat kemunculan variable C di grammar S -> ABCDE dimana Follow(C)=First(D)={d, E}. Kita tidak akan menuliskan e sebagai bagian dari follow set, melainkan menggantikan kemungkinan e tersebut pada variable D. Jadi dari pencarian Follow(C)=First(D) diperoleh E dimana berarti bahwa variable D bisa saja bernilai E dan jika D bernilai E maka Follow(C) akan sama dengan First(E)={e, E}. Hasil dari pencarian tersebut menunjukkan kembali bahwa E bisa bernilai e sehingga bila E bernilai e maka grammar bisa saja terlihat seperti berikut S -> ABCEE (bisa dianggap e tidak ada), sehingga C akan terletak di paling akhir dari derivasi yang mungkin terjadi. Jika kondisi seperti ini maka Follow set dari C akan sama dengan follow set yang dapat dihasilkan dari variable produksi (S) tersebut (karena letak C yang sudah berada dipaling kanan), sehingga sama dengan Follow(C)=Follow(S)={$}. Jadi setelah menulusuri beberapa kemungkinan epsilon tersebut maka diperoleh Follow(C)={d,e,$}.

Mencari Follow set dari D juga mirip dengan yang diatas, berarti Follow(D)=First(E)={e, E} dan jika E bernilai E maka D akan terletak dipaling akhir dari rule tersebut sehingga Follow(D)=Follow(S)={$}. Jadi Follow(D)={e,$}.

Follow set dari E sama dengan follow set dari variable produksi tersebut (S) karena terletak dipaling akhir dari rule yang ada, sehingga Follow(E)=Follow(S)={$}.

	First	Follow
S -> ABCDE	{a, b, c}	{$}
A -> a | E	{a, E}	{b, c}
B -> b | E	{b, E}	{c}
C -> c	{c}	{d, e, $}
D -> d | E	{d, E}	{e, $}
E -> e | E	{e, E}	{$}

Contoh grammar yang lain:

S -> Bb | Cd

B -> aB | E

C -> cC | E

Mari dimulai dengan pencarian First set dari grammar paling bawah.

First(C)={c, E} karena jika C diderivasi dari rule cC maka akan selalu dimulai dengan karakter {c} dan jika C di derivasi dengan menggunakan E maka memungkinkan untuk memiliki first set berupa E.

First(B)={a, E} karena jika B diderivasi dari rule aB maka akan selalu dimulai dengan karakter {a} dan jika B di derivasi dengan menggunakan E maka memungkinkan untuk memiliki first set berupa E.

Berikutnya mencari First dari S. Jika S diderivasi menggunakan grammar Bb maka terminal set yang mungkin menjadi awalan dari S sama dengan terminal set dari B, maka First(S)=First(B)={a, E}. Jika B merupakan E maka S dapat diderivasi langsung menjadi {b}, sehingga dari grammar S -> Bb kita akan memperoleh first set {a, b}. Kemudian lihat lagi dari grammar berikutnya yaitu S -> Cd dimana jika S diderivasi menggunakan aturan ini maka terminal set yang mungkin muncul menjadi awalan dari S adalah sama dengan terminal set dari awalan C, yaitu First(S)=First(C)={c, E}. Jika C bernilai E maka S dapat diderivasi menjadi d saja sehingga {d} termasuk kedalam terminal set dari first(S). Jadi First(S)={a, b, c, d}.

Untuk mencari Follow set kita akan memulai dari variable S dan mencari kemunculan S di sisi kanan (RHS). Dari contoh ini tidak ditemukan kemunculan S di RHS, maka follow(S) adalah {$} saja karena S merupakan start symbol.

Kemudian kita akan mencari Follow(B) dengan melihat kemunculan B pada RHS. B muncul di dua aturan, yaitu S -> Bb dan B -> aB.  Perhatikan aturan yang pertama terlebih dahulu (S -> Bb). Dari grammar tersebut bila S diderivasi maka setelah variable B akan diikuti oleh karakter {b}, oleh karena itu follow(B)={b}. Sedangkan untuk aturan yang kedua B -> aB, B terletak dipaling kanan dari aturan yang ada, sehingga mengikuti aturan dari follow(B)=Follow dari variable produksinya (saat ini adalah B), sehingga Follow(B)=Follow(B) sehingga follow(B) hanyalah {b}.

Untuk mencari Follow(C) dapat dilihat pada kemunculan C pada aturan S -> Cd dan C -> cC. Hal ini sama dengan sewaktu pencarian Follow(B) dimana Follow(C) pada aturan S -> Cd adalah {d} dan Follow(C)=Follow(C) pada aturan C -> cC. Jadi Follow(C) hanyalah {c} saja.

	First	Follow
S -> Bb | Cd	{a, b, c, d}	{$}
B -> aB | E	{b}	{b}
C -> cC | E	{d}	{c}