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

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

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

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

Ответ 1

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

И в этом причина генератора парсера (PG). Если вы разбираете много документов, Slow Parsing - плохая новость. Компиляторы - это одна программа, где люди разбирают много документов, и ни один программист (или его менеджер) не хочет, чтобы программист ждал компилятора. Там много других вещей для синтаксического анализа: 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.

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