People Innovation Excellence
 

Teknik Kompilasi : FOLLOW SET PADA TOP DOWN PARSING

Pada saat mau melakukan metode Top Down Parsing, langkah yang perlu kita lakukan setelah menentukan FIRST Set adalah menetukan FOLLOW SET pada grammar-grammar yang ada. FOLLOW (B) dimana B adalah non teriminal adalah himpunan simbol terminal yang mengikuti atau tepat di sebelah kanan B dalam string yang diderivasi dari start symbol.

Berikut rules yang digunakan untuk menentukan FOLLOW SET:

  1. Jika, S → Ab | C, dan S adalah start symbol maka $ adalah FOLLOW (S)
  2. Jika, A → aBb adalah sebuah production rule, maka semua FIRST (β) adalah FOLLOW (B) kecuali ε
  3. a. Jika, A → aB adalah sebuah production rule, maka semua yang FOLLOW (A) adalah FOLLOW (B)
    b.  Jika, A → aBb adalah sebuah production rule, dan FIRST (β) adalah ε, maka  semua yang FOLLOW (A) adalah FOLLOW (B)
    (untuk mencari FOLLOW kita hanya dapat mencari berdasarkan grammar yang berada di atas grammar yang kita cari)

Untuk lebih jelasnya dapat dilihat di contoh berikut ini:

  1. K à  LK’
  2. K’à /LK’ | Ɛ
  3. L à  ML’
  4. L’ à -ML’ | Ɛ
  5. M à +M | (K) | x | y

Dimana :

FIRST (K) = +, (, x, y
FIRST (K’) = /, ε
FIRST (L) = +, (, x, y
FIRST (L’) = -,  ε
FIRST (M) = +, (, x, y

Maka :

FOLLOW (K) = $, )

Dapat dilihat dari penjelasan berikut :

  • Rule nomor 1, K adalah start symbol maka $ adalah FOLLLOW (K)
  • Pada M à +M | (K) | x | y, tepat di sebelah kanan non terminal K terdapat symbol ), maka ) adalah FOLLOW (K)

FOLLOW (K’) = $, )

Dapat dilihat dari penjelasan berikut :

  • Rule nomor 3a diaplikasikan pada grammar ke-1 yang mengadung huruf K’, K à  LK’,  maka semua yang FOLLOW (K) adalah FOLLOW (K’), maka $ dan ) adalah FOLLLOW (K’).

FOLLOW (L) = /, $, )

Dapat dilihat dari penjelasan berikut :

  • Rule nomor 2 diaplikasikan pada grammar ke-2 yang mengadung huruf L, K’à /LK’,  FIRST (K’) selain ε adalah /, maka / adalah FOLLLOW (L’).
  • Rule nomor 3b diaplikasikan pada grammar ke-2 yang mengadung huruf L, K’à /LK’,  FIRST (K’) adalah ε, maka semua yang FOLLOW (K’) adalah FOLLOW (L), maka $ dan ) adalah FOLLLOW (L’).

FOLLOW (L’) = /, $, )

Dapat dilihat dari penjelasan berikut :

  • Rule nomor 3a diaplikasikan pada grammar ke-3 yang mengadung huruf L’, L à  ML’,  maka semua yang FOLLOW (L) adalah FOLLOW (L’), maka /, $ dan ) adalah FOLLLOW (L’).

FOLLOW (M) = -, /, $, )

Dapat dilihat dari penjelasan berikut :

  • Rule nomor 2 diaplikasikan pada grammar ke-4 yang mengadung huruf M, L’ à -ML’,  FIRST (L’) selain ε adalah -, maka – adalah FOLLLOW (M).
  • Rule nomor 3b diaplikasikan pada grammar ke-4 yang mengadung huruf M, L’ à -ML’,  FIRST (K’) adalah ε, maka semua yang FOLLOW (L’) adalah FOLLOW (M), maka /, $ dan ) adalah FOLLLOW (M).

Published at : Updated
Written By
Alvina Aulia, S.Kom., M.T.I
Subject Content Coordinator Software Development | School of Computer Science

Periksa Browser Anda

Check Your Browser

Situs ini tidak lagi mendukung penggunaan browser dengan teknologi tertinggal.

Apabila Anda melihat pesan ini, berarti Anda masih menggunakan browser Internet Explorer seri 8 / 7 / 6 / ...

Sebagai informasi, browser yang anda gunakan ini tidaklah aman dan tidak dapat menampilkan teknologi CSS terakhir yang dapat membuat sebuah situs tampil lebih baik. Bahkan Microsoft sebagai pembuatnya, telah merekomendasikan agar menggunakan browser yang lebih modern.

Untuk tampilan yang lebih baik, gunakan salah satu browser berikut. Download dan Install, seluruhnya gratis untuk digunakan.

We're Moving Forward.

This Site Is No Longer Supporting Out-of Date Browser.

If you are viewing this message, it means that you are currently using Internet Explorer 8 / 7 / 6 / below to access this site. FYI, it is unsafe and unable to render the latest CSS improvements. Even Microsoft, its creator, wants you to install more modern browser.

Best viewed with one of these browser instead. It is totally free.

  1. Google Chrome
  2. Mozilla Firefox
  3. Opera
  4. Internet Explorer 9
Close