Ответ 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.
В комментариях к вашему вопросу, кажется, есть некоторый интерес в том, почему один из них не просто запускает генератор синтаксического анализа, действующий во время выполнения. Простой ответ заключается в том, что он платит значительную часть накладных расходов, которые вы хотите избавиться во время выполнения.