Грамматика

Более строго, грамматика \(G=(N, \Sigma, P, S)\):

• \(N\) – к.мн. нетерминальные символы (нетерминалов)
• \(\Sigma\) – к.мн. терминальных символов (терминалов), \(\Sigma\cap N=\varnothing\).
• \(P\) – к.мн. правил продукции (продукций) вида \(\alpha A \beta \to \delta,\) где \(\alpha, \beta, \delta \in (\Sigma \cup N)^*\), \(A \in N\)
• \(S \in N\) – стартовый символ или символ предложения.

• в нашем случае, \(\Sigma\) – множество токенов

• Строка порождается последовательной текстовой заменой заголовка продукции на её тело
• Замена называется применением
• Действие замены называется шагом порождения
• Заканчивается, когда строка не содержит нетерминальных символов.
• В начале строка равна \(S\)

• шаг порождения – \(\Rightarrow\)
• \(\overset{*}\Rightarrow\) – за ноль или больше шагов
• \(\overset{+}\Rightarrow\) – за один или больше шагов.

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

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

• Терминальные символы: \(\{ +, n \}\)
• Нетерминальные символы: \(\{ S, P \}\)
• Правила продукции:
  • \(S \to\; P\)
  • \(P \to\; P + n\)
  • \(P \to\; n\)
• Стартовый символ: \(S\).

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

• процесс порождения в виде графа
• Формально – дерево, у которого:
  • Корень помечен \(S\)
  • Каждый лист помечен \(t\in \Sigma\) или \(\varepsilon\) (пустой строкой)
  • Каждый внутренний узел помечен \(n \in N\)
  • Если \(A\in N\), дочерние узлы слева направо \(X_1, \ldots, X_n\), где \(X_i \in N\cup \Sigma\) то \(\exists A \to X_1 \ldots X_n\)
  • Продукции \(A\to \varepsilon\) соответствует узел \(A\) с одним дочерним узлом \(\varepsilon\)
• поиск дерева разбора – разбор или синтаксический анализ
• Послед-сть меток листьев при обходе в глубину слева-направо совпадает с исходной строкой

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

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

• грамматика может иметь более одного дерева разбора для одной строки

• Например для строки “n+n+n” \[\begin{align} S \to\,& P \\ P \to\,& P + P \\ P \to\,& n \\ \end{align}\]

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}\]

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

• называется иерархией, т.к. тип-3 ⊂ тип-2 ⊂ тип-1 ⊂ тип-0.
• если не оговорено иное, будем называть контекстно-зависимыми только языки L ∈ тип-1, которые ∉ тип-0 и т.п.

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

• описывает продукции формальной грамматики
• нетерминалы в угловых скобках
• терминалы в кавычках
• пустая строка – ""
• вместо стрелки – ::=
• продукции с одинаковым заголовком объединяются символом |

• часто добавляют замыкания Клини и позитивного замыкания,
• прочие операторы регулярных выражений
• может использоваться для описания одновременно лексики и грамматики
• если лексика – регулярный язык, она также и КС-язык
• отдельная лексика упрощает грамматику и др.
• не будем прямо использовать БНФ, но заимствуем нотацию |

• В контексте языков программирования в основном интересуют однозначные детерминированные грамматики
• сложность разбора \(O(n)\)
• эффективно обрабатывают неоднозначные грамматики алгоритмы Кока-Янгера-Касами и Эрли, GLR и GLL.

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

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

• Проверка совпадения префиксов тривиальна

• Для выбора продукции два подхода:

  1. Откат
  2. Предпросмотр

Откат

• Выбирается произвольная продукция
• При ошибке, вернуться назад и попробовать другую.
• Если больше вариантов нет – синтаксическая ошибка
• Возможно, самый простой вариант
• Крайне популярен
• Высокая вычислительная сложность (худший случай \(O(n^2)\))
• Менее понятные сообщения об ошибках

Предпросмотр

• Выбор на основе предпросмотра небольшого числа символов входной строки
• Несколько сложнее в реализации
• Более эффективен
• Может сообщать об ошибке сразу
• Сообщения об ошибках могут давать больше контекстной информации

• грамматика с левой рекурсией, т.е. с ситуацией, когда \(A \underset{lm}{\overset{+}\Rightarrow} A\alpha\), приведёт к бесконечной рекурсии анализатора
• разбор грамматики \[\begin{align} S \to\; & P \\ P \to\; & P + n | n \\ \end{align}\] рекурсивным спуском невозможен.

Устранение левой рекурсии

• В большинстве случаев, устранение левой рекурсии возможно чисто механически.
• Тривиальный случай:
  • продукция \(A \to A\alpha | \beta,\)
  • заменяется на продукции \[\begin{align} A \to\;& \beta A', \\ A' \to\;& \alpha A' | \varepsilon, \\ \end{align}\]

• Легко обобщается:
  • \(A \to A\alpha_1 | \ldots | A\alpha_n | \beta_1 | \ldots | \beta_m,\)
  • заменяется на \[\begin{align} A\, & \to \beta_1 A' | \ldots | \beta_m A', \\ A' & \to \alpha_1 A' | \ldots | \alpha_n A' | \varepsilon. \\ \end{align}\]

Упорядочить нетерминальные символы в произвольном порядке;
for(∀ нетерминалов A) {
  for(∀ нетерминалов B < A) {
    for(∀ A -> B α) {
      for(∀ B -> β) {
        Добавить A -> β α;
      }
      Удалить A -> B α;
    }
  }
  Устранить прямую левую рекурсию в продукциях для A;
}

• гарантированно работает на грамматиках, не содержащих циклов (т.е. ситуаций \(A\overset{+}\Rightarrow A\)) и пустых продукций (т.е. продукций вида \(A\to \varepsilon\))

Алгоритм удаления пустых продукций:

while(∃ A → ε) {
  for(∀ B → α A β) {
    Добавить B → α β;
    if (! (∃ A → γ && γ != ε)) {
      Удалить B → α A β;
    }
  }
  Удалить A → ε;
}

После устранения пустых продукций, удаление циклов простым устранением “единичных” правил вида \(A \to B\):

while(∃ A → B) {
  for(∀ B → α && α != B && B → α не было удалено ранее) {
    Добавить A → α;
  }
  Удалить A → B;
}

Пример: