Разбор грамматики выражений

В информатике грамматика выражений синтаксического анализа ( PEG ) — это тип аналитической формальной грамматики , т. е. она описывает формальный язык в терминах набора правил распознавания строк на языке. Формализм был предложен Брайаном Фордом в 2004 году. и тесно связан с семейством языков нисходящего синтаксического анализа, представленных в начале 1970-х годов. Синтаксически PEG также похожи на контекстно-свободные грамматики (CFG), но имеют другую интерпретацию: оператор выбора выбирает первое совпадение в PEG, тогда как в CFG оно неоднозначно. Это ближе к тому, как распознавание строк обычно выполняется на практике, например, с помощью анализатора рекурсивного спуска .

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

Определение

— Выражение синтаксического анализа это своего рода шаблон, которому каждая строка может соответствовать или не соответствовать . В случае совпадения существует уникальный префикс строки (который может быть всей строкой, пустой строкой или чем-то промежуточным), который был использован выражением синтаксического анализа; этот префикс обычно считается соответствующим выражению. Однако соответствие строки выражению синтаксического анализа может (из-за предикатов просмотра вперед) зависеть от ее частей, которые идут после потребляемой части. — Язык выражений синтаксического анализа это набор всех строк, соответствующих определенному выражению синтаксического анализа.

— Грамматика выражений синтаксического анализа это набор именованных выражений синтаксического анализа, которые могут ссылаться друг на друга. Эффект одной такой ссылки в выражении синтаксического анализа аналогичен тому, как если бы вместо ссылки было задано все выражение синтаксического анализа, на которое имеется ссылка. Грамматика выражений синтаксического анализа также имеет назначенное начальное выражение ; строка соответствует грамматике, если она соответствует ее начальному выражению.

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

Синтаксис

как абстрактный , так и конкретный В литературе и в этой статье можно увидеть синтаксис выражений синтаксического анализа. Абстрактный синтаксис, по сути, представляет собой математическую формулу и в основном используется в теоретическом контексте, тогда как конкретные выражения синтаксического анализа могут использоваться непосредственно для управления синтаксическим анализатором . Первичный конкретный синтаксис определен Фордом: хотя многие инструменты имеют свой собственный диалект. Другие инструменты может быть ближе к использованию собственной кодировки выражений синтаксического анализа абстрактного синтаксиса в качестве их конкретного синтаксиса.

Выражения атомарного анализа

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

  "terminal" Nonterminal 'another terminal'

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

Конкретный синтаксис также имеет ряд форм для классов терминалов:

• А . (точка) — выражение синтаксического анализа, соответствующее любому отдельному терминалу.
• В скобках список символов. [abcde] сформируйте выражение синтаксического анализа, соответствующее одному из нумерованных символов. Как и в регулярных выражениях , эти классы также могут включать диапазоны. [0-9A-Za-z] записывается в виде дефиса с конечными точками диапазона до и после него. (В отличие от регулярных выражений, классы символов скобок не имеют ^ для отрицания; вместо этого эту цель можно получить с помощью не-предикатов.)
• В некоторых диалектах есть дополнительные обозначения для предопределенных классов символов, таких как буквы, цифры, знаки препинания или пробелы; это снова похоже на ситуацию в регулярных выражениях.

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

• пустая строка ε (как выражение синтаксического анализа оно соответствует каждой строке и не содержит символов),
• конец ввода E (конкретный синтаксический эквивалент !.), и
• отказ $\bot$ (ничего не соответствует).

В конкретном синтаксисе терминалы в кавычках и квадратных скобках имеют обратную косую черту, так что « перевод строки или возврат каретки ». можно записать [\n\r]. Аналогом абстрактного синтаксиса терминала в кавычках длиной больше единицы будет последовательность этих терминалов; "bar" то же самое, что "b" "a" "r". Основной конкретный синтаксис не придает терминалам определенного значения в зависимости от того, используют ли они одинарные или двойные кавычки, но некоторые диалекты рассматривают один из них как регистрозависимый, а другой - как регистронезависимый.

Составные выражения синтаксического анализа

Учитывая любые существующие выражения синтаксического анализа e , e ₁ и e ₂ , новое выражение синтаксического анализа может быть создано с использованием следующих операторов:

• Последовательность : е ₁ е ₂
• Заказанный выбор : e ₁ / e ₂
• Ноль или больше : e *
• Один или несколько : e +
• Необязательно : е ?
• И-предикат : & e
• Не-предикат : ! е
• Группа : ( е )

Приоритеты операторов следующие, согласно Таблице 1:

Оператор	Приоритет
( е )	5
и *, и +, и ?	4
& е , ! е	3
е 1 е 2	2
е1 / eе2	1

Грамматики

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

  Identifier LEFTARROW Expression

The Identifier определяется нетерминал, а Expression — это выражение синтаксического анализа, на которое оно определено как ссылка. LEFTARROW немного различается в зависимости от диалекта, но обычно представляет собой стрелку, указывающую влево, или символ назначения, например <-, ←, :=, или =. Один из способов понять это — это сделать присваивание или определение нетерминала. Другой способ понять это — противопоставить стрелку, указывающую вправо →, используемую в правилах контекстно -свободной грамматики ; при анализе выражений поток информации идет от выражения к нетерминальному, а не от нетерминального к выражению.

Как математический объект, грамматика выражений синтаксического анализа представляет собой кортеж. $(N,\Sigma ,P,e_{S})$, где $N$ - набор нетерминальных символов, $\Sigma$ - набор терминальных символов, $P$ это функция от $N$ к набору выражений синтаксического анализа на $N\cup \Sigma$, и $e_{S}$ — это начальное выражение синтаксического анализа. Некоторые конкретные синтаксические диалекты явно дают начальное выражение: но вместо этого основной конкретный синтаксис имеет неявное правило, согласно которому первый определенный нетерминал является начальным выражением.

Стоит отметить, что основной диалект конкретных грамматик выражений синтаксического анализа не имеет явного терминатора определения или разделителя между определениями, хотя принято начинать новое определение с новой строки; тот LEFTARROW следующего определения достаточно для нахождения границы, если добавить ограничение, согласно которому нетерминал в Expression не должно сопровождаться LEFTARROW. Однако некоторые диалекты могут допускать явный терминатор или прямо требовать это.

Пример

Это PEG, который распознает математические формулы, применяющие пять основных операций к неотрицательным целым числам.

Expr    ← Sum
Sum     ← Product (('+' / '-') Product)*
Product ← Power (('*' / '/') Power)*
Power   ← Value ('^' Power)?
Value   ← [0-9]+ / '(' Expr ')'

В приведенном выше примере терминальные символы представляют собой символы текста, представленные символами в одинарных кавычках, например: '(' и ')'. Диапазон [0-9] это сокращение для десяти символов из '0' к '9'. (Этот синтаксис диапазона аналогичен синтаксису, используемому в регулярных выражениях .) Нетерминальные символы — это символы, которые расширяются до других правил: Value , Power , Product , Sum и Expr . Обратите внимание, что правила Sum и Product не приводят к желаемой левой ассоциативности этих операций (они вообще не имеют дело с ассоциативностью, и ее необходимо обрабатывать на этапе постобработки после синтаксического анализа), а правило Power (с помощью ссылаясь на себя справа) приводит к желаемой правой ассоциативности показателя степени. Также обратите внимание, что правило типа Sum ← Sum (('+' / '-') Product)? (с намерением добиться левой ассоциативности) вызовет бесконечную рекурсию, поэтому его нельзя использовать на практике, даже если его можно выразить в грамматике.

Семантика

Фундаментальное различие между контекстно-свободными грамматиками и грамматиками синтаксического анализа заключается в том, что оператор выбора PEG является упорядоченным . Если первый вариант успешен, второй вариант игнорируется. Таким образом, упорядоченный выбор не является коммутативным , в отличие от неупорядоченного выбора, как в контекстно-свободных грамматиках. Упорядоченный выбор аналогичен операторам мягкого сокращения , доступным в некоторых логического программирования языках .

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

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

Операционная интерпретация выражений синтаксического анализа

Каждый нетерминал в грамматике выражений синтаксического анализа по существу представляет собой функцию синтаксического анализа в анализаторе рекурсивного спуска , а соответствующее выражение синтаксического анализа представляет собой «код», содержащий эту функцию. Каждая функция синтаксического анализа концептуально принимает входную строку в качестве аргумента и возвращает один из следующих результатов:

• успех , в котором функция может опционально двигаться вперед или использовать один или несколько символов входной строки, переданной ей, или
• сбой , и в этом случае входные данные не потребляются.

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

Выражение атомарного синтаксического анализа, состоящее из A , представляет собой рекурсивный вызов нетерминальной функции A. нетерминала Нетерминал может добиться успеха, фактически не потребляя никаких входных данных, и это считается результатом, отличным от неудачи.

Оператор последовательности e e ₁ e ₂ сначала вызывает e ₁ , и, если e ₁ завершается успешно, впоследствии вызывает e ₂ для оставшейся части входной строки, не использованной 1 _, и возвращает результат. Если e ₁ или e ₂ терпят неудачу, то выражение последовательности e ₁ e ₂ терпит неудачу (не потребляя никаких входных данных).

Оператор выбора если e1 _/ , e2 _, вызывает e1 _и завершается успешно e1 _{сначала} немедленно возвращает свой результат. В противном случае, если e ₁ терпит неудачу, тогда оператор выбора возвращается к исходной позиции ввода, в которой он вызвал e ₁ , но затем вместо этого вызывает e ₂ , возвращая e ₂ результат .

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

Выражение and-predicate & e вызывает подвыражение e , а затем завершается успешно, если e завершается успешно, и завершается неудачно, если e завершается неудачно, но в любом случае никогда не потребляет никаких входных данных .

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

Больше примеров

Следующее рекурсивное правило соответствует стандартным операторам if/then/else в стиле C таким образом, что необязательное предложение else всегда привязывается к самому внутреннему оператору if из-за неявного определения приоритета оператора '/'. (В контекстно-свободной грамматике эта конструкция дает классическую двусмысленность висячего else .)

S ← 'if' C 'then' S 'else' S / 'if' C 'then' S

Следующее рекурсивное правило соответствует синтаксису вложенных комментариев в стиле Паскаля: (* which can (* nest *) like this *). Напомним, что . соответствует любому отдельному символу.

C     ← Begin N* End
Begin ← '(*'
End   ← '*)'
N     ← C / (!Begin !End .)

Выражение синтаксического анализа foo &(bar) соответствует и потребляет текст «foo», но только если за ним следует текст «bar». Выражение синтаксического анализа foo !(bar) соответствует тексту «foo», но только если за ним не следует текст «bar». Выражение !(a+ b) a соответствует одному «а», но только если он не является частью произвольно длинной последовательности букв «а», за которой следует буква «б».

Выражение синтаксического анализа ('a'/'b')* соответствует и потребляет последовательность символов a и b произвольной длины. Правило производства S ← 'a' ''S''? 'b' описывает простой контекстно-свободный «язык сопоставления». $\{a^{n}b^{n}:n\geq 1\}$. Следующая грамматика выражений синтаксического анализа описывает классический неконтекстно-свободный язык. $\{a^{n}b^{n}c^{n}:n\geq 1\}$:

S ← &(A 'c') 'a'+ B !.
A ← 'a' A? 'b'
B ← 'b' B? 'c'

Реализация парсеров из анализа грамматик выражений

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

Можно добиться более высокой производительности для любой грамматики синтаксического анализа, преобразовав ее анализатор рекурсивного спуска в анализатор Packrat , который всегда работает за линейное время , ценой существенно большего требования к объему памяти. Парсер Packrat это форма синтаксического анализатора, аналогичная по конструкции парсеру рекурсивного спуска, за исключением того, что во время процесса синтаксического анализа он запоминает промежуточные результаты всех вызовов взаимно рекурсивных функций синтаксического анализа, гарантируя, что каждая функция синтаксического анализа вызывается не более одного раза на заданном входе. позиция. Благодаря этой мемоизации парсер Packrat имеет возможность анализировать множество контекстно-свободных грамматик и любую грамматику синтаксических выражений (включая те, которые не представляют контекстно-свободные языки) за линейное время. Примеры мемоизированных парсеров рекурсивного спуска известны как минимум еще с 1993 года. Этот анализ производительности парсера Packrat предполагает, что памяти достаточно для хранения всех запомненных результатов; на практике, если памяти недостаточно, некоторые функции синтаксического анализа, возможно, придется вызывать более одного раза в одной и той же позиции ввода, и, следовательно, синтаксический анализатор может занять больше линейного времени.

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

Восходящий анализ PEG

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

Преимущества

Компиляция не требуется

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

По сравнению с регулярными выражениями

По сравнению с чистыми регулярными выражениями (т. е. описывающими язык, распознаваемый с помощью конечного автомата ), PEG гораздо более мощны. В частности, они могут обрабатывать неограниченную рекурсию и, таким образом, сопоставлять круглые скобки до произвольной глубины вложенности; регулярные выражения в лучшем случае могут отслеживать вложенность до некоторой фиксированной глубины, поскольку конечный автомат (имеющий конечный набор внутренних состояний) может различать только конечное число различных глубин вложенности. Если говорить более теоретически, $\{a^{n}b^{n}\}_{n\geqslant 0}$ (язык всех строк из нуля и более $a$'s, за которыми следует же количество такое $b$s) не является обычным языком, но легко увидеть, что это язык синтаксического анализа выражений, соответствующий грамматике

start   ← AB !.
AB ← ('a' AB 'b')?

Здесь AB !. является начальным выражением. !. часть обеспечивает, чтобы ввод заканчивался после AB, сказав «следующего символа нет»; в отличие от регулярных выражений, которые имеют магические ограничения $ или \Z для этого выражения синтаксического анализа могут выражать конец ввода, используя только базовые примитивы.

The *, +, и ? выражений синтаксического анализа аналогичны тем, которые используются в регулярных выражениях, но разница в том, что они работают строго в жадном режиме. В конечном итоге это связано с / будучи упорядоченным выбором. Следствием этого является то, что что-то может соответствовать регулярному выражению, но не соответствовать выражению синтаксического анализа:

[ab]?[bc][cd]

является одновременно допустимым регулярным выражением и допустимым выражением синтаксического анализа. Как регулярное выражение оно соответствует bc, но как выражение синтаксического анализа оно не соответствует, потому что [ab]? будет соответствовать b, затем [bc] будет соответствовать c, не оставляя ничего для [cd], поэтому в этот момент сопоставление последовательности не удается. «Попытка еще раз» с наличием [ab]? соответствие пустой строки явно противоречит семантике выражений синтаксического анализа; это не крайний случай конкретного алгоритма сопоставления, а искомое поведение.

Даже регулярные выражения, которые зависят от недетерминизма, могут быть скомпилированы в грамматику синтаксического анализа, имея отдельный нетерминал для каждого состояния соответствующего DFA и кодируя его функцию перехода в определения этих нетерминалов —

A  ← 'x' B / 'y' C

фактически означает «переход из состояния A в состояние B, если следующим символом является x, но в состояние C, если следующим символом является y» — но это работает, потому что недетерминизм можно устранить в области обычных языков. Он не будет использовать варианты выражений синтаксического анализа операций повторения.

По сравнению с контекстно-свободными грамматиками

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

В строго формальном смысле PEG, скорее всего, несопоставимы с CFG, но на практике есть много вещей, которые PEG могут делать, чего не могут чистые CFG, тогда как трудно привести примеры обратного. В частности, PEG могут быть созданы для естественного разрешения неоднозначностей, таких как проблема « висячего else » в C, C++ и Java, тогда как для их разрешения на основе CFG часто требуется правило вне грамматики. Более того, любой PEG можно проанализировать за линейное время с помощью анализатора Packrat, как описано выше, тогда как анализ в соответствии с общей CFG асимптотически эквивалентен к умножению логических матриц (таким образом, вероятно, между квадратичным и кубическим временем).

Одним из классических примеров формального языка, который, очевидно, не является контекстно-свободным, является язык $\{a^{n}b^{n}c^{n}\}_{n\geqslant 0}$: произвольное количество $a$за ними следует равное количество $b$s, за которыми, в свою очередь, следует равное количество $c$с. Это тоже язык синтаксического анализа, которому соответствует грамматика

start ← AB 'c'*
AB    ← 'a' AB 'b' / &(BC !.)
BC    ← ('b' BC 'c')?

Для AB чтобы соответствовать, первый отрезок $a$за s должно следовать равное количество $b$с, и кроме того BC должно совпадать с местом, где $a$переключиться на $b$s, что означает те $b$за ними следует равное количество $c$с.

Недостатки

Потребление памяти

Разбор PEG обычно выполняется посредством разбора Packrat , который использует мемоизацию. чтобы исключить лишние шаги синтаксического анализа. Для синтаксического анализа Packrat требуется внутренняя память, пропорциональная общему размеру входных данных, а не глубине дерева синтаксического анализа, как в случае с парсерами LR. Является ли это существенной разницей, зависит от обстоятельств; если синтаксический анализ является услугой, предоставляемой как функция , то синтаксический анализатор будет хранить полное дерево синтаксического анализа до тех пор, пока не вернет его, и уже это дерево синтаксического анализа обычно будет иметь размер, пропорциональный общему размеру входных данных. Если вместо этого синтаксический анализ предоставляется в виде генератора , то можно обойтись сохранением в памяти только частей дерева синтаксического анализа, но осуществимость этого зависит от грамматики. Грамматика выражений синтаксического анализа может быть спроектирована так, что только после обработки всех входных данных анализатор обнаружит, что ему необходимо вернуться к началу. что снова может потребовать хранения, пропорционального общему размеру входных данных.

Для рекурсивных грамматик и некоторых входных данных глубина дерева разбора может быть пропорциональна размеру входных данных. поэтому и анализатор LR, и анализатор Packrat будут иметь одинаковую асимптотическую производительность в худшем случае. Однако во многих областях, например, в рукописном исходном коде, глубина вложенности выражений имеет фактически постоянную границу, совершенно независимую от длины программы, поскольку выражения, вложенные за пределы определенной глубины, имеют тенденцию подвергаться рефакторингу . Когда нет необходимости сохранять полное дерево разбора, более точный анализ будет учитывать глубину дерева разбора отдельно от входного размера.

Вычислительная модель

Чтобы достичь линейной общей сложности, хранилище, используемое для мемоизации, должно, кроме того, обеспечивать амортизированный постоянный доступ по времени к отдельным запоминаемым элементам данных. На практике это не проблема — например, это достигается с помощью хеш-таблицы динамического размера — но здесь используется арифметика указателей , поэтому предполагается наличие машины с произвольным доступом . Теоретические дискуссии о структурах данных и алгоритмах имеют негласную тенденцию предполагать более ограниченную модель (возможно, модель лямбда-исчисления , возможно, модель Scheme ), где разреженная таблица скорее должна быть построена с использованием деревьев, а доступ к элементам данных не является постоянным временем. . Традиционные алгоритмы синтаксического анализа, такие как парсер LL, это не затрагивает, но это становится наказанием для репутации парсеров Packrat: они полагаются на операции с, казалось бы, плохой репутацией.

С другой стороны, это говорит о том, что парсеры Packrat используют вычислительную мощность, легко доступную в реальных системах, которую старые алгоритмы синтаксического анализа не умеют использовать.

Косвенная левая рекурсия

ПЭГ называется хорошо сформированным. если он не содержит леворекурсивных правил, т. е. правил, которые позволяют нетерминалу расширяться до выражения, в котором тот же нетерминал встречается в качестве самого левого символа. Для анализатора сверху вниз слева направо такие правила вызывают бесконечный регресс: анализ будет постоянно расширять один и тот же нетерминал без продвижения вперед по строке. Следовательно, чтобы разрешить синтаксический анализ Packrat, необходимо устранить левую рекурсию.

Практическая значимость

Прямая рекурсия, будь то левая или правая, важна в контекстно-свободных грамматиках, поскольку там рекурсия — единственный способ описать повторение:

Sum   → Term | Sum '+' Term | Sum '-' Term
Args  → Arg | Arg ',' Args

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

Sum   ← Term ( '+' Term / '-' Term )*
Args  ← Arg ( ',' Arg )*

Разница заключается в генерируемых абстрактных синтаксических деревьях : с рекурсией каждое Sum или Args может иметь не более двух детей, но при повторении их может быть сколь угодно много. Если более поздние этапы обработки требуют, чтобы такие списки дочерних элементов были преобразованы в деревья с ограниченной степенью (например, инструкции микропроцессора для сложения обычно допускают только два операнда), тогда такие свойства, как левая ассоциативность, будут применены после этапа синтаксического анализа, управляемого PEG.

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

Неповторяющаяся левая рекурсия

Например, в приведенной выше арифметической грамматике может показаться заманчивым выразить приоритет операторов как вопрос упорядоченного выбора: Sum / Product / Value означало бы сначала попробовать просмотреть как Sum (поскольку мы анализируем сверху вниз), во-вторых, попробуйте просмотреть как Product, и только третья попытка просмотра как Value — а не через вложение определений. Эта (неправильно сформированная) грамматика стремится сохранить порядок приоритета только в одной строке:

Value   ← [0-9.]+ / '(' Expr ')'
Product ← Expr (('*' / '/') Expr)+
Sum     ← Expr (('+' / '-') Expr)+
Expr    ← Sum / Product / Value

К сожалению, соответствие Expr требует тестирования, если Sum совпадает, при этом сопоставляя Sum требует тестирования, если Expr матчи. Поскольку термин появляется в крайнем левом положении, эти правила образуют замкнутое определение , которое невозможно разрешить. (Существуют циклические определения, которые можно разрешить, например, в исходной формулировке из первого примера, но такие определения не должны проявлять патологическую рекурсию.) Однако леворекурсивные правила всегда можно переписать, чтобы устранить левую рекурсию. Например, следующее леворекурсивное правило CFG:

string-of-a ← string-of-a 'a' | 'a'

можно переписать в PEG с помощью оператора плюс:

string-of-a ← 'a'+

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

С некоторыми изменениями традиционный синтаксический анализ Packrat может поддерживать прямую левую рекурсию. но это приводит к потере свойства синтаксического анализа линейного времени что, как правило, является оправданием использования PEG и анализа пакетов в первую очередь. Только OMeta алгоритм парсинга поддерживает полную прямую и косвенную левую рекурсию без дополнительной сопутствующей сложности (но опять же, за счет потери линейной временной сложности), тогда как все анализаторы GLR поддерживают левую рекурсию.

Неожиданное поведение

Обычное первое впечатление от PEG состоит в том, что они похожи на CFG с определенными удобными функциями — операторами повторения. *+? как в регулярных выражениях и предикатах просмотра вперед &! — плюс упорядоченный выбор для устранения неоднозначности. Этого понимания может быть достаточно, если целью является создание синтаксического анализатора языка, но его недостаточно для более теоретических обсуждений вычислительной мощности синтаксического анализа выражений. В частности, недетерминизм, присущий неупорядоченному выбору. | контекстно-свободных грамматик сильно отличается от детерминированного упорядоченного выбора. /.

Проблема средней точки

Парсеры PEG Packrat не могут распознать некоторые однозначные недетерминированные правила CFG, такие как следующие:

S ← 'x' S 'x' | 'x'

Ни алгоритмы анализа LL(k) , ни LR(k) не способны распознать этот пример. Однако эта грамматика может использоваться обычным анализатором CFG, например алгоритмом CYK . Однако рассматриваемый язык может быть распознан всеми этими типами парсеров, поскольку на самом деле это обычный язык (строки с нечетным числом x).

Полезно выяснить, что именно делает анализатор PEG при попытке сопоставить

S ← 'x' S 'x' / 'x'

против струны xxxxxq. Как и ожидалось, он рекурсивно пытается сопоставить нетерминальный S по возрастанию позиции в этой строке, пока не будет провален матч против q, и после этого начинает отступать. Это происходит следующим образом:

Position:  123456
  String:  xxxxxq
 Results:       ↑ Pos.6: Neither branch of S matches
               ↑ Pos.5: First branch of S fails, second branch succeeds, yielding match of length 1.
              ↑ Pos.4: First branch of S fails, second branch succeeds, yielding match of length 1.
             ↑ Pos.3: First branch of S succeeds, yielding match of length 3.
            ↑ Pos.2: First branch of S fails, because after the S match at 3 comes a q.
              Second branch succeeds, yielding match of length 1.
           ↑ Pos.1: First branch of S succeeds, yielding match of length 3.

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

Обнаружение неоднозначности и влияние порядка правил на сопоставляемый язык

Генераторы синтаксического анализатора LL(k) и LR(k) не смогут завершить работу, если входная грамматика неоднозначна. Это особенность обычного случая, когда грамматика должна быть однозначной, но она дефектна. Генератор синтаксического анализатора PEG разрешит непреднамеренные двусмысленности по принципу «раннее совпадение», которые могут быть произвольными и приводить к неожиданным результатам анализа.

Порядок продукций в грамматике PEG влияет не только на разрешение неоднозначности, но и на сопоставленный язык . Например, рассмотрим первый пример PEG в статье Форда. (пример переписан в нотации pegjs.org/online и помечен ⁠ $G_{1}$⁠ и ⁠ $G_{2}$⁠ ):

• ⁠ $G_{1}$⁠ :   A = "a" "b" / "a"
• ⁠ $G_{2}$⁠ :   A = "a" / "a" "b"

Форд отмечает, что вторая альтернатива в последнем правиле PEG никогда не будет успешной, поскольку первый вариант всегда выбирается, если входная строка ... начинается с «а». . В частности, ⁠ $L(G_{1})$⁠ (т. е. язык, соответствующий ⁠ $G_{1}$⁠ ) ​​включает ввод «ab», но ⁠ $L(G_{2})$⁠ нет. Таким образом, добавление новой опции в грамматику PEG может удалить строки из соответствующего языка, например ⁠ $G_{2}$⁠ — добавление правила к однопродукционной грамматике A = "a" "b", который содержит строку, которой не соответствует ⁠ $G_{2}$⁠ . Кроме того, построение грамматики, соответствующей ⁠ $L(G_{1})\cup L(G_{2})$⁠ из грамматик PEG ⁠ $G_{1}$⁠ и ⁠ $G_{2}$⁠ не всегда тривиальная задача. Это резко контрастирует с CFG, в которых добавление новой продукции не может удалить строки (хотя это может создать проблемы в виде двусмысленности). и (потенциально неоднозначная) грамматика для ⁠ $L(G_{1})\cup L(G_{2})$⁠ можно построить

S → start(G1) | start(G2)

Теория анализа грамматик выражений

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

Класс языков синтаксического анализа закрыт при пересечении и дополнении множеств, а значит, и при объединении множеств.

Неразрешимость пустоты

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

Напомним, что пример задачи о переписке Почты состоит из списка $(\alpha _{1},\beta _{1}),(\alpha _{2},\beta _{2}),\dotsc ,(\alpha _{n},\beta _{n})$ пар строк (терминальных символов). Задача состоит в том, чтобы определить, существует ли последовательность $\{k_{i}\}_{i=1}^{m}$ индексов в диапазоне $\{1,\dotsc ,n\}$ такой, что $\alpha _{k_{1}}\alpha _{k_{2}}\dotsb \alpha _{k_{m}}=\beta _{k_{1}}\beta _{k_{2}}\dotsb \beta _{k_{m}}$. Чтобы свести это к грамматике синтаксического анализа, позвольте $\gamma _{0},\gamma _{1},\dotsc ,\gamma _{n}$ — произвольные попарно различные одинаково длинные строки терминальных символов (уже с $2$ отдельные символы в алфавите терминальных символов, длина $\lceil \log _{2}(n+1)\rceil$ достаточно) и рассмотрим грамматику выражений синтаксического анализа $${\begin{aligned}S&\leftarrow \&(A\,!.)\&(B\,!.)(\gamma _{1}/\dotsb /\gamma _{n})^{+}\gamma _{0}\\A&\leftarrow \gamma _{0}/\gamma _{1}A\alpha _{1}/\dotsb /\gamma _{n}A\alpha _{n}\\B&\leftarrow \gamma _{0}/\gamma _{1}B\beta _{1}/\dotsb /\gamma _{n}B\beta _{n}\end{aligned}}$$ Любая строка, совпадающая с нетерминалом $A$ имеет форму $\gamma _{k_{m}}\dotsb \gamma _{k_{2}}\gamma _{k_{1}}\gamma _{0}\alpha _{k_{1}}\alpha _{k_{2}}\dotsb \alpha _{k_{m}}$ для некоторых индексов $k_{1},k_{2},\dotsc ,k_{m}$. Аналогично любая строка, совпадающая с нетерминалом $B$ имеет форму $\gamma _{k_{m}}\dotsb \gamma _{k_{2}}\gamma _{k_{1}}\gamma _{0}\beta _{k_{1}}\beta _{k_{2}}\dotsb \beta _{k_{m}}$. Таким образом, любая строка, совпадающая с $S$ будет иметь форму $\gamma _{k_{m}}\dotsb \gamma _{k_{2}}\gamma _{k_{1}}\gamma _{0}\rho$ где $\rho =\alpha _{k_{1}}\alpha _{k_{2}}\dotsb \alpha _{k_{m}}=\beta _{k_{1}}\beta _{k_{2}}\dotsb \beta _{k_{m}}$.

Практическое использование

• Python Эталонная реализация CPython представил парсер PEG в версии 3.9 в качестве альтернативы парсеру LL(1) и использует только PEG из версии 3.10.

• Язык программирования jq использует формализм, тесно связанный с PEG.

• Авторы Lua создали LPeg — библиотеку сопоставления с образцом , которая использует PEG вместо регулярных выражений. , а также модуль re , который реализует синтаксис, подобный регулярному выражению, с использованием библиотеки LPeg. .

См. также

• Булева контекстно-свободная грамматика
• Язык описания компилятора (CDL)
• Формальная грамматика
• Регулярное выражение
• Язык синтаксического анализа сверху вниз
• Сравнение генераторов парсеров
• Парсер-комбинатор

Внешние ссылки

• Преобразование строкового выражения в лямбда-выражение с помощью анализатора выражений
• Страница грамматики синтаксического анализа и синтаксического анализа выражений Packrat
• Созданный язык ложбан имеет довольно большую PEG-грамматику, позволяющую однозначно анализировать ложбанский текст.
• Иллюстративная реализация схемы PEG в Guile