44
yang
menarik
dari Earley
parser
adalah
karena
dapat
mem-
parsing
semua
bahasa
dalam
konteks
yang bebas.
Waktu
eksekusi
dari Earley
parser
berjalan
dalam
waktu
kompleksitas.
Waktu
komplesitas
adalah
jumlah
waktu yang
dibutuhkan
oleh sebuah
algoritma
untuk
menjalankan
sebagai
fungsi
dari ukuran
masukan
untuk
masalah
ini, dan
waktu
kompleksitas dari
suatu
algoritma biasanya dinyatakan
menggunakan
notasi
O
besar,
Cubic
time
(O
(n
3
),
di
mana
n
adalah panjang string yang diurai) dalam kasus umum,
quadratic
time
(O
(n
2
)) untuk
tata
bahasa
yang
ambigu,
dan
linear
time
untuk
hampir
semua
LR (k) tata
bahasa.
Earley
parser
dapat
bekerja
secara
optimal
ketika
aturan
tertulis
secara rekursif kiri.
Pada
sumber
tertentu,
algoritma
Earley
merupakan
baik
algoritma bottom-up
yang
menggabungkan beberapa
elemen
prediksi
top-down,
maupun
algoritma
prediksi
top-
down yang memiliki
pemeriksaan
bottom-up.
Dengan
demikian,
algoritma
Earley terlihat
seperti perkawinan
antara
pendekatan bottom-up
dan top-down.
Dari akar bottom-up,
Earley
menjaga
runtime
untuk
kasus
terburuk pada
(O
(n
3
),
tetapi
karena
kekuatan
dari elemen
prediksi
top-down,
dalam
banyak
kasus
memiliki
runtime
pada
O(n).
(Sandstrom,
2004,
p4).
 |