Существует множество различных алгоритмов синтаксического анализа (рекурсивный спуск, LL (k), LR (k), LALR,...). Я нахожу много информации о разных грамматиках, которые могут принимать разные типы парсеров. Но как они отличаются поведением во время работы? Какой алгоритм работает быстрее, использует меньше памяти или пространства стека?
Или поставить это по-другому - какой алгоритм работает лучше всего, предполагая, что грамматика может быть сформулирована для работы с любым алгоритмом?
LR парсеры ИМХО могут быть самыми быстрыми. По сути, они используют токен в качестве индекса для набора промежуточных данных или таблицы переходов, чтобы решить, что делать дальше (выдвинуть индекс состояния, выдвинуть индексы состояния/вызвать процедуру сокращения). Преобразовать в машинный код это может быть всего несколько машинных инструкций. Пеннелло подробно обсуждает это в своей статье:
Томас Дж. Пеннелло: очень быстрый разбор LR. Симпозиум SIGPLAN по компиляции 1986: 145-151
Анализаторы LL включают рекурсивные вызовы, которые немного медленнее, чем просто поиск по таблице, но они могут быть довольно быстрыми.
Парсеры GLR являются обобщениями парсеров LR и, следовательно, должны быть медленнее, чем парсеры LR. Ключевое наблюдение состоит в том, что большую часть времени анализатор GLR действует точно так же, как и анализатор LR, и можно заставить эту часть работать по существу с той же скоростью, что и анализатор LR, поэтому они могут быть довольно быстрыми.
Ваш синтаксический анализатор, вероятно, будет тратить больше времени на разбиение входного потока на токены, чем на выполнение алгоритма синтаксического анализа, поэтому эти различия могут не иметь большого значения.
С точки зрения приведения вашей грамматики в удобную форму, следующий порядок, в котором технологии синтаксического анализа "упрощают":
Я провел исследование скорости синтаксического анализатора LR между LRSTAR и YACC.
В 1989 году я сравнил таблицы синтаксического анализатора, определенные в статье "Оптимизация таблиц синтаксического анализа для переносимых компиляторов", с таблицами синтаксического анализатора YACC (структура гребенки). Это таблицы LR или LALR. Я обнаружил, что таблицы парсера матрицы обычно в два раза быстрее таблиц парсера гребенки. Это связано с тем, что количество нетерминальных переходов (действий goto) обычно примерно вдвое превышает количество терминальных переходов. Матричные таблицы имеют более быстрый нетерминальный переход. Однако в парсере происходит много других вещей, кроме переходов между состояниями, так что это может быть не узким местом.
В 2009 году я сравнил матричные лексерные таблицы с таблицами лексеров, сгенерированных flex, а также с лексерами прямого кода, сгенерированными re2c. Я обнаружил, что таблицы матриц были примерно в два раза быстрее, чем таблицы, сгенерированные flex, и почти так же быстро, как код rexc lexer. Преимущество матричных таблиц состоит в том, что они компилируются намного быстрее, чем таблицы прямого кода, и они меньше. И наконец, если вы позволите матричным таблицам быть очень большими (без сжатия), они на самом деле могут быть быстрее, чем таблицы с прямым кодом (re2c). График, показывающий сравнение, см. На странице сравнения LRSTAR.
Интерфейсы компилятора (без предварительной обработки), созданные с помощью LRSTAR, обрабатывают около 2 400 000 строк кода в секунду, и это включает в себя создание таблицы символов и абстрактного синтаксического дерева при синтаксическом анализе и лексировании. Созданные с помощью DFA лексеры обрабатывают 30 000 000 токенов в секунду. Есть еще одно преимущество матричных лексеров, управляемых таблицами, при использовании DFA. Скелет лексера может быть переписан на ассемблере. Когда я делал это в 1986 году, скорость лексера была в два раза выше, чем у версии на С-коде.
У меня нет большого опыта со скоростью парсера LL или скоростью парсера рекурсивного спуска. Сожалею. Если бы ANTLR мог генерировать код C++, то я мог бы сделать тест скорости для его анализаторов.