Синтаксический анализ Packrat позволяет обеспечить асимптотически более высокую производительность для анализа грамматик выражений. (ПЭГ); специально для PEG может быть гарантирован анализ линейного времени.

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

На высоком уровне:

• Парсеры Packrat используют грамматики синтаксического анализа выражений (PEG), а не традиционные контекстно-свободные грамматики (CFG).

• Благодаря использованию PEG, а не CFG, как правило, проще настроить и поддерживать синтаксический анализатор packrat, чем традиционный синтаксический анализатор LR. .

• Из-за того, как они используют запоминание, синтаксические анализаторы Packrat обычно используют больше памяти во время выполнения, чем классические синтаксические анализаторы, такие как LALR( 1) и парсеры LR(1).

• Как и классические парсеры LR, парсеры packrat работают за линейное время.

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

Остальная часть этого ответа дает более подробный обзор парсеров packrat и PEG.

О CFG и PEG

Многие традиционные синтаксические анализаторы (и многие современные синтаксические анализаторы) используют контекстно-свободные грамматики. Контекстно-свободная грамматика состоит из ряда правил, подобных показанным здесь:

E -> E * E | E + E | (E) | N
N -> D | DN
D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Например, в верхней строке сказано, что нетерминал E можно заменить либо на E * E, либо на E + E, либо на (E), либо на N. Во второй строке говорится, что N можно заменить либо на D, либо на DN. Последняя строка говорит, что D можно заменить любой одиночной цифрой.

Если вы начнете со строки E и будете следовать правилам приведенной выше грамматики, вы сможете сгенерировать любое математическое выражение, используя +, *, круглые скобки и одиночные цифры.

Контекстно-свободные грамматики — это компактный способ представления набора строк. У них есть богатая и хорошо изученная теория. Однако у них есть два основных недостатка. Первый заключается в том, что сама по себе CFG определяет набор строк, но не говорит вам, как проверить, генерируется ли конкретная строка грамматикой. Это означает, что то, будет ли конкретная CFG поддаваться хорошему синтаксическому анализатору, зависит от особенностей работы синтаксического анализатора, а это означает, что автору грамматики может потребоваться ознакомиться с внутренней работой их генератора синтаксического анализа, чтобы понять, какие ограничения накладываются на могут возникнуть различные грамматические структуры. Например, парсеры LL(1) не поддерживают левую рекурсию и требуют левого факторинга. , в то время как синтаксические анализаторы LALR(1) требуют некоторого понимания алгоритма синтаксического анализа для устранения shift/reduce и reduce/reduce конфликты.

Вторая, большая проблема заключается в том, что грамматики могут быть неоднозначными. Например, приведенная выше грамматика генерирует строку 2 + 3 * 4, но делает это двумя способами. С одной стороны, мы фактически получаем группировку 2 + (3 * 4), что и предполагалось. Другой дает нам (2 + 3) * 4, что не имеет в виду. Это означает, что авторы грамматики должны либо убедиться, что грамматика однозначна, либо ввести объявления приоритета, вспомогательные по отношению к грамматике, чтобы сообщить синтаксическому анализатору, как разрешать конфликты. Это может быть немного хлопотно.

Парсеры Packrat используют альтернативу контекстно-свободным грамматикам, называемую грамматиками синтаксического анализа (PEG). Грамматики синтаксического анализа выражений в некотором роде напоминают CFG — они описывают набор строк, говоря, как собрать эти строки из (потенциально рекурсивных) меньших частей. С другой стороны, они похожи на регулярные выражения: они включают более простые операторы, объединенные небольшим набором операций, описывающих более крупные структуры.

Например, вот простой PEG для того же типа арифметических выражений, что и выше:

E -> F + E / F
F -> T * F / T
T -> D* / (E)
D -> 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9

Чтобы понять, о чем это говорит, давайте посмотрим на первую строку. Подобно CFG, эта строка выражает выбор между двумя вариантами: вы можете заменить E на F + E или на F. Однако, в отличие от обычной CFG, для этих вариантов существует определенный порядок. В частности, этот PEG можно считать первым, попробуйте заменить E на F + E. Если это сработает, отлично! И если это не сработает, попробуйте заменить E на F. И если это работает, отлично! А в остальном, мы пробовали все, и это не сработало, так что сдавайтесь.

В этом смысле PEG напрямую кодируют в самой структуре грамматики, как должен выполняться синтаксический анализ. В то время как CFG более абстрактно говорит, что E может быть заменена любым из следующего, PEG специально говорит, чтобы проанализировать E, сначала попробуйте это, затем это, затем это и т. д. В результате для любой данной строки, которую PEG может parse, PEG может выполнить синтаксический анализ только одним способом, поскольку он прекращает пробовать варианты, как только будет найден первый синтаксический анализ.

PEG, как и CFG, может занять некоторое время, чтобы освоиться. Например, абстрактные CFG — и многие методы разбора CFG — не имеют проблем с левой рекурсией. Например, эту CFG можно разобрать парсером LR(1):

E -> E + F | F
F -> F * T | T
T -> (E) | N
N -> ND | D
D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Однако следующий PEG не может быть проанализирован синтаксическим анализатором packrat (хотя более поздние улучшения синтаксического анализа PEG могут исправить это):

E -> E + F / F
F -> F * T / T
T -> (E) / D*
D -> 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9

Давайте посмотрим на эту первую строку. В первой строке говорится, что для разбора E сначала попробуйте прочитать E, затем +, затем F. И если это не удастся, попробуйте прочитать F. Так как же тогда попробовать этот первый вариант? Первым шагом было бы попытаться проанализировать E, что сработает, если сначала попытаться проанализировать E, и теперь мы попали в бесконечный цикл. Упс. Это называется левой рекурсией и также отображается в CFG при работе с анализаторами семейства LL.

Еще одна проблема, возникающая при проектировании PEG, — это необходимость правильного выбора упорядоченных вариантов. Если вы приехали из страны контекстно-свободной грамматики, где выбор неупорядочен, очень легко случайно испортить PEG. Например, рассмотрим этот PEG:

E -> F / F + E
F -> T / T * F
T -> D* / (E)
D -> 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9

А что произойдет, если вы попытаетесь разобрать строку 2 * 3 + 4? Хорошо:

• Мы пытаемся разобрать E, который сначала пытается разобрать F.
• Мы пытаемся разобрать F, который сначала пытается разобрать T.
• Мы пытаемся разобрать T, который сначала пытается прочитать ряд цифр. Это удается при чтении 2.
• Мы успешно прочитали F.
• Итак, мы успешно прочитали E, так что на этом мы должны закончить, но есть оставшиеся токены, и синтаксический анализ завершается ошибкой.

Проблема здесь в том, что мы сначала попытались проанализировать F до F + E, и аналогичным образом сначала попытались проанализировать T перед разбором T * F. В результате мы фактически откусили меньше, чем могли бы проверить, потому что попытались прочитать более короткое выражение перед более длинным.

Считаете ли вы CFG с присутствием двусмысленностей и деклараций приоритета проще или сложнее, чем PEG с присутствием порядка выбора, в основном зависит от личных предпочтений. Но многие люди сообщают, что с PEG немного легче работать, чем с CFG, потому что они более механически отображают то, что должен делать синтаксический анализатор. Вместо того, чтобы говорить, что вот абстрактное описание строк, которые мне нужны, вы можете сказать, что вот порядок, в котором я хотел бы, чтобы вы попробовали что-то, что немного ближе к тому, как часто работает синтаксический анализ.

Алгоритм синтаксического анализа Packrat

По сравнению с алгоритмами для построения таблиц синтаксического анализа LR или LL, алгоритм, используемый синтаксическим анализом packrat, концептуально довольно прост. На высоком уровне синтаксический анализатор Packrat начинает со стартового символа, затем последовательно пробует упорядоченные варианты, пока не найдет тот, который работает. По мере того, как он работает с этими вариантами, он может обнаружить, что ему нужно сопоставить другой нетерминал, и в этом случае он рекурсивно пытается сопоставить этот нетерминал с остальной частью строки. Если конкретный выбор терпит неудачу, синтаксический анализатор откатывается, а затем пробует следующую продукцию.

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

Это означает, что, в более общем смысле, анализатор packrat работает, пытаясь решить проблемы следующей формы:

Учитывая некоторую позицию в строке и нетерминал, определить, какая часть строки соответствует этому нетерминалу, начиная с этой позиции (или сообщить, что она не совпадает вообще).

Здесь обратите внимание, что нет никакой двусмысленности в том, что подразумевается под тем, какая часть строки соответствует нетерминалу. В отличие от традиционной CFG, где нетерминал может совпадать в заданной позиции в нескольких различных длинах, упорядоченный выбор, используемый в PEG, гарантирует, что если есть какое-то совпадение, начинающееся в данной точке, то есть ровно одно совпадение, начинающееся с эта точка.

Если вы изучали динамическое программирование, вы могли заметить, что эти подзадачи могут пересекаться друг с другом. На самом деле, в PEG с k нетерминалами и строкой длины n существует только Θ(kn) возможных различных подзадач: по одной для каждой комбинации начальной позиции и нетерминала. Это означает, что, в принципе, вы могли бы использовать динамическое программирование для предварительного вычисления таблицы всех возможных совпадений позиции/нетерминального синтаксического анализа и иметь очень быстрый синтаксический анализатор. По сути, синтаксический анализ Packrat делает это, но использует запоминание, а не динамическое программирование. Это означает, что он не обязательно будет пытаться заполнить все записи таблицы, а только те, которые действительно встречаются в ходе разбора грамматики.

Поскольку каждая запись в таблице может быть заполнена за постоянное время (для каждого нетерминала существует только конечное число продукций, которые нужно попробовать для фиксированного PEG), синтаксический анализатор в конечном итоге работает за линейное время, что соответствует скорости синтаксического анализатора LR.

Недостатком этого подхода является объем используемой памяти. В частности, таблица запоминания может записывать несколько записей на позицию во входной строке, требуя использования памяти, пропорционального как размеру PEG, так и длине входной строки. Сравните это с синтаксическим анализом LL или LR, для которого требуется только память, пропорциональная размеру стека синтаксического анализа, который обычно намного меньше длины полной строки.

При этом компромисс здесь в виде худшей производительности памяти компенсируется отсутствием необходимости изучать внутреннюю работу парсера packrat. Вы можете просто прочитать о ПЭГ и взять оттуда что-то.

Надеюсь это поможет!

Pyparsing — это библиотека синтаксического анализа на чистом языке Python, которая поддерживает синтаксический анализ с помощью Packrat, поэтому вы можете посмотреть, как это реализовано. Pyparsing использует метод запоминания, чтобы сохранить предыдущие попытки синтаксического анализа для определенного выражения грамматики в определенном месте во входном тексте. Если грамматика включает повторную попытку того же выражения в этом месте, она пропускает дорогостоящую логику синтаксического анализа и просто возвращает результаты или исключение из кэша запоминания.

Дополнительную информацию можно найти здесь, в FAQ. страница вики-страницы pyparsing, которая также содержит ссылки на оригинальную диссертацию Брайана Форда по анализу packrat.