Формальные грамматики

Итак, что имеется в виду под формальной грамматикой?

В теории формальных языков, формальная грамматика, или, для краткости, просто грамматика, описывает как, используя лексику языка, сконструировать строки, соответствующие синтаксису (т.е. – корректные). При этом, значение не принимается в расчёт, рассматривается только синтаксис.

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

Грамматика

Более строго, грамматика \(G\) состоит из следующего:

• Конечного множества нетерминальных символов \(N\) (сокращённо нетерминалов), непересекающееся с множеством строк, порождаемых \(G\).
• Конечного множества терминальных символов \(\Sigma\) (сокращённо терминалов), непересекающегося с \(N\).
• Конечного множества правил продукции \(P\) (сокращённо, продукций), каждое из которых имеет форму \[\alpha A \beta \to \delta,\] где \(\alpha, \beta, \delta \in (\Sigma \cup N)^*\) – произвольные строки терминальных и нетерминальных символов (\(^*\) – замыкание Клини), \(A \in N\) – нетерминальный символ. Часть слева от стрелки называется заголовком или левой частью продукции. Часть справа от стрелки – телом или правой частью. Вместо стрелки может использоваться \(::=\). Если тело является пустой строкой, часто используется обозначение \(\varepsilon\).
• Символа \(S \in N\), называемого стартовым или символом предложения.

Формальная грамматика определяется как кортеж \((N, \Sigma, P, S)\).

Отметим, что в нашем случае, множество терминалов эквивалентно множеству токенов, т.е. каждый терминальный символ соответствует какому-то токену лексического анализатора.

Конкретная строка порождается грамматикой через процесс последовательной текстовой замены в строке левой части правила продукции на правую часть того же правила продукции. В начальном состоянии, строка состоит из стартового символа. Такая замена называется применением правила продукции. Одно действие замены называется шагом порождения. Процесс заканчивается, когда строка не содержит нетерминальных символов.

Будем обозначать шаг порождения символом \(\Rightarrow\). Для удобства, введём также обозначения \(\overset{*}\Rightarrow\) для порождения за ноль или больше шагов и \(\overset{+}\Rightarrow\) для порождения за один или больше шагов.

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

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

• Левое порождение. На каждом шаге порождения заменяется самый левый нетерминальный символ. Левые порождения будем при необходимости обозначать \(\underset{lm}\Rightarrow\).
• Правое порождение. На каждом шаге порождения заменяется самый правый нетерминальный символ. Правые порождения будем при необходимости обозначать \(\underset{rm}\Rightarrow\).

Пример

Рассмотрим грамматику, определяющую синтаксис бинарного оператора \(+\) над некоторыми лексическими единицами (обозначим их \(n\)).

Терминальные символы: \(\{ +, n \}\)

Нетерминальные символы: \(\{ S, P \}\)

Правила продукции:

\[\begin{align} S \to\; & P \\ P \to\; & P + n \\ P \to\; & n \\ \end{align}\]

Стартовый символ: \(S\).

Эта грамматика порождает, например, строку \(n+n+n\) (записывается \(S \overset{*}\Rightarrow n+n+n\)) следующим образом:

\(S \Rightarrow P \Rightarrow P + n \Rightarrow P +n+n \Rightarrow n+n+n\)

Можно отметить, что на каждом шаге используется левое порождение, поэтому можно так же записать

\(S \underset{lm}\Rightarrow P \underset{lm}\Rightarrow P + n \underset{lm}\Rightarrow P +n+n \underset{lm}\Rightarrow n+n+n\)

Деревья разбора

Дерево разбора является представлением в виде графа процесса порождения данной строки языка его грамматикой. Формально, дерево разбора представляет из себя дерево, у которого:

• Корень помечен стартовым символом грамматики
• Каждый лист помечен терминальным символом или \(\varepsilon\) (пустой строкой)
• Каждый внутренний узел помечен нетерминалом
• Если \(A\) – нетерминал, и его дочерние узлы слева направо имеют метки \(X_1, \ldots, X_n\), где \(X_i\) – терминальный или нетерминальный символ, то существует продукция \(A \to X_1 \ldots X_n\). Продукции \(A\to \varepsilon\) соответствует узел \(A\) с одним дочерним узлом \(\varepsilon\).

Процесс поиска дерева разбора для данной строки называется разбором или синтаксическим анализом этой строки.

Последовательность меток листьев дерева при обходе в глубину слева-направо будет совпадать с исходной строкой.

Пример

Дерево разбора строки “n+n+n” в соответствии с грамматикой, приведённой выше, будет иметь вид:

Однозначность грамматики

В общем случае, грамматика может иметь более одного дерева разбора для данной строки. Например, грамматика с продукциями вида \[\begin{align} S \to\,& P \\ P \to\,& P + P \\ P \to\,& n \\ \end{align}\] будет иметь два дерева разбора для строки “n+n+n”:

Иерархия Хомского

Ноам Хомский, стоявший у истоков формальной теории языков, ввёл следующую классификацию формальных грамматик на основе допустимого вида правил продукции. Здесь греческими буквами обозначены произвольные (возможно пустые) строки терминалов и нетерминалов, причём \(\gamma\) – непустая, прочие – возможно пустые. \(A, B\) – нетерминальные символы (возможно одинаковые), \(a\) – какой-либо терминальный символ.

1. Тип-0. Неограниченные грамматики. Допускается любой вид правил продукции, \[\alpha A \beta \to \delta.\]
2. Тип-1. Контекстно-зависимые грамматики. Допускаются продукции вида \[\alpha A \beta \to \alpha \gamma \beta.\]
3. Тип-2. Контекстно-свободные грамматики. Допускаются продукции вида \[A \to \alpha.\]
4. Тип-3. Регулярные грамматики. Допускаются продукции вида \[\begin{align} A & \to a, \\ A & \to a B, \\ \end{align}\] такие грамматики называются праворегулярными, или \[\begin{align} A & \to a, \\ A & \to B a, \\ \end{align}\] такие грамматики называются леворегулярными. Отдельно стоит отметить, что грамматика, содержащая одновременно продукции \[\begin{align} A & \to B a, \\ A & \to a B, \\ \end{align}\] не является регулярной.

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

Языки, описываемые только неограниченными грамматиками, называются рекурсивно-перечислимыми.

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

Эти типы выделены не произвольно: каждый тип требует определённой вычислительной мощности для разбора, и соотносится с определённым классом автоматов из теории автоматов:

1. Тип-0 соответствует абстрактной машине Тьюринга (МТ).
2. Тип-1 соответствует линейно-ограниченной недетерминированной машине Тьюринга (размер ленты – “памяти” – есть линейная функция размера входных данных)
3. Тип-2 соответствует недетерминированному автомату с магазинной памятью (НАМП)
4. Тип-3 соответствует конечному автомату (КА).

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

Форма Бэкуса-Наура

Форма Бэкуса-Наура¹ (БНФ, BNF) – это способ записи контекстно-свободных грамматик. Существует несколько вариаций, две из них широко используются, и известны как расширенная форма Бэкуса-Наура (РБНФ, EBNF) и дополненная форма Бэкуса-Наура (ДБНФ, ABNF).

Формально, БНФ описывает правила продукций формальной грамматики. При этом, имена нетерминалов заключаются в угловые скобки, имена терминалов – в двойные или одинарные кавычки, пустая строка обозначается как "", вместо стрелки используется обозначение ::=, и наконец, продукции с одинаковым заголовком объединяются в одну, различные тела разделяются символом |. Например, БНФ для грамматики, приведённой выше, будет иметь вид:

<S> ::= <P>
<P> ::= <P> "+" "n" | "n"

Частая модификация – добавление замыкания Клини и позитивного замыкания, а так же прочих операторов из синтаксиса регулярных выражений (применяемых к подпоследовательностям терминалов и нетерминалов в теле продукций), в частности РБНФ и ДБНФ вносят такие модификации (кроме того, что значительно изменяют синтаксис).

Отдельно заметим, что часто БНФ (или скорее одна из модификаций) используется для описания одновременно лексики и грамматики. Действительно, если считать, что лексика представляет собой регулярный язык, она может быть так же описана в терминах контекстно-свободной грамматики. Отделение лексики, однако, имеет некоторые преимущества, о которых мы говорили ранее.

Мы не будем прямо использовать БНФ при описании грамматик, однако для удобства заимствуем из него нотацию с | для объединения продукций с одинаковым заголовком.

Проблема разбора

С точки зрения компиляции, в первую очередь нас интересуют контекстно-свободные языки. Редкий язык является действительно контекстно-свободным, например, необходимость объявления переменных перед их использованием может проверена в рамках контекстно-зависимой грамматики. Однако, практически, разбор контекстно-зависимых языков является крайне сложной задачей (формально относится к классу PSPACE-полных, иначе говоря, как минимум NP-сложных), и самые эффективные алгоритмы её решения – фантастически медленные (хуже любых полиномиальных).

В то же время, разбор контекстно-свободной грамматики относится к классу P и имеет теоретическую сложность не хуже \(O(n^3)\) (по более точным оценкам, не хуже \(O(n^{2.373})\)).

Кроме того, в контексте языков программирования, нас будут в основном интересовать однозначные грамматики детерминистических языков (т.е. языков, которые могут быть разобраны детерминированным автоматом с магазинной памятью), сложность разбора которых оказывается ещё меньше, \(O(n)\).

Существуют т.н. универсальные методы синтаксического анализа, которые эффективно обрабатывают неоднозначные грамматики, строя все возможные деревья разбора. К ним относятся алгоритмы Кока-Янгера-Касами и Эрли, GLR и GLL.

Выделяются два подхода к синтаксическому анализу:

• Восходящие. Алгоритмы Кока-Янгера-Касами, LR и GLR используют этот подход. С точки зрения языков программирования, практический интерес представляют в основном детерминистические контекстно-свободные языки, которые могут быть разобраны алгоритмом LR.
• Нисходящие. Алгоритмы Эрли и LL используют этот подход. Для нас в основном интересны т.н. LL-языки, являющиеся подмножеством детерминистических контекстно-свободных языков. На практике, LL-грамматики имеют некоторые неприятные ограничения, однако нисходящие синтаксические анализаторы достаточно эффективны и просты в разработке.