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

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

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

Определение

Синтаксис

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

• Конечное множество N из нетерминальные символы.
• Конечное множество Σ терминальные символы то есть непересекающийся из N.
• Конечное множество п из правила парсинга.
• Выражение е_S назвал начальное выражение.

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

1. An выражение атомарного синтаксического анализа состоит из:
   • любой терминальный символ,
   • любой нетерминальный символ, или
   • пустая строка ε.
2. Учитывая любые существующие выражения синтаксического анализа е, е₁, и е₂, новое выражение синтаксического анализа можно создать с помощью следующих операторов:
   • Последовательность: е₁ е₂
   • Заказанный выбор: е₁ / е₂
   • Ноль или больше: е*
   • Один или больше: е+
   • Необязательный: е?
   • И-предикат: &е
   • Не-предикат: !е

Семантика

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

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

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

Оперативная интерпретация синтаксических выражений

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

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

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

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

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

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

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

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

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

Примеры

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

Expr ← SumSum ← Product (('+' / '-') Product) * Product ← Power (('*' / '/') Power) * Power ← Value ('^' Power)? Value ← [0-9 ] + / '(' Выражение ')'

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

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

S ← 'если' C ', то' S 'иначе' S / 'если' C ', то' S

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

Begin ← '(*' End ← '*)' C ← Begin N * EndN ← C / (! Begin! End Z) Z ← любой одиночный символ

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

Выражение синтаксического анализа ('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'

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

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

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

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

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

По сравнению с чистым обычные выражения (т.е. без обратных ссылок), PEG строго более мощные, но требуют значительно больше памяти. Например, регулярное выражение по своей сути не может найти произвольное количество совпадающих пар круглых скобок, потому что оно не рекурсивно, а PEG может. Однако PEG потребует объем памяти, пропорциональный длине ввода, в то время как средство сопоставления регулярных выражений потребует только постоянного объема памяти.

Любой PEG может быть проанализирован за линейное время с помощью анализатора packrat, как описано выше.

Многие CFG содержат двусмысленность, даже если они предназначены для однозначного описания языков. "болтается еще «проблема в C, C ++ и Java - один из примеров. Эти проблемы часто решаются путем применения правила вне грамматики. В PEG эти неоднозначности никогда не возникают из-за приоритизации.

Недостатки

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

Анализ PEG обычно выполняется через парсинг packrat, который использует мемоизация^[5][6] для исключения лишних шагов синтаксического анализа. Для синтаксического анализа Packrat требуется объем памяти, пропорциональный общему размеру входных данных, а не глубине дерева синтаксического анализа, как в парсерах LR. Это существенное различие во многих областях: например, рукописный исходный код имеет фактически постоянную глубину вложенности выражений, не зависящую от длины программы - выражения, вложенные за пределы определенной глубины, обычно подвергаются рефакторингу.

Для некоторых грамматик и некоторых входных данных глубина дерева синтаксического анализа может быть пропорциональна размеру входных данных,^[7]таким образом, как LR-парсер, так и парсер packrat будут иметь одинаковую асимптотическую производительность в худшем случае. Более точный анализ будет учитывать глубину дерева синтаксического анализа отдельно от размера ввода. Это похоже на ситуацию, которая возникает в графовые алгоритмы: the Алгоритм Беллмана – Форда и Алгоритм Флойда-Уоршолла похоже, имеют одинаковое время работы (${\displaystyle O(|V|^{3})}$), если учесть только количество вершин. Однако более точный анализ, который учитывает количество ребер как отдельный параметр, присваивает Алгоритм Беллмана – Форда время ${\displaystyle O(|V|*|E|)}$, что квадратично для разреженных графов с ${\displaystyle |E|\in O(|V|)}$.

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

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

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

Значение ← [0-9.] + / '(' Expr ')' Product ← Expr (('*' / '/') Expr) * Sum ← Expr (('+' / '-') Expr) * Expr ← Продукт / Сумма / Стоимость

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

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

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

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

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

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

Выразительная сила

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

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

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

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

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

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

Порядок продукции в грамматике PEG влияет не только на разрешение неоднозначности, но и на язык соответствует. Например, рассмотрим первый пример PEG в статье Форда.^[1](пример переписан в нотации pegjs.org/online и помечен как G1 и G2):

• G1:А = "а" "б" / "а"
• G2:А = «а» / «а» «б»

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

S → начало (G1) | начало (G2)

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

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

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

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

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

1. Форд, Брайан (январь 2004 г.). "Анализ грамматик выражений: синтаксическая основа на основе распознавания" (PDF). Материалы 31-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования. ACM. С. 111–122. Дои:10.1145/964001.964011. ISBN  1-58113-729-X.
2. Форд, Брайан (сентябрь 2002 г.). «Парсинг Packrat: простой, мощный, ленивый, линейное время, функциональная жемчужина» (PDF). Уведомления ACM SIGPLAN. 37 (9). Дои:10.1145/583852.581483.
3. Форд, Брайан (сентябрь 2002 г.). Парсинг Packrat: практический алгоритм линейного времени с возвратом (Тезис). Массачусетский Институт Технологий. Получено 2007-07-27.
4. Мерритт, Дуг (ноябрь 1993 г.). «Прозрачный рекурсивный спуск». Составители группы Usenet. Получено 2009-09-04.
5. Форд, Брайан. "Страница грамматик синтаксического анализа выражений Packrat". BFord.info. Получено 23 ноя 2010.
6. Джеллифф, Рик (10 марта 2010 г.). "Что такое парсер Packrat? Что такое производные Бжозовского?". Архивировано из оригинал 28 июля 2011 г.
7. например, выражение LISP (x (x (x (x ....))))
8. Ахо, А.В .; Sethi, R .; Ульман, Дж. Д. (1986). Компиляторы: принципы, методы и инструменты. Бостон, Массачусетс, США: Эддисон-Уэсли Лонгман.
9. Варт, Алессандро; Дуглас, Джеймс Р .; Миллштейн, Тодд (январь 2008 г.). «Парсеры Packrat могут поддерживать левую рекурсию» (PDF). Материалы симпозиума 2008 ACM SIGPLAN по частичной оценке и манипулированию программами на основе семантики. PEPM '08. ACM. С. 103–110. Дои:10.1145/1328408.1328424. Получено 2008-10-02.
10. Штейнманн, Руеди (март 2009 г.). «Обработка левой рекурсии в парсерах Packrat» (PDF). n.ethz.ch. Архивировано из оригинал (PDF) на 2011-07-06.
11. Хатчисон, Люк А. Д. (2020). «Анализ Pika: обратный синтаксический анализ решает проблемы левой рекурсии и восстановления после ошибок». arXiv:2005.06444.

внешняя ссылка

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