Какая разница во времени выполнения между разными алгоритмами разбора?

Question

Существует множество различных алгоритмов синтаксического анализа (рекурсивный спуск, LL (k), LR (k), LALR, ...).Я нахожу много информации о различных грамматиках, которые могут принимать разные типы синтаксических анализаторов.Но как они отличаются поведением во время выполнения?Какой алгоритм работает быстрее, использует меньше памяти или места в стеке?

Или, иначе говоря, какой алгоритм работает лучше всего, предполагая, что грамматика может быть сформулирована для работы с любым алгоритмом?

Answer 1

LR парсеры ИМХО могут быть самыми быстрыми. По сути, они используют токен в качестве индекса для набора промежуточных данных или таблицы переходов, чтобы решить, что делать дальше (выдвинуть индекс состояния, выдвинуть индексы состояния / вызвать процедуру сокращения). Преобразовать в машинный код это может быть всего несколько машинных инструкций. Пеннелло подробно обсуждает это в своей статье:

Томас Дж. Пеннелло: очень быстрый разбор LR. Симпозиум SIGPLAN по компиляции 1986: 145-151

LL-парсеры используют рекурсивные вызовы, которые немного медленнее, чем просто поиск по таблице, но могут быть довольно быстрыми.

GLR-парсеры являются обобщениями LR-парсеров, и, таким образом, имеют медленнее, чем LR-парсеры. Ключевое наблюдение заключается в том, что большую часть времени анализатор GLR действует точно так же, как и анализатор LR, и можно заставить эту часть работать практически с той же скоростью, что и анализатор LR, поэтому они могут быть довольно быстрыми.

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

С точки зрения перевода вашей грамматики в пригодную для использования форму, ниже приведен порядок, в котором технологии синтаксического анализа "облегчают":

• GLR (действительно просто: если вы можете написать правила грамматики, вы можете разобрать)
• LR (k) (подходит много грамматик, крайне мало генераторов синтаксического анализатора)
• LR (1) (чаще всего доступно [YACC, Bison, Gold, ...]
• LL (обычно требуется значительный реинжиниринг грамматики для удаления левых рекурсий)
• Рекурсивный спуск с ручным кодированием (легко кодировать для простых грамматик; трудно обрабатывать сложные грамматики и трудно поддерживать, если грамматика сильно меняется)

Answer 2

Я провел исследование скорости синтаксического анализатора LR между LRSTAR и YACC.

В 1989 году я сравнил таблицы синтаксического анализа матрицы, определенные в статье, «Оптимизация таблиц синтаксического анализа для переносных компиляторов» с таблицами синтаксического анализа YACC (структура гребенки).Это таблицы LR или LALR.Я обнаружил, что таблицы парсера матрицы обычно в два раза быстрее таблиц парсера гребенки.Это связано с тем, что количество нетерминальных переходов (действий goto) обычно примерно вдвое превышает количество терминальных переходов.Матричные таблицы имеют более быстрый нетерминальный переход.Однако в парсере происходит много других вещей, кроме переходов между состояниями, так что это может быть не узким местом.

В 2009 году я сравнил матричные лексерные таблицы с таблицами лексеров, сгенерированных гибким способом, а также с лексерами прямого кода, сгенерированными re2c.Я обнаружил, что таблицы матриц были примерно в два раза быстрее, чем таблицы, сгенерированные flex, и почти так же быстро, как код rexc lexer.Преимущество матричных таблиц состоит в том, что они компилируются намного быстрее, чем таблицы прямого кода, и они меньше.И наконец, если вы позволите матричным таблицам быть очень большими (без сжатия), они на самом деле могут быть быстрее, чем таблицы с прямым кодом (re2c).График, показывающий сравнение, см .: страница сравнения LRSTAR

Интерфейсы компилятора (без предварительной обработки), созданные с помощью LRSTAR, обрабатывают около 2 400 000 строк кода в секунду, и это включает в себя создание символатаблица и абстрактное синтаксическое дерево при разборе и лексировании.Созданные с помощью DFA лексеры обрабатывают 30 000 000 токенов в секунду.Есть еще одно преимущество для матричных лексеров, управляемых таблицами, при использовании DFA.Скелет лексера может быть переписан на ассемблере.Когда я делал это в 1986 году, скорость лексера в два раза превышала скорость версии кода С.

У меня нет большого опыта со скоростью парсера LL или скоростью парсера рекурсивного спуска.Сожалею.Если бы ANTLR мог генерировать код C ++, то я мог бы сделать тест скорости для его парсеров.