Когда я смотрю на разбор Эрли, он выглядит очень элегантно, и мне интересно, почему методы GLR становятся популярными? Кто-нибудь знает, что не так с парсингом Эрли, который Томита создал GLR? Представление? Любые публикации по этой дискуссии высоко ценится.
11
Ответы:
Лучше поздно, чем никогда.
Если я правильно понимаю, Эрли работает сверху вниз и будет тратить время и память на создание предметов Эрли для каждого производства с заданным S (i). Это означает, что для естественного языка в S (0) мы создаем и проверяем элемент Earley для каждого возможного слова, начинающего предложение, и их довольно много.
Но GLR снизу вверх, поэтому при условии эффективного хеширования поиска по таблице / состоянию первый токен выбирает следующий переход (ы) за постоянное время.
Это верно специально для естественных языков, с огромным количеством отдельных произведений. Но это не очень важно для языков программирования с очень небольшим набором произведений.
источник