25
CFG, terutama dalam ilmu komp uter. Batasan formal y ang tidak tertan gkap
oleh grammar
kemudian d ip ertimbangk an sebagai b agian d ari b ahasa
semantik.
CFG
cukup
sederhana
untuk
memp erbolehkan
p
embentukan
algoritma parsing y ang efisien. M isalny a untuk string y ang diberik an, CFG
menentukan
ap akah
dan
bagaiman a
string
tersebut
dap at
dihasilkan
d
ari
grammar. Earley parser merup akan contoh dari algoritma tersebut.
CFG G merup akan sebuah 4-tuple (deretan nilai) :
G
=
(V, ?, R, S) di mana
1. V
adalah
kump ulan
terbatas dari
karakter
nonterminal
atau
variabel,
merep resentasikan tip e berbeda dari frase atau klausa dalam k alimat.
2. ? adalah
kump ulan
terbatas dari
terminal,
men ggambarkan
isi
y
ang
sebenarny a dari kalimat.
3. R
adalah
relasi
d
ari
V
samp ai
sep erti
4. S
adalah
variab el
start,
d
igunakan
untuk
merep resentasikan
keseluruhan kalimat (atau p rogram). M erup akan elemen dar i V.
M
enurut
Russel dan Norvig (2003, p p 795-797),
sebelum membu at
suatu
grammar
(misalny a
dalam
fragmen
In ggris),
p
ertama
didefin isikan
lexicon
terleb ih
dahulu. Lexicon
ad alah
d
aftar
dari
k
ata-kata
y
ang
diizinkan. Kata-kata ini
dikelomp okkan ke dalam kategor i atau bagian dari
 |