First set

Pembangunan parser prediktif dibantu oleh dua fungsi yang terkait dengan sebuah grammar G. Fungsi tersebut yaitu FIRST dan FOLLOW, yang memungkinkan kita untuk mengisi entri tabel parsing prediktif untuk G, bila memungkinkan. Himpunan token yang dihasilkan oleh fungsi FOLLOW juga dapat digunakan sebagai sinkronisasi token selama perbaikan error panic-mode.

FIRST(alfa)
Jika alfa adalah setiap string simbol grammar, jadikan FIRST(alfa) sebagai himpunan dari terminal yang memulai string berasal dari alfa. Jika alfa ->empty string, maka empty string juga ada di dalam FIRST (alfa).


Untuk menghitung FIRST(X) untuk semua grammar simbol X, terapkan aturan berikut sampai terminal tidak lebih atau empty string dapat ditambahkan ke setiap set FIRST:
1. Jika X adalah terminal, maka FIRST(X) adalah {X}
2. Jika X -> empty string adalah sebuah production, kemudian tambahkan empty string ke FIRST(X).
3. Jika X adalah non-terminal dan X -> Y1 Y2...Yk adalah production, maka tempatkan a pada FIRST(X) jika untuk beberapa i, a adalah FIRST(Yi), dan empty string berada pada semua  FIRST(Y1) , ... ,  FIRST(Yi-1) , yaitu  Y1 , ... ,  Yi-1  => empty string. Jika empty string adalah  FIRST(Yj) untuk semua j = 1, 2, ... , k, kemudian tambahkan empty string untuk FIRST(X).
Sebagai contoh, segala sesuatu dalam  FIRST(Y1)  pasti berada di  FIRST(X) . Jika  Y1  tidak berasal empty string, maka kita tidak menambahkan apa-apa lagi untuk  FIRST(X) , tetapi jika  Y1  => empty string, maka kita tambahkan  FIRST(Y2)  dan sebagainya.

Sekarang, kita dapat menghitung FIRST untuk setiap string  X1 X2...Xn  sebagai berikut.
Tambahkan ke FIRST( X1 X2...Xn) semua simbol non-empty string dari  FIRST( X1) . Juga menambahkan simbol non-empty string dari  FIRST(X2)  jika empty string-nya berada pada FIRST( X1) , simbol non-empty string dari  FIRST(X2) , jika empty string berada di kedua  FIRST( X1) dan  FIRST(X2), dan sebagainya. Akhirnya, tambahkan empty string ke  FIRST( X1 X2...Xn)  jika, untuk semua i,  FIRST(Xi) berisi empty string.

Contoh..
Perhatikan grammar ekspresi berulang di bawah ini:
E -> T E’
E’-> + T E’ | empty string
T -> F T’
T’-> * F T’ | empty string
F -> ( E ) | id

maka:
FIRST(E) = FIRST(T) = FIRST(F) = {( , id}
FIRST(E’) = {+,  empty string }
FIRST(T’) = {*,  empty string }

Baca yang Follow set..