Войти
В информатике, выражение синтаксического анализа грамматика ( PEG), является типом аналитической формальной грамматики, т.е. описывает формальный язык в терминах набора правил для распознавания строк на языке. Формализм был введен Брайаном Фордом в 2004 году и тесно связан с семейством языков синтаксического анализа сверху вниз, представленных в начале 1970-х годов. Синтаксически PEG также похожи на контекстно-свободные грамматики (CFG), но имеют другую интерпретацию: оператор выбора выбирает первое совпадение в PEG, в то время как в CFG оно неоднозначно. Это ближе к тому, как распознавание строк обычно осуществляется на практике, например, с помощью синтаксического анализатора рекурсивного спуска.
В отличие от CFG, PEG не могут быть двусмысленными ; если строка анализируется, у нее есть ровно одно допустимое дерево синтаксического анализа. Предполагается, что существуют контекстно-свободные языки, которые не могут быть распознаны PEG, но это еще не доказано. PEG хорошо подходят для анализа компьютерных языков (и искусственных человеческих языков, таких как ложбан ), но не естественных языков, где производительность алгоритмов PEG сопоставима с общими алгоритмами CFG, такими как алгоритм Эрли.
Формально грамматика синтаксического выражения состоит из:
Каждое правило синтаксического анализа в P имеет форму A ← e, где A - нетерминальный символ, а e - выражение синтаксического анализа. Выражение синтаксического анализа - это иерархическое выражение, подобное регулярному выражению, которое строится следующим образом:
Фундаментальное различие между контекстно-свободными грамматиками и грамматиками синтаксического анализа состоит в том, что оператор выбора PEG упорядочен. Если первая альтернатива успешна, вторая игнорируется. Таким образом, упорядоченный выбор не является коммутативным, в отличие от неупорядоченного выбора, как в контекстно-свободных грамматиках. Упорядоченный выбор аналогичен операторам мягкого сокращения, доступным в некоторых языках логического программирования.
Следствием этого является то, что если CFG транслитерируется непосредственно в PEG, любая неоднозначность в первом разрешается путем детерминированного выбора одного дерева синтаксического анализа из возможных синтаксических анализов. Тщательно выбирая порядок, в котором указываются альтернативы грамматики, программист может в значительной степени контролировать, какое дерево синтаксического анализа будет выбрано.
Подобно логическим контекстно-свободным грамматикам, грамматики синтаксического анализа также добавляют предикаты and и несинтаксические. Потому что они могут использовать сколь угодно сложную суб-выражение «смотреть вперед» во входной строку фактически не потребляя его, они обеспечивают мощный синтаксическое опережение и устранение неоднозначности объект, в частности, когда переназначение альтернативы не может указать точное дерево разбора желаемое.
Каждый нетерминал в грамматике выражений разбора по существу, представляет собой синтаксический анализ функцию в методе рекурсивного спуска, и соответствующее разборе выражение представляет «код», содержащую функцию. Каждая функция синтаксического анализа концептуально принимает входную строку в качестве аргумента и дает один из следующих результатов:
Выражение атомарного синтаксического анализа, состоящее из одного терминала (т.е. литерала), завершается успешно, если первый символ входной строки совпадает с этим терминалом и в этом случае потребляет входной символ; в противном случае выражение даст результат сбоя. Выражение атомарного синтаксического анализа, состоящее из пустой строки, всегда тривиально завершается успешно, не потребляя никаких входных данных.
Атомарный разбор выражения, состоящие из нетерминального А представляет собой рекурсивный вызов к нетерминальной-функции A. Нетерминал может преуспеть, фактически не потребляя никаких входных данных, и это считается результатом, отличным от неудачи.
Последовательность оператора е 1 е 2 первые вызывает е 1, и, если е 1 завершается успешно, затем вызывает е 2 на оставшуюся часть входной строки слева неизрасходованные по е 1, и возвращает результат. Если либо e 1, либо e 2 терпят неудачу, то выражение последовательности e 1 e 2 терпит неудачу (не потребляя ввода).
На выборе оператор е 1 / е 2 первых вызывающих й 1, и если е 1 успешно, немедленно возвращает результат. В противном случае, если e 1 терпит неудачу, то оператор выбора возвращается к исходной позиции ввода, в которой он вызвал e 1, но затем вместо этого вызывает e 2, возвращая результат e 2.
Операторы " ноль или более", " один или более" и необязательные операторы потребляют ноль или более, одно или более, либо ноль или одно последовательных повторений их подвыражения e соответственно. Однако, в отличие от контекстно-свободных грамматик и регулярных выражений, эти операторы всегда ведут себя жадно, потребляя как можно больше входных данных и никогда не возвращаются. (Средства сопоставления регулярных выражений могут начинаться с жадного сопоставления, но затем будут возвращаться и пытаться найти более короткие сопоставления, если они не совпадают.) Например, выражение a * всегда будет потреблять столько значений a, сколько последовательно доступно во входной строке, а выражение (a * a) всегда будет терпеть неудачу, потому что первая часть (a *) никогда не оставит никаких a для соответствия второй части.
В и-предикатные выражения и е Запускает Подвыражение е, а затем успешно, если е преуспевает и терпит неудачу, если е не может, но в любом случае никогда не потребляет никакой вход.
Не-сказуемое выражение! e преуспевает, если e терпит неудачу, и терпит неудачу, если e преуспевает, снова не потребляя никаких входных данных в любом случае.
Это PEG, распознающий математические формулы, применяющие пять основных операций к неотрицательным целым числам.
Expr ← Sum Sum ← Product (('+' / '-') Product)* Product ← Power (('*' / '/') Power)* Power ← Value ('^' Power)? Value ← [0-9]+ / '(' Expr ')' В приведенном выше примере терминальные символы - это символы текста, представленные символами в одинарных кавычках, например '('и ')'. Диапазон [0-9]также является сокращением для десяти символов, обозначающих любую из цифр от 0 до 9. (Этот синтаксис диапазона такой же, как синтаксис, используемый регулярными выражениями. ) Нетерминальные символы - это символы, которые расширяются до других правил: значение, Мощность, произведение, сумма и выражение. Обратите внимание, что правила Sum и Product не приводят к желаемой левой ассоциативности этих операций (они вообще не имеют дело с ассоциативностью, и ее нужно обрабатывать на этапе постобработки после синтаксического анализа), а правило Power (с помощью ссылаясь на себя справа) приводит к желаемой правоассоциативности показателя степени. Также обратите внимание, что такое правило, как (с намерением достичь левоассоциативности), вызовет бесконечную рекурсию, поэтому его нельзя использовать на практике, даже если оно может быть выражено в грамматике. Sum ← Sum (('+' / '-') Product)?
Следующее рекурсивное правило соответствует стандартным операторам if / then / else в стиле C таким образом, что необязательное предложение «else» всегда привязывается к самому внутреннему «if» из-за неявной приоритизации оператора '/'. (В контекстно-независимой грамматике эта конструкция приводит к классической двусмысленности висячего else. )
S ← 'if' C 'then' S 'else' S / 'if' C 'then' S
Следующее рекурсивное правило соответствует Pascal стиль вложенных синтаксис комментариев, (* which can (* nest *) like this *). Символы комментариев заключены в одинарные кавычки, чтобы отличать их от операторов PEG.
Begin ← '(*' End ← '*)' C ← Begin N* End N ← C / (!Begin !End Z) Z ← any single character
Выражение синтаксического анализа соответствует и использует текст «foo», но только если за ним следует текст «bar». Выражение синтаксического анализа соответствует тексту «foo», но только если за ним не следует текст «bar». Выражение соответствует одному "a", но только если оно не является частью произвольно длинной последовательности символов a, за которыми следует b. foo amp;(bar)foo !(bar)!(a+ b) a
Выражение синтаксического анализа соответствует и использует последовательность произвольной длины, состоящую из букв a и b. Правило производства описывает простой контекстно-свободной «язык соответствия». Следующая грамматика синтаксического анализа описывает классический неконтекстно-свободный язык: ('a'/'b')* S ← 'a' ''S''? 'b'
S ← amp;(A 'c') 'a'+ B !. A ← 'a' A? 'b' B ← 'b' B? 'c'
Любую грамматику выражения синтаксического анализа можно преобразовать непосредственно в синтаксический анализатор с рекурсивным спуском. Однако из-за неограниченной возможности просмотра вперед, которую предоставляет грамматический формализм, результирующий синтаксический анализатор в худшем случае может демонстрировать экспоненциальную временную производительность.
Можно получить лучшую производительность для любой грамматики синтаксического анализа, преобразовав его рекурсивный анализатор спуска в синтаксический анализатор packrat, который всегда работает в линейном времени, за счет существенно большего объема памяти. Парсер packrat - это форма синтаксического анализатора, похожая на синтаксический анализатор с рекурсивным спуском по конструкции, за исключением того, что во время процесса синтаксического анализа он запоминает промежуточные результаты всех вызовов взаимно рекурсивных функций синтаксического анализа, гарантируя, что каждая функция синтаксического анализа вызывается не более одного раза в одно и то же время. заданная позиция ввода. Благодаря этой мемоизации, синтаксический анализатор packrat может анализировать множество контекстно-свободных грамматик и любую грамматику синтаксического анализа (включая те, которые не представляют контекстно-свободные языки) за линейное время. Примеры мемоизированных рекурсивных анализаторов спуска известны, по крайней мере, с 1993 года. Этот анализ производительности синтаксического анализатора packrat предполагает, что доступно достаточно памяти для хранения всех мемоизированных результатов; на практике, если памяти недостаточно, некоторые функции синтаксического анализа, возможно, придется вызывать более одного раза в одной и той же позиции ввода, и, следовательно, синтаксический анализатор может занять больше, чем линейное время.
Также возможно построить анализаторы LL и синтаксические анализаторы LR на основе синтаксического анализа грамматик выражений с лучшей производительностью в худшем случае, чем синтаксический анализатор с рекурсивным спуском, но при этом теряется неограниченная возможность упреждающего просмотра грамматического формализма. Следовательно, не все языки, которые могут быть выражены с помощью грамматик синтаксического анализа, могут быть проанализированы анализаторами LL или LR.
По сравнению с чистыми регулярными выражениями (то есть без обратных ссылок) PEG строго более мощные, но требуют значительно больше памяти. Например, регулярное выражение по своей сути не может найти произвольное количество совпадающих пар круглых скобок, потому что оно не рекурсивно, а PEG может. Однако PEG потребует объем памяти, пропорциональный длине ввода, в то время как сопоставитель регулярных выражений потребует только постоянный объем памяти.
Любой PEG может быть проанализирован за линейное время с помощью синтаксического анализатора packrat, как описано выше.
Многие CFG содержат двусмысленность, даже если они предназначены для однозначного описания языков. Одним из примеров является проблема « болтающегося остального » в C, C ++ и Java. Эти проблемы часто решаются применением правила вне грамматики. В PEG эти двусмысленности никогда не возникают из-за расстановки приоритетов.
Анализ PEG обычно выполняется с помощью синтаксического анализа packrat, который использует мемоизацию для устранения избыточных шагов синтаксического анализа. Для синтаксического анализа Packrat требуется объем памяти, пропорциональный общему размеру входных данных, а не глубине дерева синтаксического анализа, как в парсерах LR. Это существенное различие во многих областях: например, рукописный исходный код имеет фактически постоянную глубину вложенности выражений, не зависящую от длины программы - выражения, вложенные за пределами определенной глубины, обычно подвергаются рефакторингу.
Для некоторых грамматик и некоторых входных данных глубина дерева синтаксического анализа может быть пропорциональна размеру ввода, поэтому и LR-синтаксический анализатор, и синтаксический анализатор packrat будут иметь одинаковую асимптотическую производительность в худшем случае. Более точный анализ будет учитывать глубину дерева синтаксического анализа отдельно от размера входных данных. Это похоже на ситуацию, которая возникает в алгоритмах на графах : в Беллмане-Форде алгоритм и Флойд-Воршалл алгоритм, как представляется, в то же время бега (), если только число вершин считаются. Однако более точный анализ, который учитывает количество ребер как отдельный параметр, присваивает алгоритму Беллмана – Форда время, которое квадратично для разреженных графов с.
PEG называется правильно сформированным, если он не содержит леворекурсивных правил, т. Е. Правил, которые позволяют нетерминалу расширяться до выражения, в котором такой же нетерминал встречается как крайний левый символ. Для синтаксического анализатора с направлением сверху вниз слева направо такие правила вызывают бесконечную регрессию: синтаксический анализ будет постоянно расширять один и тот же нетерминал, не продвигаясь вперед по строке.
Следовательно, чтобы разрешить синтаксический анализ packrat, необходимо исключить левую рекурсию. Например, в приведенной выше арифметической грамматике было бы заманчиво переместить некоторые правила так, чтобы порядок приоритета продуктов и сумм мог быть выражен в одной строке:
Value ← [0-9.]+ / '(' Expr ')' Product ← Expr (('*' / '/') Expr)* Sum ← Expr (('+' / '-') Expr)* Expr ← Product / Sum / Value В этой новой грамматике сопоставление Exprтребует проверки Productсовпадения, а сопоставление Productтребует проверки Exprсовпадения. Поскольку термин находится в крайнем левом положении, эти правила образуют циклическое определение, которое не может быть разрешено. (Круговые определения, которые могут быть разрешены, существуют - например, в исходной формулировке из первого примера - но такие определения требуются, чтобы не демонстрировать патологическую рекурсию.) Однако леворекурсивные правила всегда можно переписать, чтобы исключить леворекурсию. Например, следующее леворекурсивное правило CFG:
string-of-a ← string-of-a 'a' | 'a'
можно переписать в PEG с помощью оператора плюс:
string-of-a ← 'a'+
Процесс переписывания косвенно левый рекурсивные правил является сложным в некотором Packrat анализаторах, особенно когда семантические действия вовлечены.
С некоторыми изменениями традиционный синтаксический анализ packrat может поддерживать прямую левую рекурсию, но это приводит к потере свойства синтаксического анализа в линейном времени, что обычно является оправданием для использования PEG и анализа packrat в первую очередь. Только алгоритм синтаксического анализа OMeta поддерживает полную прямую и косвенную левую рекурсию без дополнительной сопутствующей сложности (но опять же, с потерей линейной временной сложности), тогда как все синтаксические анализаторы GLR поддерживают левую рекурсию.
Парсеры PEG packrat не могут распознать некоторые недетерминированные правила CFG, такие как следующие:
S ← 'x' S 'x' | 'x'
Ни алгоритмы анализа LL (k), ни LR (k) не способны распознать этот пример. Однако эта грамматика может использоваться обычным парсером CFG, например алгоритмом CYK. Однако рассматриваемый язык может быть распознан всеми этими типами синтаксического анализатора, поскольку на самом деле это обычный язык (язык строк с нечетным числом x).
Это открытая проблема - дать конкретный пример контекстно-свободного языка, который не может быть распознан грамматикой синтаксического анализа.
Генераторы парсеров LL (k) и LR (k) не смогут завершить работу, если входная грамматика неоднозначна. Это характерная черта в общем случае, когда грамматика должна быть недвусмысленной, но дефектной. Генератор синтаксического анализатора PEG разрешит непреднамеренные неоднозначности «раннее совпадение», что может быть произвольным и привести к неожиданному синтаксическому анализу.
Порядок продукции в грамматике PEG влияет не только на разрешение неоднозначности, но и на сопоставленный язык. Например, рассмотрим первый пример PEG в статье Форда (пример, переписанный в нотации pegjs.org/online и помеченный и):
A = "a" "b" / "a"A = "a" / "a" "b"Форд отмечает, что вторая альтернатива в последнем правиле PEG никогда не будет успешной, потому что всегда выбирается первый вариант, если входная строка... начинается с 'a'.. В частности, (т. Е. Язык, которому соответствует) включает ввод «ab», но не включает. Таким образом, добавление новой опции к грамматике PEG может удалить строки из сопоставленного языка, например, добавление правила к грамматике с одним продуктом , которое содержит строку, не сопоставленную. Кроме того, построение грамматики в соответствии с PEG - грамматик и не всегда является тривиальной задачей. Это резко контрастирует с CFG, в котором добавление новой продукции не может удалить строки (хотя это может вызвать проблемы в виде двусмысленности), и (потенциально неоднозначная) грамматика для может быть построена A = "a" "b"
S → start(G1) | start(G2)
Парсер pika использует динамическое программирование для применения правил PEG снизу вверх и справа налево, что является обратным нормальному рекурсивному порядку спуска сверху вниз слева направо. Синтаксический анализ в обратном порядке решает проблему левой рекурсии, позволяя использовать леворекурсивные правила непосредственно в грамматике без переписывания в не леворекурсивную форму, а также предоставляет синтаксическому анализатору оптимальные возможности восстановления после ошибок, что исторически оказалось труднодостижимым. для парсеров рекурсивного спуска.
