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