Почему парсер-генераторы, а не просто настраиваемые парсеры?

Question

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

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

В большинстве случаев я вижу, что генерация кода используется для обхода ограничений в способности метапрограммирования языков (т. Е. Веб-фреймворки, AOP, взаимодействие с базами данных), но в целом лекс-анализ кажется довольно простым и статичным. , не нуждаясь ни в каком дополнительном динамическом метапрограммировании, которое вы получаете от генерации кода. Что дает? Выигрыш в производительности настолько велик?

Answer 1

Если все, что вам нужно, это парсер, который вы можете настроить, передав ему правила грамматики, это может быть достигнуто. Синтаксический анализатор Earley будет анализировать любой контекстно-свободный язык, используя только набор правил. Цена значительного времени выполнения: O (N ^ 3), где N - длина входа. Если N большое (как для многих разбираемых сущностей), вы можете закончить очень медленным анализом.

И это причина генератора парсера (PG). Если вы анализируете много документов, медленный анализ - плохая новость. Компиляторы - это одна программа, в которой люди анализируют много документов, и ни один программист (или его менеджер) не хочет, чтобы программист ждал компилятора. Есть много других вещей, которые нужно проанализировать: SQL-запросы, JSON-документы ... все они имеют свойство "Никто не хочет ждать".

Что PG делает, так это принимает много решений, которые должны были бы возникнуть во время выполнения (например, для парсера Earley), и предварительно вычисляет эти результаты во время генерации парсера. Таким образом, LALR (1) PG (например, Bison) будет генерировать парсеры, которые запускаются за O (N) времени, и это, очевидно, намного быстрее в практических условиях. (ANTLR делает нечто подобное для парсеров LL (k)). Если вы хотите, чтобы полный контекстный синтаксический анализ был обычно линейным, вы можете использовать вариант синтаксического анализа LR, называемый GLR-анализ ; это дает вам удобство «настраиваемого» (Earley) синтаксического анализатора с гораздо лучшей типичной производительностью.

Эта идея предварительного вычисления заранее известна как частичная оценка , то есть, учитывая функцию F (x, y) и знание того, что x всегда является определенной константой x_0, вычисляют новую функцию F '(y) = F (x0, y), в котором решения и вычисления, зависящие исключительно от значения x, предварительно вычисляются. F 'обычно работает намного быстрее, чем F. В нашем случае, F - это что-то вроде общего синтаксического анализа (например, синтаксический анализатор Эрли), x - это грамматический аргумент, а x0 - специфическая грамматика, а F' - некоторая инфраструктура синтаксического анализатора P и дополнительная код / ​​таблицы, вычисленные PG так, что F '= PG (x) + P.

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