WikiSort.ru - Не сортированное

Интерпретация выражений разбора

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

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

Нетерминал может завершиться успешно без поглощения ввода, и это состояние отлично от провала.

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

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

Оператор выбора e₁ / e₂ сначала вызывает e₁ и, если e₁ успешно, возвращает её результат. Иначе, если e₁ проваливается, оператор выбора восстанавливает входную строку в состояние, предшествующее вызову e₁, и вызывает e₂, возвращая её результат.

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

Наконец, И-предикат и НЕ-предикат реализуют синтаксические предикаты. Выражение &e вызывает подвыражение e, и возвращает успех, если e успешно, и провал в противном случае, но никогда не поглощает ввода. Аналогично, выражение !e срабатывает успешно, если e проваливается и проваливается, если e успешно, так же не поглощая ввода. Поскольку выражение e может представлять собой сколь угодно сложную конструкцию, вычисляемую «наперёд» без поглощения входной строки, эти предикаты предоставляют мощные синтаксические средства предварительного анализа и устранения неоднозначности.

Примеры

Следующая РВ-грамматика распознаёт математические формулы с четырьмя действиями над неотрицательными целыми.

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

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

В примерах ниже нет кавычек для улучшения читаемости. Строчные буквы являются терминальными символами, а прописные курсивные — нетерминалы. Настоящие анализаторы РВ-грамматик требуют кавычек.

Выражение разбора (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' / 'b' / 'c')
A ← 'a' A? 'b'
B ← 'b' B? 'c'

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

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

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

Следующее рекурсивное правило соответствует вложенному комментарию языка Паскаль. Символы комментариев помещены в одинарные кавычки для отличия их от операторов РВГ.

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

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

Анализ РВ-грамматики обычно производится packrat-парсером, который запоминает лишние шаги анализа. Такой анализ требует хранения данных пропорционально длине входных данных, в отличие от глубины дерева разбора для LR-анализаторов. Это существенный прирост во многих областях: например, программный код, написанный человеком, как правило имеет практически константную глубину вложенности независимо от длины программы — выражения с глубиной свыше некоторой величины обычно подвергаются рефакторингу.

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

Непрямая левая рекурсия

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

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

Тут проблема в том, что для того, чтобы получить срабатывание для Expr, необходимо проверить, срабатывает ли Product, а чтобы проверить Product, нужно сначала проверить Expr. А это невозможно.

Однако, леворекурсивные правила всегда можно переписать, ликвидируя левую рекурсию. Например, леворекурсивное правило может повторять некоторое выражение неопределённо долго, как в правиле КС-грамматики:

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

Это можно переписать в РВ-грамматике, используя оператор +:

string-of-a ← 'a'+

С определёнными изменениями можно заставить обычный packrat-парсер поддерживать прямую левую рекурсию^[1][2][3].

Однако, процесс переписывания косвенных леворекурсивных правил затруднён, особенно когда имеют место семантические действия. Хотя теоретически это и возможно, не существует анализатора РВ-грамматики, поддерживающего косвенную левую рекурсию, в то время как её поддерживают все GLR-анализаторы.

Незаметные ошибки в грамматике

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

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

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

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

Развитость

РВ-грамматики новы, и не получили широкого распространения. Регулярные выражения и КС-грамматики, напротив, существуют уже десятилетия, программный код, их анализирующий, совершенствовался и оптимизировался, а программисты имеют опыт их применения.