37
b. Bottom-up parsing
Pada
teknik
ini,
d
imulai
den gan kata-kata
dan
mencar i
tree
dengan ak ar S. Formulasi dar i bottom-up parsing adalah
sebagai
berikut:
•
Initial
state
adalah daftar d ari kata-kata d alam
inpu t
string,
masin g-masin g
ditamp ilkan
sebagai
parse
tree
y
ang
merup akan
node
daun
tunggal
–
contohny a:
[the,
wumpus,
is,
dead].
Pada
umumny a,
setiap
state
dalam
search
space
adalah d aftar dari parse tree.
•
Successor function mencari p ada setiap p osisi i dalam daftar
tree
dan
setiap
aturan
sisi
kanan
dari
grammar. Jika
subsequence dari
daftar tree
dimulai den gan i sesuai den gan
sisi
kanan,
mak a
subsequence
d
igantikan
oleh
sebuah
tree
baru
y
ang k ategor iny a
merup akan
aturan
sisi
kiri
dan
anakny a adalah subsequence.
Den gan
menco cokkan,
didap atkan bahwa kategori nod e sama den gan elemen di sisi
kanan.
Seb agai
contoh
dari
Gambar
2.5,
aturan
Article
Æ
the,
sesuai
dengan
subsequence
y
ang
berisi
node
p
ertama
dari
daftar
[
the,
wumpus,
is,
d
ead],
jadi
sebuah
successor
state akan b erup a [[Article: the], wumpus, is, dead].
•
Goal
test
memer iksa
state
y
ang berisi
tree
tunggal
d
en gan
akar S.
 |