Korai algoritmus
Az Earley - algoritmus egy környezetfüggetlen nyelvtani mondatelemző algoritmus , amely a dinamikus programozási módszeren alapul . Ellentétben a Kok-Younger-Kasami algoritmussal , amely megköveteli, hogy a nyelvtant Chomsky-féle normálformára redukálják , Early algoritmusa vonzó, mivel nem szab korlátozásokat az elemzéshez használt kontextusmentes nyelvtanra. Emellett a Kok-Younger-Kasami algoritmus alulról felfelé haladva működik, azaz felülről kiindulva építi fel a lehetséges mondatelemző fákat. Ezzel szemben az Early algoritmusa balról jobbra haladó következtetési stratégiát valósít meg.
Linkek
Lásd még
- A Kok-Younger- Kasami algoritmus egy másik -algoritmus bármely környezetfüggetlen nyelvtan elemzéséhez .
Irodalom
- J. Earley, "An efficient Context-free parsing algorithm" , Communications of the Association for Computing Machinery , 13 :2:94-102, 1970.