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

Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.

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

• тип 0. неограниченные грамматики — возможны любые правила
• тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.
• тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала.
• Тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.

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

Грамматики с фразовой структурой (тип 0). Этот тип грамматик характеризуется ничем не ограниченным набором правил вида α → с, где α — это любая строка нетерминальных символов, а β — любая строка, составленная из терминальных или нетерминальных символов (их так и называют «unrestricted grammars» — «неограниченные грамматики»).

Свойства этого типа грамматик следующие:

• Они могут использоваться для распознавания любой вычислимой функции. Например, можно создать грамматику (хотя это и не очень просто) для цепочки aⁿb^f(n), представляющей функцию f (n). По заданному n — числу элементов a, эта грамматика генерирует цепочку, содержащую f (n) элементов b.
• Большая часть свойств этих грамматик относится к неразрешимым. Это означает, что не существует процесса, с помощью которого можно было бы определить, выполняется ли данное свойство для всех грамматик данного типа (например, является ли множество цепочек данного языка пустым?). Отличие от контекстно-зависимых грамматик заключается в том, что у последних о многих свойствах просто ничего не известно — они могут быть истинными, ложными или быть неразрешимыми. 

Контекстно-зависимые грамматики (тип 1). Такой тип грамматики характеризуется правилами вида:

α → β

где α — это любая цепочка, состоящая из нетерминальных символов, β — любая цепочка, состоящая из терминальных и нетерминальных символов, и количество символов в α меньше или равно количеству символов в β.

Ниже перечислены некоторые свойства контекстно-зависимых грамматик:

• Все цепочки, последовательно выводимые из начального символа, имеют длину не меньшую, чем предыдущая, поскольку каждое правило должно оставлять длину цепочки неизменной или увеличивать ее (их еще называют неукорачивающими грамматиками).
• Контекстно-зависимые грамматики генерируют цепочки, для хранения которых требуется фиксированный объем памяти. Например, такие грамматики способны распознавать цепочки вида aⁿbⁿcⁿ, что не может сделать контекстно-свободная грамматика.
• Контекстно-зависимые грамматики обычно слишком сложны, чтобы быть практически полезными для моделирования языков программирования.
• Некоторые свойства контекстно-зависимых грамматик до сих пор не исследованы.

Контекстно-свободные грамматики (тип 2). Правила таких грамматик являются правилами НФБ-грамматик (контекстно-свободных грамматик, от «нормальная форма Бэкуса»). Они записываются в форме X —> а, где под а понимается любая последовательность терминальных или нетерминальных символов.

Эти грамматики характеризуются следующими свойствами.

• Многие свойства такой грамматики являются разрешимыми. (Это означает, что можно получить ответы, например, на такие вопросы: генерирует ли
  данная грамматика какие-либо цепочки? Сгенерирована ли этой грамматикой данная цепочка языка? Является ли язык, порождаемый грамматикой,
  пустым?)
• Такие грамматики можно использовать для подсчета вхождения в цепочку двух символов и последующего сравнения. То есть они характеризуются
  цепочками вида aⁿcbⁿ для любого n.
• Контекстно-свободная грамматика может быть «реализована» при помощи стеков. Для распознавания цепочки aⁿcbⁿ из предыдущего пункта можно занести в стек цепочку аⁿ, затем проигнорировать с и сравнить содержимое стека с цепочкой bⁿ, чтобы удостовериться в одинаковой длине этих двух
  цепочек.
• Эти грамматики можно использовать для автоматического построения дерева грамматического разбора.
• Грамматики типа 2 и типа 3 по большей части более не представляют интереса и не являются объектом исследований. Судя по всему, все важные свойства этих грамматик уже изучены.  

Тип 3. Регулярные грамматики обеспечивают модель для конструирования лексического анализатора в трансляторе некоторого языка программирования. Свойства регулярных грамматик таковы:

• Большинство свойств такой грамматики разрешимы. (Это означает, что можно получить ответы, например, на такие вопросы: генерирует ли данная грамматика любые цепочки? Сгенерирована ли этой грамматикой заданная цепочка символов языка? Ограничено ли количество цепочек в языке?)
• Для любой конечной последовательности а и целого п регулярная грамматика может генерировать строки вида а". Это означает, что регулярная грамматика может распознавать любое количество образцов конечной длины.
• С помощью регулярной грамматики можно реализовать счет до любого конечного целого числа. Например, вы можете распознать цепочку {aⁿ
   | n = 147}, если построите КА, в котором будет как минимум 148 состояний. Ввод первых 146 символов не приведет КА в конечное состояние, тогда как
  очередной ввод символа под номером 147 будет принят. Ни один К А с числом состояний ровно 148 не сможет надежно принять цепочку символов
  длиной больше 147.
• Грамматики такого типа часто используются в сканерах (лексических анализаторах) компиляторов для распознавания отдельных лексем (идентификаторов, литералов и строк) или ключевых слов данного языка (например, if, begin, while).

Нормальная форма Хомского

КС-грамматика G = (Т, N, S, R) представлена в нормальной форме Хомского, если она неукорачивающая и каждое ее правило имеет одну из следующих
форм:

А → ВС или А → а, где А, В, C ∈ N, a ∈ Т.

Простыми эквивалентными преобразованиями любую неукорачивающую грамматику можно привести к нормальной форме Хомского. 

Общие методы разбора. Эффективные методы разбора: LL и LR грамматики - как-нибудь потом.