Stablo parsiranja

Stablo parsiranja ili konkretno sintaksno stablo ili generativno stablo je stablo koje predstavlja sintaksnu strukturu niza znakova (simbola) prema nekoj formalnoj gramatici. Program koji proizvodi takva stabla se zove parser. Stabla parsiranja mogu biti generirana za rečenice prirodnih jezika, kao i prilikom prevođenja jezika, poput npr. programskih jezika.

Osnovni opis

uredi

Stablo parsiranja čine čvorovi i grane. Donja slika predstavlja lingvističko stablo parsiranja koje predstavlja valjanu rečenicu engleskog jezika. Stablo parsiranja jest prikazana stablasta struktura, počinjući od korijena S i završujući u svakom od listova (John, ball, the, hit).

 
Jednostavno stablo parsiranja

U stablu parsiranja čvor može biti korijenski čvor ili korijen, čvor grananja, te listovni čvor ili kraće list. U gornjem je primjeru S korijen, NP i VP su čvorovi grananja, dok su listovi John, ball, the i hit.

Pozicijski odnos čvorova stabla može biti ustanovljen korištenjem termina roditelj i dijete. Roditeljski čvor ili roditelj je čvor koji ima bar jedan čvor povezan granom razinu ispod njega u stablu. U gornjem primjeru, S je roditelj čvorova NP i VP. Dijete je onaj čvor koji ima barem jedan čvor razinu iznad sebe u stablu i s kojim je povezan odgovarajućom granom. U našem primjeru, hit je dijete čvora V.

Vidjeti također

uredi
Nedovršeni članak Stablo parsiranja koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.