Teoreetilibe informaatika kordamisküsimused
CB asendan A BDB )
Iga keele jaoks leidub genereeriv grammatika Greibachi normaarkujul.
16. KV-keelte süntaksanalüüsi ülesanne. CKY-algoritm.
Cocke-Kasami-Youngeri algoritm:
Chomsky normaalkujul oleva grammatika ning terminaalse stringi korral otsustab,
kas sõna kuulub keelde või mitte.
Ühendab kõikvõimalikud tuletuspuud tuletuspäramiidiks.
Tabeli alumise astme laiuseks saab analüüsitava sõna pikkus. Tipulahtrisse peab
tekkima stardisümbol.
Vahepealsetesse lahtritesse kirjutatakse mitteterminaal parajasti siis, kui ...
Algoritmi tulemusena tekib lahtrisse mitteterminaal A, kui grammatikas G on
esitatav tuletus A xjxj+1w, sõna kuulub keelde ning tipulahtris on stardisümbol.
Keerukuseks n pikkuse sõna korral O(n3).
17. Earley algoritm.
Ülesanne: kas sõna x kuulub grammatikaga G genereeritavasse keelde L.
Üritame ehitada sõna vasaktuletust.
G produktsiooni A v võib olla kasutatud sõna w = x1x2
annaabi.ee 
