Почему Томита создал GLR и не использовал Эрли?

11

Когда я смотрю на разбор Эрли, он выглядит очень элегантно, и мне интересно, почему методы GLR становятся популярными? Кто-нибудь знает, что не так с парсингом Эрли, который Томита создал GLR? Представление? Любые публикации по этой дискуссии высоко ценится.

Wickoo
источник
5
GLR допускает детерминированный разбор на части грамматики. Посмотрите, например, Elkhound ( scottmcpeak.com/elkhound ), где эта идея принята. Однако для естественных языков не так ясно, что GLR лучше, чем Earley.
Сильвен
1
@Sylvain: звучит как ответ для меня ...
Джошуа Грохов

Ответы:

5

Лучше поздно, чем никогда.

Если я правильно понимаю, Эрли работает сверху вниз и будет тратить время и память на создание предметов Эрли для каждого производства с заданным S (i). Это означает, что для естественного языка в S (0) мы создаем и проверяем элемент Earley для каждого возможного слова, начинающего предложение, и их довольно много.

Но GLR снизу вверх, поэтому при условии эффективного хеширования поиска по таблице / состоянию первый токен выбирает следующий переход (ы) за постоянное время.

Это верно специально для естественных языков, с огромным количеством отдельных произведений. Но это не очень важно для языков программирования с очень небольшим набором произведений.

Джефф
источник