Анализ грамматики выражений

Тип грамматики для описания формальных языков

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

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

Определение

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

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

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

Синтаксис

В литературе и в этой статье рассматриваются как абстрактный , так и конкретный синтаксис выражений синтаксического анализа. Абстрактный синтаксис по сути является математической формулой и в основном используется в теоретических контекстах, тогда как выражения синтаксического анализа конкретного синтаксиса могут использоваться напрямую для управления синтаксическим анализатором . Основной конкретный синтаксис определен Фордом ^{[1] : Рис.1} , хотя многие инструменты имеют свой собственный диалект этого. Другие инструменты ^[3] могут быть ближе к использованию собственного кодирования языка программирования выражений синтаксического анализа абстрактного синтаксиса в качестве своего конкретного синтаксиса.

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

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

 «терминал»  Нетерминал  «другой терминал»

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

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

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

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

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

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

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

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

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

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

Грамматики

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

 Идентификатор  LEFTARROW  Выражение

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

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

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

Пример

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

Выражение  ←  Сумма Сумма ← Произведение (( '+' / '-' ) Произведение ) * Произведение ← Степень (( '*' / '/' ) Степень ) * Степень ← Значение ( '^' Степень ) ? Значение ← [ 0-9 ] + / '(' Выражение ')'                      

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

Семантика

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

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

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

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

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

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

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

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

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

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

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

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

Выражение не-предиката ! e выполняется успешно, если e не выполняется, и не выполняется, если e выполняется успешно, снова не потребляя входных данных в обоих случаях.

Еще примеры

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

S  ←  «если»  C  «тогда»  S  «иначе»  S  /  «если»  C  «тогда»  S

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

C  ←  Начало  N *  Конец Начало  ←  '(*' Конец  ←  '*)' N  ←  C  /  ( ! Начало  ! Конец  . )

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

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

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

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

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

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

Также возможно построить LL-парсеры и LR-парсеры из грамматик выражений синтаксического анализа ^{[ требуется ссылка ]} с лучшей производительностью в худшем случае, чем парсер рекурсивного спуска без мемоизации, но тогда теряется неограниченная возможность опережения формализма грамматики. Поэтому не все языки, которые могут быть выражены с помощью грамматик выражений синтаксического анализа, могут быть проанализированы парсерами LL или LR.

Анализ PEG снизу вверх

Парсер pika ^[7] использует динамическое программирование для применения правил PEG снизу вверх и справа налево, что является обратным порядку обычного рекурсивного спуска сверху вниз, слева направо. Парсинг в обратном порядке решает проблему левой рекурсии, позволяя использовать леворекурсивные правила непосредственно в грамматике без переписывания в нелеворекурсивную форму, а также предоставляет парсеру оптимальные возможности восстановления ошибок, что исторически оказалось труднодостижимым для парсеров рекурсивного спуска.

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

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

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

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

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

начало  ←  AB  ! . AB  ←  ( 'a'  AB  'b' ) ?

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

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

[ab]?[bc][cd]

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

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

А  ←  'х'  Б  /  'у'  В

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

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

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

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

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

начало  ←  AB  'c' * AB  ←  'a'  AB  'b'  /  & ( BC  ! . ) BC  ←  ( 'b'  BC  'c' ) ?

Для ABсоответствия за первым отрезком s должно следовать равное количество s, и, кроме того, должно совпадать место, где s переходит в s, что означает, что за этими s должно следовать равное количество s. ${\displaystyle a}$ ${\displaystyle b}$BC ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle c}$

Недостатки

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

Разбор PEG обычно выполняется с помощью анализа packrat , который использует мемоизацию ^{[10] [11]} для устранения избыточных шагов анализа. Анализ Packrat требует внутреннего хранилища, пропорционального общему размеру ввода, а не глубине дерева анализа, как в случае с анализаторами LR. Является ли это существенной разницей, зависит от обстоятельств; если анализ — это услуга, предоставляемая как функция , то анализатор будет хранить полное дерево анализа до его возврата, и уже это дерево анализа будет иметь размер, пропорциональный общему размеру ввода. Если анализ вместо этого предоставляется как генератор , то можно обойтись сохранением только частей дерева анализа в памяти, но осуществимость этого зависит от грамматики. Грамматику выражения анализа можно разработать таким образом, что только после потребления полного ввода анализатор обнаружит, что ему нужно вернуться к началу, ^[12] что снова может потребовать хранилища, пропорционального общему размеру ввода.

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

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

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

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

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

PEG называется хорошо сформированным ^[1], если он не содержит леворекурсивных правил, т. е. правил, которые позволяют нетерминалу расширяться до выражения, в котором тот же нетерминал встречается как самый левый символ. Для нисходящего слева направо парсера такие правила вызывают бесконечный регресс: парсинг будет постоянно расширять тот же нетерминал без продвижения вперед по строке. Поэтому, чтобы разрешить парсинг Packrat, левая рекурсия должна быть устранена.

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

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

Сумма  →  Термин  |  Сумма  '+'  Термин  |  Сумма  '-'  Термин Аргументы  →  Арг  |  Арг  ','  Аргументы

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

Сумма  ←  Термин  (  '+'  Термин  /  '-'  Термин  ) * Аргументы  ←  Аргумент  (  ','  Аргумент  ) *

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

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

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

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

Значение  ←  [ 0-9. ] +  /  '('  Выражение  ')' Произведение  ←  Выражение  (( '*'  /  '/' )  Выражение ) + Сумма  ←  Выражение  (( '+'  /  '-' )  Выражение ) + Выражение  ←  Сумма  /  Произведение  /  Значение

К сожалению, сопоставление Exprтребует проверки, Sumсовпадает ли a, в то время как сопоставление Sumтребует проверки, Exprсовпадает ли an. Поскольку термин появляется в крайней левой позиции, эти правила составляют циклическое определение , которое не может быть разрешено. (Циклические определения, которые могут быть разрешены, существуют, например, в исходной формулировке из первого примера, но такие определения требуются, чтобы не проявлять патологическую рекурсию.) Однако леворекурсивные правила всегда можно переписать, чтобы устранить левую рекурсию. ^{[2] [15]} Например, следующее леворекурсивное правило CFG:

строка-из-a  ←  строка-из-a  'a'  |  'a'

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

строка-из-a  ←  'a' +

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

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

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

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

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

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

С  ←  'х'  С  'х'  |  'х'

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

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

С  ←  'х'  С  'х'  /  'х'

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

Позиция: 123456 Строка: xxxxxq Результаты: ↑ Pos.6: Ни одна из ветвей S не соответствует ↑ Pos.5: Первая ветвь S терпит неудачу, вторая ветвь успешна, что дает совпадение длины 1. ↑ Pos.4: Первая ветвь S терпит неудачу, вторая ветвь успешна, что дает совпадение длины 1. ↑ Pos.3: Первая ветвь S завершается успешно, давая совпадение длины 3. ↑ Pos.2: Первая ветвь S терпит неудачу, потому что после совпадения S в позиции 3 следует q. Вторая ветвь завершается успешно, давая совпадение длины 1. ↑ Pos.1: Первая ветвь S завершается успешно, давая совпадение длины 3.

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

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

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

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

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

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

S → старт ( G1 ) | старт ( G2 )    

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

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

Класс языков синтаксического анализа выражений замкнут относительно пересечения и дополнения множеств, а значит, и относительно объединения множеств. ^{[1] : Раздел 3.4}

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

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

Напомним, что экземпляр задачи соответствия Post состоит из списка пар строк (терминальных символов). Задача состоит в том, чтобы определить, существует ли последовательность индексов в диапазоне такая, что . Чтобы свести это к грамматике выражений разбора, пусть будут произвольными попарно различными одинаково длинными строками терминальных символов (уже с различными символами в алфавите терминальных символов, длины достаточно) и рассмотрим грамматику выражений разбора Любая строка, сопоставляемая нетерминалом, имеет вид для некоторых индексов . Аналогично любая строка, сопоставляемая нетерминалом, имеет вид . Таким образом, любая строка, сопоставляемая будет иметь вид , где . ${\displaystyle (\alpha _{1},\beta _{1}),(\alpha _{2},\beta _{2}),\dotsc ,(\alpha _{n},\beta _{n})}$ ${\displaystyle \{k_{i}\}_{i=1}^{m}}$ ${\displaystyle \{1,\dotsc ,n\}}$ ${\displaystyle \alpha _{k_{1}}\alpha _{k_{2}}\dotsb \alpha _{k_{m}}=\beta _{k_{1}}\beta _{k_{2}}\dotsb \beta _{k_{m}}}$ ${\displaystyle \gamma _{0},\gamma _{1},\dotsc ,\gamma _{n}}$ ${\displaystyle 2}$ ${\displaystyle \lceil \log _{2}(n+1)\rceil }$ $${\displaystyle {\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}}}$$ ${\displaystyle A}$ ${\displaystyle \gamma _{k_{m}}\dotsb \gamma _{k_{2}}\gamma _{k_{1}}\gamma _{0}\alpha _{k_{1}}\alpha _{k_{2}}\dotsb \alpha _{k_{m}}}$ ${\displaystyle k_{1},k_{2},\dotsc ,k_{m}}$ ${\displaystyle B}$ ${\displaystyle \gamma _{k_{m}}\dotsb \gamma _{k_{2}}\gamma _{k_{1}}\gamma _{0}\beta _{k_{1}}\beta _{k_{2}}\dotsb \beta _{k_{m}}}$ ${\displaystyle S}$ ${\displaystyle \gamma _{k_{m}}\dotsb \gamma _{k_{2}}\gamma _{k_{1}}\gamma _{0}\rho }$ ${\displaystyle \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. ^[19]

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

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

Смотрите также

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

Ссылки

1. Форд, Брайан (январь 2004 г.). "Parsing Expression Grammars: A Recognition Based Syntactic Foundation" (PDF) . Труды 31-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . ACM . стр. 111–122. doi :10.1145/964001.964011. ISBN 1-58113-729-X.
2. Ford, Bryan (сентябрь 2002 г.). «Packrat parsing: simple, powerful, lazy, linear time, functional Pearl» (PDF) . ACM SIGPLAN Notices . 37 (9). doi :10.1145/583852.581483.
3. Сиртиас, Матиас. «Parboiled: Rule Construction in Java». GitHub . Получено 13 января 2024 г.
4. Куприс, Андреас. "pt::peg_language - PEG Language Tutorial". Исходный код библиотеки Tcl . Получено 14 января 2024 г.
5. Ford, Bryan (сентябрь 2002 г.). Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (диссертация). Массачусетский технологический институт . Получено 27 июля 2007 г.
6. Мерритт, Дуг (ноябрь 1993 г.). "Прозрачный рекурсивный спуск". Usenet group comp.compilers . Получено 2009-09-04 .
7. Хатчисон, Люк АД (2020). «Разбор Pika: обратный разбор решает проблемы левой рекурсии и восстановления после ошибок». arXiv : 2005.06444 [cs.PL].
8. CFG можно использовать для описания синтаксиса распространенных языков программирования вплоть до уровня символов, но делать это довольно обременительно, поскольку стандартное правило токенизации, согласно которому токен состоит из самой длинной последовательной последовательности символов одного и того же вида, не очень хорошо согласуется с недетерминированной стороной CFG. Чтобы формализовать, что пробел между двумя соседними токенами обязателен, если символы по обе стороны границы токена являются буквами, но необязателен, если они не являются буквами, CFG необходимо несколько вариантов большинства нетерминалов, чтобы отслеживать, какой символ должен быть на границе. Если существуют различные виды непробельных символов, это приводит к возможным вариантам на нетерминал — значительно раздувая грамматику. ${\displaystyle 3}$ ${\displaystyle 3^{2}=9}$
9. Ли, Лиллиан (январь 2002 г.). «Быстрый контекстно-свободный синтаксический анализ грамматики требует быстрого умножения булевых матриц». J. ACM . 49 (1): 1–15. arXiv : cs/0112018 . doi :10.1145/505241.505242.
10. Форд, Брайан. "Страница анализа и грамматики выражений анализа Packrat". BFord.info . Получено 23 ноября 2010 г.
11. Джеллифф, Рик (10 марта 2010 г.). «Что такое Packrat Parser? Что такое Brzozowski Derivatives?». Архивировано из оригинала 28 июля 2011 г.
12. Например, в самом конце ввода может быть директива о том, что «в этом файле запятая является десятичным разделителем , поэтому все эти вызовы функций f(3,14*r), как вы думали, имеют два аргумента? Это не так. Теперь вернитесь к началу ввода и проанализируйте все снова». Возможно, это было бы плохой конструкцией языка ввода, но суть в том, что грамматики выражений синтаксического анализа достаточно мощны, чтобы справиться с этим, чисто с точки зрения синтаксиса.
13. например, выражение LISP (x (x (x (x ....))))
14. Это похоже на ситуацию, которая возникает в графовых алгоритмах : алгоритм Беллмана–Форда и алгоритм Флойда–Уоршелла, по-видимому, имеют одинаковое время выполнения ( ), если учитывать только количество вершин. Однако более точный анализ, который учитывает количество ребер как отдельный параметр, назначает алгоритму Беллмана–Форда время , которое является квадратичным для разреженных графов с . ${\displaystyle O(|V|^{3})}$ ${\displaystyle O(|V|*|E|)}$ ${\displaystyle |E|\in O(|V|)}$
15. Ахо, А. В.; Сети, Р.; Ульман, Дж. Д. (1986). Компиляторы: принципы, методы и инструменты . Бостон, Массачусетс, США: Addison-Wesley Longman . ISBN 0-201-10088-6.
16. Warth, Alessandro; Douglass, James R.; Millstein, Todd (январь 2008 г.). "Packrat Parsers Can Support Left Recursion" (PDF) . Труды симпозиума ACM SIGPLAN 2008 г. по частичной оценке и семантической обработке программ . PEPM '08. ACM . стр. 103–110. doi :10.1145/1328408.1328424. ISBN 9781595939777. Получено 2008-10-02 .
17. Steinmann, Ruedi (март 2009). "Handling Left Recursion in Packrat Parsers" (PDF) . n.ethz.ch . Архивировано из оригинала (PDF) 2011-07-06.
18. Лофф, Бруно; Морейра, Нельма; Рейс, Рожерио (14 февраля 2020 г.). «Вычислительная мощность анализа грамматик выражений». arXiv : 1902.08272 [cs.FL].
19. "PEP 617 – Новый анализатор PEG для CPython | peps.python.org". peps.python.org . Получено 2023-01-16 .
20. Ierusalimschy, Roberto (10 марта 2009 г.). "Инструмент сопоставления текстовых шаблонов на основе грамматик выражений синтаксического анализа". Software: Practice and Experience . 39 (3): 221–258. doi :10.1002/spe.892. ISSN  0038-0644.
21. Иерусалимский, Роберто. "LPeg.re - Синтаксис регулярных выражений для LPEG". www.inf.puc-rio.br .

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

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