Грамматики экспрессии парсинга (PEG) ^[6] являются производными от Extended Backus-Naur Form (EBNF) ^[7] с другой интерпретацией, предназначенной для представления рекурсивного спускового парсера. ПЭГ можно непосредственно представить в виде парсера рекурсивного спуска.

Как и EBNF, PEG является формальной грамматикой для описания формального языка с точки зрения набора правил, используемых для распознавания строк этого языка. В отличие от EBNF, ПЭГ имеют точную интерпретацию. Для каждой грамматики PEG существует только одно действующее дерево разбора (см. Резюме синтаксиса).

Sequences

Последовательности представлены сопоставлением, как в EBNF:

a b

Выражение PEG выше гласит, что для достижения успеха b должно следовать a. Вот синтаксическая диаграмма:

Вот тривиальный пример:

'x' digit

символ x должен сопровождаться цифрой.

	Note
	В Spirit.Qi мы используем >> для последовательностей, поскольку C++ не допускает сопоставления, в то время как в Spirit.Karma мы используем <<.

Alternatives

Альтернативы представлены в PEG с использованием слэша:

a / b

	Note
	В Spirit.Qi и Spirit.Karma мы используем | для альтернатив, как в EBNF.

Альтернативы позволяют делать выбор. Выражение выше гласит: попробуйте сопоставить a. Если a удаётся, успех, если не пытаться сопоставить b. Это немного отклонение от обычной интерпретации EBNF, где вы просто соответствуете a или b. Вот синтаксическая диаграмма:

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

Loops

Опять же, как и EBNF, PEG использует звезду Kleene с регулярным выражением и петли плюс:

a*
a+

	Note
	Spirit.Qi и Spirit.Karma используют префикс звезды и плюс, поскольку в C++ нет постфиксной звезды или плюса.

Вот синтаксические диаграммы:

Первая, называемая звездой Клин, соответствует нулю или больше ее объекта a. Вторая, плюс, соответствует одной руде больше ее предмета a.

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

alnum* digit

В PEG число будет съедать столько буквенно-цифровых символов, сколько оно не сможет оставить позади. Таким образом, следующая цифра ничего не получит. Петли просто реализуются в рекурсивном коде спуска, что делает их чрезвычайно эффективными. Это явное преимущество. С другой стороны, те, кто знаком с EBNF и поведением регекса, могут найти это поведение основным. PEG предоставляет несколько других механизмов, чтобы обойти это. В ближайшее время мы увидим больше подобных механизмов.

Difference

В некоторых случаях вы можете ограничить определенное выражение. Вы можете думать о выражении PEG как о совпадении с потенциально бесконечным набором строк. Разница оператора позволяет ограничить этот набор:

a - b

Выражение гласит: «соответствовать a, но не b».

	Note
	Нет разницы оператора в Spirit.Karma, так как концепция не имеет смысла в контексте генерации выходных данных.