Hello World!

1. Kenapa harus dihilangkan left recursive dan left-factoring sebelum melakukan top down parsing?

Jawab :

dihilangkan left recursive dan left-factoring sebelum melakukan top down parsing karena berbagai alasan dibawah ini antara lain :

(left recursive)

1. Dalam praktik , jika ada right-hand side dari produksi yang left recursive, harus ada paling tidak satu nonrecursive right-hand side untuk non terminal yang sama.
   Contoh : ada grammar yang berbentuk S à S α, semua derivasi yang menggunakan produksi tersebut akan mengulang terus menerus atau looping forever seperti :
   
   Jadi diperlukan nonrecursive right-hand side dari S untuk mengakhiri derivasi.
2. Produksi left-recursive akan menyebabkan parsing mengalami looping tak hingga / infinite loop.

(Left Factoring)
Jika tidak dilakukan , akan terjadi ambigu karena terdapat non-terminal yang sama muncul 2 kali pada sisi kanan produksi.

References :

Alfred V. Aho
Ravi Sethi
Jeffrey D. Ullman
Compilers, Principles, Techniques, and Tools
1986(Reprinted 1988)
Addison-wesley publishing company

2. Jelaskan perbedaan Top Down Parsing dan Bottom Up Parsing serta mana yang lebih baik? Dan buktikan!

Perbedaan antara Top Down Parsing dan Bottom Up Parsing:

Top Down Parsing menggunakan asumsi untuk mengecek kebenaran parsing (parsing dilakukan dari root)) sedangkan Bottom Up mencocokkan rules dengan string, bila terjadi kesalahan maka akan dilakukan backtrack (Parsing dilakukan dari leaves).

Top Down memiliki kelebihan:

– Menemukan hasil lebih cepat jika pencarian tepat.

– Tidak perlu mengecek setiap node.

Top Down memiliki kelemahan:

– Jika terjadi Left Rekursif akan looping forever.

– Tidak efadalahien karena harus menyimpan hasil pencarian sebelumnya.

– Algoritma lebih sulit.

Bottom Up memiliki kelebihan:

– Semua kemungkinan pasti ditelusuri.

– Mendapatkan hasil yang lebih akurat.

– Lebih mudah dimengerti oleh manusia.

– Tidak akan terjadi looping forever (pasti berhenti).

Bottom Up memiliki kelemahan:

– Lambat karena harus mengecek satu per satu jika salah satu maka harus backtrack.

– Time complexity besar.

– Menggunakan memori besar.

Jadi Bottom Up lebih baik dibandingkan dengan Top Down sehingga parser generator lebih banyak menggunakan Bottom Up

Pembuktian pekerjaan yang dilakukan oleh Top Down dan Bottom Up:

Grammar:

Top Down Parsing

String : acddf.

Dengan Top Down Parsing kita mengasumsikan string cocok dengan S. Kita tahu bahwa string akan mungkin cocok dengan xyz atau aBC. Dalam kasus ini kita tahu string acddf tidak cocok dengan xyz tetapi akan cocok dengan aBC, sehingga kita perlu membuktikannya.

Langkah-langkah:

• Langkah 1: acddf cocok dengan S
  • Langkah 2: acddf cocok dengan xyz -> salah
  • Langkah 2: acddf cocok dengan aBC misalnya cddf cocok dengan BC:
    • Langkah 3: cddf cocok dengan cC misalnya ddf cocok dengan C:
      • Langkah 4: ddf cocok dengan eg -> salah.
      • Langkah 4: ddf cocok dengan df -> salah.
    • Langkah 3 adalah salah maka coba yang lain.
    • Langkah 3: cddf cocok dengan cdC misalnya df cocok dengan C:
      • Langkah 4: df cocok dengan eg -> salah.
      • Langkah 4: df cocok dengan df -> benar.
      • Langkah 4 adalah benar.
    • Langkah 3 adalah benar.
  • Langkah 2 adalah benar.
• Langkah 1 adalah benar. Berhasil!

Bottom Up Parsing

Bottom Up Parsing mulai melakukan parse tree dari leaves (nodes). Pada akhir string, semuanya harus digabungkan menjadi S dan hanya S yang hanya tersisa. Jika tidak, maka harus dilakukan backtrack dan mencoba mengkombinasikan dalam cara yang lain. Dengan Bottom Up Parsing, kita mengurangi sebanyak mungkin node untuk menjadi token yang lebih besar.

Contoh

String : acddf.

Langkah-langkah:

• ε tidak bias direduksi.
• a tidak bias direduksi.
• ac bisa direduksi, sebagai berikut:
• Reduksi ac to aB
  • aB tidak bisa direduksi.
  • aBd tidak bisa direduksi.
  • aBdd tidak bisa direduksi.
  • aBddf tidak bisa direduksi.
  • Akhir dari String. Stacknya adalah aBddf, bukan S. Gagal! Harus backtrack.

• ac tidak bias direduksi.
• acd dapat direduksi, sebagai berikut:
• Reduksi acd to aB
  • aB tidak bisa direduksi.
  • aBd tidak bisa direduksi.
  • aBdf bisa direduksi, sebagai berikut:
  • Reduksi aBdf to aBC
    • aBC bisa direduksi, sebagai berikut:
    • Reduksi aBC to S
      • Akhir dari String. Stack adalah S. Berhasil!

References :

J. P. Bennett
Introduction to Compiling Techniques
1996
McGraw-Hill(A Division of The McGraw-Hill Companies)

3. Buatlah 1 case untuk melakukan proses syntax analyzer? (dengan Coding) dalam bentuk output list operand & operator.

Syntax Analyzer Application Source code dowload link : http://willypt.com/YkZQDqCpvV.file

Syntax Analyzer Application : http://willypt.com/tekkom/

References :
Compilers – Principles, Techniques, and Tools
by Alfred V.Aho , Ravi Sethi , Jeffrey D.Ullman

Thanks for the teamwork guys,

www.binus.ac.id