Алгори́тм Э́рли ( англ. Earley ) — алгоритм синтаксического анализа предложения по контекстно-свободной грамматике , основанный на методе динамического программирования . В отличие от алгоритма Кока — Янгера — Касами , который требует приведения грамматики к нормальной форме Хомского , алгоритм Эрли привлекателен тем, что не накладывает ограничений на используемую для анализа контекстно-свободную грамматику. Кроме того, Алгоритм Кока — Янгера — Касами работает по принципу «снизу-вверх», то есть строит возможные деревья разбора предложения начиная с вершины. В отличие от него Алгоритм Эрли реализует стратегию вывода «слева-направо».

Ссылки

См. также

• Алгоритм Кока — Янгера — Касами — ещё один ${\displaystyle O(n^{3})}$ -алгоритм для разбора любой контекстно-свободной грамматики .

Литература

• J. Earley, , Communications of the Association for Computing Machinery , 13 :2:94-102, 1970.