Здравствуйте, vdimas, Вы писали:
V>Сравнимой — это когда не в разы, а на единицы или десяток-другой процентов.
V>Цифры разницы на своих данных я давал.
Я не знаю, что ты там за цифры давал. Но на свете нет ни одного GLR-а пригодного для промышленного использования. У них и с производительностью проблемы, и с восстановлением после ошибок. Они только для научных эксперементов и детских поделок годятся.
Если я ошибаюсь, дай ссылок.
V>Т.е., когда лексер-парсер работают в паре, то лексический анализатор занимает львиную долю тиков процессора из затрат на парсинг (формирование AST — это, считай, "отдельная" нагрузка). Т.е. синтаксический анализ занимает меньшую долю тиков в совместной работе.
Слушай читать твои фантазии у меня никакого желания нет. Рассуждения настолько не серьезные, что надо начинать разжевывать тебе все детали, чтобы что-то объяснит. Но учитывая, что ты слушать то не намерен — это совсем уж бесполезное время препровождение.
Само наличие лексера сокращает число этих самых тактов на порядки. Парсеру приходится работать не с миллионами символов, а с тысячами или даже сотнями. Число неоднозначностей падает с тысяч, до единиц или даже нуля.
Но сам лексер работает просто на порядки быстрее. "Отлексить" с помощью качественного компилированного кода основанного на ДКА даже десятимегабайтный файл — это денницы миллисекунд. А вот парсинг того же самого — это совсем другой расклад.
V>Потому что трафик символов разный, ес-но.
Ты говоришь полную чушь! Трафик ничто по сравнению с вычислительными затратами. Даже сложност грамматики резко менят расклад. Например, грамматика препроцессора шарпа отрабатывает так быстро, что ее можно даже не брать в расчет при парсинге.
А главное, что GLR (ну, если это реально GLR, а не что нибудь) являются безлексерными и разбирают отдельные символы далекими от эффективности алгоритмами.
VD>>А GLR привносит еже оверхэд.
V>Только на неоднозначностях.
Хрен там. У них и константа во много раз выше. Не может быть обобщенный алгоритм столь же эффективным, как специализированный. Вот ДКА ты хрен когда догонишь. Хот ты лопни.
Плюс ты похоже не понимаешь принципов работы GLR-ов. Они сворачивают продункции в обратную сторону, так что промежуточные свортки им надо как-то хранить. Они обязательно оперируют структурой лесов. Все это не бесплатно.
V>Почитай внимательно вот это:
V>https://ru.wikipedia.org/wiki/LR(0)
Спасибо. Читай это сам. И за одно запомни LR(0) это совсем не GLR. LR(0) не распарсит даже C#.
V>Обрати внимание, что по если по каждой свертке у нас будет конечный (выходной) нетерминал, то получаем в точности автоматный лексер.
Языком в основном. На практике код там будет долек от того, что можно сгенерировать для ДКА. А попытка жрать символы ЛР-ом приведет к неоднозначностям на ровном месте. GLR, конечно, их разрулит, но обойдется тебе это не дешево.
V>В этом случае содержимое "стека" — это цепочка-значение разобранной лексемы.
Языком. Языком.
V>Теперь представь, ...
Не хочу. Мне время дорого. Приведи тесты GLR vs лексер и за одно дай ссылки те самые С++-парсеры, которые используют GLR для разбора С++. Потом поговорим. А до тех пор не убивай мое время, плиз.
V>Именно так насчет сложности:
V>V>Алгоритм GLR в худшем случае имеет такую же сложность, как алгоритм Кока — Янгера — Касами и алгоритм Эрли — O(n³). Однако, у GLR-алгоритма имеется два преимущества:
V>* Время, необходимое для выполнения алгоритма, пропорционально степени недетерминированности исходной грамматики — при полностью детерминированной грамматике GLR-алгоритм работает за O(n). (Для Earley- и CYK-алгоритмов это не так, хотя оригинальный алгоритм Earley может быть модифицирован для получения такого же преимущества).
V>* Алгоритм GLR «оперативный» (it is on-line) — считывая каждый символ из входного буфера, он производит как можно больше работы по анализу доступной по прочтению данной входной последовательности.
Блин, клинический детский сад! Открой для себя понятие константы. Тогда узнаешь, что линейное != быстрое. Если ты на разбор символа в потоке тратишь секунду, то твой алгоритм линейный, но он никому не нужный, так как даже на 100 символов ты потратишь неприемлемо много времени. Вот именно это и происходит со всеми G.
И еще задумайся на фиг нужен GLR, если грамматика полностью детерминирована?
Вот мы используем модифицированный Эрли для качественного восстановления после ошибок. При этом числ неоднозначностей растет просто лавинообразно. Но по другому нельзя, так как только обобщенный алгоритм может найти все пути.
V>Поэтому, я не просто говорил про GLR, я говорил о сценариях, где он очень хорошо себя показывает.
Нет таких сценариев на практике. GLR используется исключительно в научных целях. Я просто ржал читая научные статьи где на полном серьезе говорилось об восстановлении после ошибок за 10 секунд. Успехов всем кто готов ждать отклика редактора по 10 секунд.
V>И то, что он требует — тоже именно оно, чтобы иметь возможность найти сценарий, где GLR будет хуже некоей другой альтернативы, например, где какой-нить ПЕГ отработает вообще без откатов.
Блин. Это просто песня!
Запомни на будущее.
1. ПЕГ — это формат грамматики. Алгоритм парсинга ПЕГ-а называется Пакрат.
2. Пакрат работает без откатов на любой грамматике описываемой ПЕГ-ом.
V>Однако, где нисходящему алгоритму надо будет регулярно откатываться на много мегабайт назад, GRL рвет его как тузик грелку.
Пипец ты берд несешь! Прямо хоть в юмор выноси тему. Но, боюсь, там большинство не поймет. Весь смысл Пакрата в том, что он безоткатный, т.е. гарантирует линейное время. Вот константа у него опять же достаточно высокая. Но все же ниже чем у GRL. У нас сейчас файлы в редакторе перепарсиваются на каждый чих и производительности хватает. Хуже с восстановлением. Но и с ним в большинстве случаев все не плохо работает.
VD>>А он о константе, которая у GLR будет сушественно выше чем у ДКА.
V>Я уже говорил, суть алгоритма LR(0) — это, грубо, лексер вызывает лексер и так рекурсивно.
Пипец! Эта песня хороша, начинай сначала. Не я на тебя время тратить не буду.
