Ketika saya melihat parsing Earley, itu terlihat sangat elegan, dan saya bertanya-tanya mengapa teknik GLR menjadi populer? Adakah yang tahu apa yang salah dengan Earley parsing yang Tomita buat GLR? Performa? Setiap publikasi pada diskusi ini sangat dihargai.
11
Jawaban:
Lebih baik terlambat daripada tidak sama sekali.
Jika saya mengerti dengan benar, Earley adalah top-down, dan akan menghabiskan waktu dan memori membuat item Earley untuk setiap produksi pada S (i) yang diberikan. Ini berarti bahwa untuk bahasa alami, dalam S (0) kami membuat dan memeriksa item Earley untuk setiap kata yang mungkin memulai kalimat, dan ada cukup banyak.
Tetapi GLR adalah bottom-up, sehingga dengan asumsi pencarian tabel / state hash yang efisien, token pertama memilih transisi berikutnya dalam waktu yang konstan.
Ini berlaku khusus untuk bahasa alami, dengan sejumlah besar produksi yang berbeda. Tetapi tidak terlalu berarti untuk bahasa pemrograman, dengan rangkaian produksi yang sangat kecil.
sumber