Разбор пакетов по сравнению с анализом LALR

Question

Многие веб-сайты утверждают, что парсеры пакетов могут анализировать ввод за линейное время.
Так что на первый взгляд они могут быть быстрее, чем парсер LALR, созданный инструментами yacc или bison.знать, лучше или хуже производительность анализаторов пакетов, чем производительность анализатора LALR при тестировании с общим вводом (например, с исходными файлами языка программирования), а не с какими-либо теоретическими входами.два подхода.
Спасибо!

Answer 1

Я не эксперт в разборе пакетов, но вы можете узнать больше на Грамматика синтаксического анализа выражений в Википедии .

Я не копался в этом, поэтому предположу, чтохарактеристика линейного времени синтаксического разбора пакетов верна.

L (AL) R парсеры также линейные парсеры времени.Таким образом, теоретически, ни packrat, ни L (AL) R парсеры не «быстрее».

На практике, конечно, важна реализация.Переходы состояний L (AL) R могут быть выполнены в очень немногих машинных инструкциях («посмотрите код токена в векторе, получите следующее состояние и действие»), поэтому они могут быть чрезвычайно быстрыми на практике.«Компилируя» разбор L (AL) R в машинный код, вы можете получить молниеносные парсеры, как показано в этой статье Тома Пеннелло 1986 года об очень быстром разборе LR .(Машины теперь на 20 лет быстрее, чем когда он написал статью!).

Если парсеры Packrat сохраняют / кэшируют результаты по ходу, они могут иметь линейное время, но я быдумаю, постоянные издержки будут довольно высокими, и тогда парсеры L (AL) R на практике будут намного быстрее.Реализации YACC и Bison из того, что я слышал, довольно хороши.

Если вам небезразличен ответ, внимательно прочитайте основные технические документы;если вы действительно заботитесь, то реализуйте по одному из каждого и проверьте служебные константы.Мои деньги сильно на L (AL) R.

Наблюдение: большинство языковых интерфейсов не проводят большую часть своего времени "в разборе";скорее они проводят много времени в лексическом анализе.Оптимизируйте это (ваша биография говорит, что вы есть), и скорость парсера не будет иметь большого значения.

(Я использовал для создания генераторов парсера LALR и соответствующих парсеров. Я больше не делаю этого; вместо этого я использую GLR-парсеры , которые на практике имеют линейное время, но обрабатывают произвольные грамматические выражения без контекста. Я теряю некоторую производительность, но я могу [и знаю, смотри био] создавать десятки парсеров для многих языков без особых проблем.).

Answer 2

Я являюсь автором LRSTAR, генератора парсера LR (k) с открытым исходным кодом. Поскольку люди проявляют интерес к нему, я разместил продукт здесь онлайн LRSTAR .

Я много лет изучал скорость парсеров LALR и лексеров DFA. Работа Тома Пеннелло очень интересна, но это скорее академическое упражнение, чем реальное решение для компиляторов. Однако, если все, что вам нужно, это распознаватель образов, то это может быть идеальным решением для вас.

Проблема заключается в том, что реальным компиляторам обычно нужно делать больше, чем распознавание образов, например, поиск в таблице символов для входящих символов, восстановление после ошибок, предоставление списка ожидающих (информация о завершении оператора) и создание абстрактного синтаксическое дерево при разборе.

В 1989 году я сравнил скорость синтаксического анализа синтаксических анализаторов LRSTAR с "yacc" и обнаружил, что они в 2 раза превышают скорость синтаксических анализаторов "yacc". Парсеры LRSTAR используют идеи, опубликованные в статье: «Оптимизация таблиц парсеров для переносных компиляторов».

Что касается скорости лексера (лексического анализа), я обнаружил в 2009 году, что «re2c» генерирует самые быстрые лексеры, примерно в два раза быстрее, чем те, которые генерирует «flex». В то время я переписывал секцию генератора лексеров LRSTAR и нашел способ сделать лексеры почти такими же быстрыми, как «re2c», и намного меньше. Однако я предпочитаю лексеры, управляемые таблицами, которые генерирует LRSTAR, потому что они почти такие же быстрые, а код компилируется намного быстрее.

Кстати, внешние интерфейсы компилятора, сгенерированные LRSTAR, могут обрабатывать исходный код со скоростью 2400000 строк в секунду или быстрее. Сгенерированные LRSTAR лексеры могут обрабатывать 30 000 000 токенов в секунду. Тестируемый компьютер представлял собой машину с частотой 3,5 ГГц (с 2010 года).

Answer 3

[2015/02/15] вот статья Тома Пеннелло 1986 года об очень быстром разборе LR

http://www.genesishistory.org/content/ProfPapers/VF-LRParsing.pdf

Answer 4

Я знаю, что это старый пост, но примерно месяц назад я наткнулся на этот документ: https://www.mercurylang.org/documentation/papers/packrat.pdf и случайно увидел этот пост сегодня.

Разбитая версия этогогазета говорит: запоминание пакета - смешанное благословение.Наилучших результатов можно достичь, если у вас есть эвристика относительно того, как часто будет соответствовать это или другое правило.По сути, имеет смысл запомнить правила, которые имеют два следующих свойства: (1) несколько элементов, (2) очень часто встречающиеся.

Answer 5

Производительность в основном зависит от языкового дизайна.Для каждого языка найдется подход, технология или генератор синтаксического анализатора, который лучше всего подойдет.

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