- Алгоритм Эрли
-
Алгори́тм Э́рли (англ. Earley) — алгоритм синтаксического анализа предложения по контекстно-свободной грамматике, основанный на методе динамического программирования. В отличие от алгоритма Кока — Янгера — Касами, который требует приведения грамматики к нормальной форме Хомского, алгоритм Эрли привлекателен тем, что не накладывает ограничений на используемую для анализа контекстно-свободную грамматику. Алгоритм Эрли работает по принципу «сверху-вниз», то есть строит возможные деревья разбора предложения начиная с вершины.
См. также
- Алгоритм Кока — Янгера — Касами — еще один
-алгоритм для разбора любой контекстно-свободной грамматики.
Литература
- J. Earley, "An efficient context-free parsing algorithm", Communications of the Association for Computing Machinery, 13:2:94-102, 1970.
Категории:- Синтаксический анализ
- Динамическое программирование
- Алгоритм Кока — Янгера — Касами — еще один
Wikimedia Foundation. 2010.