Алгоритм Эрли

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

Ссылки

JavaScript реализация алгоритма с возможностью генерации леса синтаксических деревьев (в случае неоднозначной грамматики)

См. также

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

Литература

J. Earley, "An efficient context-free parsing algorithm", Communications of the Association for Computing Machinery, 13:2:94-102, 1970.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.