38
2.5.5.2 Algoritma Earley
Earley
parser
merup akan
jenis
dari
chart
parser
y
ang
digun akan
untuk
parsing
dalam
lin gu istik
komp utasional.
Earley
parser muncul
karena
dap at
menguraikan
semua context-free
language.
Parser
ini
berjalan
dalam
cub ic
time
(O(n³),
di
mana
n
adalah p anjan g
dar i
string
y
ang
diuraikan)
d
alam
kasus umu m,
quadratic
time
(O(n²)) untuk
grammar
y
ang
ambigu,
dan
linear
time untuk
hamp ir
semua
LR(k) grammar. Parser
ini b ekerja
dengan san gat baik ketika aturan dituliskan secar a rekursif kir i.
Bergantung
p
ada sumber
tertentu,
algoritma Ear ley
merup akan
baik
algor itma
bottom-up
y
ang
men ggabun gk an
beberap a elemen p rediksi top-down,
maup un algoritma p rediksi
top-down y ang memiliki p emer iksaan bottom-up. Dengan demikian,
algoritma
Ear ley
terlihat
sep erti p erkawinan
antara p endekatan
bottom-up dan top-down. Dari akar bottom-up, Ear ley
menjaga
runtime
untuk
kasus
terburuk
p
ada
O(n³),
tetap i
karena
k
ekuatan
dari
elemen
p
rediksi
top-down,
dalam
bany ak
kasus
memilik i
runtime p ada O(n). (Sandstrom, 2004, p 4).
Berdasarkan
algoritma
Earley
ini,
p
ertama
kali
dilakukan
inisialisasi aturan top-down ber ikut
(Lop er, 2005, pp 30-33):
Untuk setiap
aturan
grammar
S
Æ
a,
maka
tambahkan
ke
queue[0].
Kemudian,
scan
dari
kir i
ke
kanan
d
en gan
menerap kan
satu dari 3 aturan ini:
 |