Русские вычислители

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Русские вычислители » Вычислители по-русски » Алгоритм Эрли


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

Сообщений 1 страница 3 из 3

1

Предлагаю пообсуждать алгоритм Эрли 1970-года.

В сети есть много работ по его расширению на случай контекстно-зависимых грамматик.

Ещё у меня есть мысль, что компилятор имеет право ошибаться при анализе текста программы.
Сейчас компиляторы не ошибаются, но "в любой программе есть ошибка". Если компиляторы получат право на ошибку - ничего не поменяется, а возможности увеличатся.

В википедии описания алгоритма на русском языке нет, но есть такое:
http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf

То есть план такой:
1) сначала разобраться как реализовывать алгоритм Earley;
2) потом рассмотреть современные развития этого алгоритма применительно к естественным языкам
(типа такого - https://courses.cit.cornell.edu/ling771 … earley.pdf);
3) потом сделать парсер с учётом падежей и структуры предложений.

Отредактировано ВежливыйЛис (04.04.2016 11:36:31)

0

2

Все контекстно свободные языки провалились. Из-за своей сложности в освоении пользователями(программистами).
И время компиляции возрастает с линейной до квадратичной.  И потребление памяти!

Если вы уже разобрались со стековым парсером, то для вас алгоритм будет простым. В отличие от LR и RR. Выбор между сверткой и наталкиванием в стек делается путём перебора возможных вариантов.

0

3

Павиа написал(а):

Все контекстно свободные языки провалились.


зависимые.

Парсер perl называется marpa и выбран в качестве референсной реализации, он основан на Earley+SPPF.

Павиа написал(а):

И время компиляции возрастает с линейной до квадратичной


Существуют разные оценки сложности - в худшем случае, в среднем случае.

Для типовых грамматик сложность линейная, было проведено тестирование в сообществе RSDN, вычислили константу.
Я считаю, что константа - это малая плата за удобство.

Отредактировано ВежливыйЛис (04.04.2016 12:39:34)

0


Вы здесь » Русские вычислители » Вычислители по-русски » Алгоритм Эрли


форум на 24bb Создать форум бесплатно