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

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

В информатике грамматика выражений синтаксического анализа ( 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], записанные в виде дефиса, с конечными точками диапазона до и после него. (В отличие от регулярных выражений, в классах символов скобок нет ^отрицания; вместо этого его конец можно получить с помощью не-предикатов.)
• В некоторых диалектах есть дополнительные обозначения для предопределенных классов символов, таких как буквы, цифры, знаки препинания или пробелы; это снова похоже на ситуацию в регулярных выражениях.

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

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

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

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

Учитывая любые существующие выражения синтаксического анализа 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достаточно для нахождения границы, если добавить ограничение, согласно которому за нетерминалом в a Expressionне должен следовать a LEFTARROW. Однако некоторые диалекты могут допускать явный терминатор или прямо требовать ^[4] его.

Пример

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

Expr  ←  Sum Sum  ←  Продукт  (( '+'  /  '-' )  Продукт ) * Продукт  ←  Мощность  (( '*'  /  '/' )  Мощность ) * Мощность  ←  Значение  ( '^'  Мощность ) ? Значение  ←  [ 0-9 ] +  /  '('  Выражение  ')'

В приведенном выше примере терминальные символы — это символы текста, представленные символами в одинарных кавычках, например '('и ')'. Диапазон [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 _{2 .}

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

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

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

Выражение синтаксического анализа соответствует и использует текст «foo», но только если за ним следует текст «bar». Выражение синтаксического анализа соответствует тексту «foo», но только если за ним не следует текст «bar». Выражение соответствует одному «а», но только если оно не является частью произвольно длинной последовательности букв «а», за которой следует «б».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  ! . А  ←  'а'  А ?  'b' B  ←  'b'  B ?  'с'

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

Любую грамматику выражения синтаксического анализа можно преобразовать непосредственно в анализатор рекурсивного спуска . ^[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, но как выражение синтаксического анализа оно не соответствует, потому что the [ab]?будет соответствовать b, затем [bc]будет соответствовать c, не оставляя ничего для [cd], поэтому в этот момент сопоставление последовательности завершается неудачно. «Попытка еще раз» с сопоставлением [ab]?пустой строки явно противоречит семантике синтаксического анализа выражений; это не крайний случай конкретного алгоритма сопоставления, а искомое поведение.

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

A  ←  'x'  B  /  'y'  C

фактически означает «переход из состояния 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}$

start  ←  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 обычно выполняется посредством синтаксического анализа packagerat , который использует мемоизацию ^{[10] [11]} для устранения избыточных шагов синтаксического анализа. Для синтаксического анализа Packrat требуется внутренняя память, пропорциональная общему размеру входных данных, а не глубине дерева синтаксического анализа, как в случае с парсерами LR. Является ли это существенной разницей, зависит от обстоятельств; если синтаксический анализ является услугой, предоставляемой как функция , то синтаксический анализатор будет хранить полное дерево синтаксического анализа до тех пор, пока не вернет его, и уже это дерево синтаксического анализа обычно будет иметь размер, пропорциональный общему размеру входных данных. Если вместо этого синтаксический анализ предоставляется в виде генератора , то можно обойтись сохранением в памяти только частей дерева синтаксического анализа, но осуществимость этого зависит от грамматики. Грамматика выражений синтаксического анализа может быть спроектирована так, что только после обработки всех входных данных анализатор обнаружит, что ему необходимо вернуться к началу, ^[12] что опять же может потребовать памяти, пропорциональной общему размеру входных данных.

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

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

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

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

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

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

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

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

Сумма  →  Срок  |  Сумма  '+'  Термин  |  Сумма  '-'  Термин Args  →  Arg  |  Арг  ','  Аргс

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

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

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

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

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

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

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

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

строка  ←  строка  'a'  |  'а'

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

строка-а  ←  'а' +

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

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

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

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

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

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

S  ←  'x'  S  'x'  |  'Икс'

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

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

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

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

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

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

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

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

Порядок продукций в грамматике 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"

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

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

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

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

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

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

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

Напомним, что пример задачи соответствия Поста состоит из списка пар строк (терминальных символов). Проблема состоит в том, чтобы определить, существует ли в диапазоне последовательность индексов такая, что . Чтобы свести это к грамматике выражений синтаксического анализа, пусть это произвольные попарно различные одинаково длинные строки терминальных символов (уже с различными символами в алфавите терминальных символов, длины достаточно) и рассмотрим грамматику выражений синтаксического анализа ${\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.

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

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

Рекомендации

1. Форд, Брайан (январь 2004 г.). «Разбор грамматик выражений: синтаксическая основа, основанная на распознавании» (PDF) . Материалы 31-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . АКМ . стр. 111–122. дои : 10.1145/964001.964011. ISBN 1-58113-729-Х.
2. Форд, Брайан (сентябрь 2002 г.). «Парсинг Packrat: простой, мощный, ленивый, линейное время, функциональная жемчужина» (PDF) . Уведомления ACM SIGPLAN . 37 (9). дои : 10.1145/583852.581483.
3. Сиртиас, Матиас. «Пропаренный: построение правил на Java» . Проверено 13 января 2024 г.
4. Куприс, Андреас. «pt::peg_language — Учебник по языку PEG». Исходный код библиотеки Tcl . Проверено 14 января 2024 г.
5. Форд, Брайан (сентябрь 2002 г.). Анализ Packrat: практический алгоритм линейного времени с обратным отслеживанием (тезис). Массачусетский Институт Технологий . Проверено 27 июля 2007 г.
6. Мерритт, Дуг (ноябрь 1993 г.). «Прозрачный рекурсивный спуск». Группа Usenet comp.compilers . Проверено 4 сентября 2009 г.
7. Хатчисон, Люк А.Д. (2020). «Разбор Пика: обратный анализ решает проблемы левой рекурсии и устранения ошибок». arXiv : 2005.06444 [cs.PL].
8. CFG можно использовать для описания синтаксиса распространенных языков программирования вплоть до уровня символов, но это довольно громоздко, поскольку стандартное правило токенизации, согласно которому токен состоит из самой длинной последовательной последовательности символов одного типа, плохо сочетается. с недетерминированной стороной CFG. Чтобы формализовать этот пробел между двумя соседними токенами, он является обязательным, если символы по обе стороны границы токена являются буквами, но необязательным, если они не являются буквами, CFG требуется несколько вариантов большинства нетерминалов, чтобы отслеживать, какой тип символа имеет оказаться на границе. Если существуют разные типы символов без пробелов, это увеличивает количество возможных вариантов для каждого нетерминала, что значительно раздувает грамматику. ${\displaystyle 3}$ ${\displaystyle 3^{2}=9}$
9. Ли, Лилиан (январь 2002 г.). «Быстрый бесконтекстный анализ грамматики требует быстрого умножения булевой матрицы». Дж. АКМ . 49 (1): 1–15. arXiv : cs/0112018 . дои : 10.1145/505241.505242.
10. Форд, Брайан. «Страница синтаксического анализа и анализа выражений Packrat». BFord.info . Проверено 23 ноября 2010 г.
11. Джеллифф, Рик (10 марта 2010 г.). «Что такое анализатор Packrat? Что такое производные Бжозовского?». Архивировано из оригинала 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. Ахо, А.В.; Сетхи, Р.; Уллман, JD (1986). Составители: принципы, методы и инструменты . Бостон, Массачусетс, США: Аддисон-Уэсли Лонгман . ISBN 0-201-10088-6.
16. Варт, Алессандро; Дуглас, Джеймс Р.; Миллштейн, Тодд (январь 2008 г.). «Парсеры Packrat могут поддерживать левую рекурсию» (PDF) . Материалы симпозиума ACM SIGPLAN 2008 года по частичной оценке и манипулированию программами на основе семантики . ПЭПМ '08. АКМ . стр. 103–110. дои : 10.1145/1328408.1328424. ISBN 9781595939777. Проверено 2 октября 2008 г.
17. Штайнманн, Руди (март 2009 г.). «Обработка левой рекурсии в парсерах Packrat» (PDF) . n.ethz.ch. ​Архивировано из оригинала (PDF) 6 июля 2011 г.
18. Лофф, Бруно; Морейра, Нельма; Рейс, Рожерио (14 февраля 2020 г.). «Вычислительная мощность анализа грамматик выражений». arXiv : 1902.08272 [cs.FL].
19. «PEP 617 — новый парсер PEG для CPython | peps.python.org» . peps.python.org . Проверено 16 января 2023 г.

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

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