36
a.
Top-down parsing
Pada teknik in i, dimulai den gan simbol S dan
mencari tree y ang
memiliki kata-kata p ada
daunny a (karena S
digambark an di
p
aling
atas dari
tree).
Top-down parsing
dap at
didefinisik an
sebagai ber ikut:
•
Initial
state
adalah
parse
tree
y
ang
berisi
ak ar
S
dan
anak
y
ang
tidak
diketahui:
[S:
?].
Pad a
umumny a,
setiap
state
dalam search space adalah sebuah parse tree.
•
Successor function memilih leftmost node dalam tree d en gan
anak
y
ang tidak
diketahui.
Kemudian
akan
mencar i
di
grammar
untuk
aturan
y
ang
memiliki
label
root
dar i
node
p
ada
sisi
kiri.
Untuk
aturan
y
ang
demik ian,
successor
function membuat
successor state di
mana ? digantikan o leh
sebuah daftar y an g sesuai p ada aturan d i sisi kanan.
Sebagai
contoh, dari
Gambar
2.6
ada dua
aturan
untuk S. Seh ingga
tree [S: ?] akan digantikan oleh du a successor berikut:
[S: [S: ?][Conjun ction : ?][S: ?]]
[S: [NP: ?][ VP: ?]]
•
Goal test
memeriksa
daun d ari
parse tree
y
ang
sesuai
dengan
tep at
untuk
input
string,
dengan
input
y
ang
tidak
diketahui dan tidak ditemuk an.
 |