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

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

Пример построения грамматики

Примером языка может являться множество различных корректных формул, включающих в себя натуральные числа, скобки и знаки арифметических действий. Алфавитом в этом случае будет множество $\Sigma$ ={'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}. Например, строка (2+3)*(5+7) будет словом такого языка, а строка +2(3-1( не будет (хотя она и состоит из допустимых символов, но записана с очевидными ошибками). Как можно описать этот язык? Мы знаем, что числа состоят из цифр и могут объединяться с помощью знаков арифметических действий в формулы (например, формулой будет цепочка 2+3). Формулы можно заключать в скобки, а также складывать, вычитать, умножать и делить — то есть объединять друг с другом (и с числами) в более сложные формулы. Например, (2+3)*(5+7) — это сложная формула, состоящая из двух более простых, ее можно символически записать следующим образом: ФОРМУЛА ЗНАК ФОРМУЛА. Заметим, что вместо слов ФОРМУЛА можно подставить любую корректную формулу, а вместо слова ЗНАК — знак любого арифметического действия, и эта строка останется правильной формулой.

Идея теории порождающих формальных грамматик, разработанной Н.Хомским, состоит в том, чтобы описывать язык через правила подстановок, которые позволяют строить слова языка из «кирпичиков», описываемых с помощью других «кирпичиков». Правила языка при этом можно записывать, просто указывая, какие цепочки «кирпичиков» можно подставлять вместо других «кирпичиков». Например, разобранное выше правило построения сложных формул из простых можно записать следующим образом (такая запись называется правилом вывода)

1. ФОРМУЛА $\Rightarrow \!\,$ ФОРМУЛА ЗНАК ФОРМУЛА

Правило нужно читать так: «вместо слова ФОРМУЛА можно подставить цепочку ФОРМУЛА ЗНАК ФОРМУЛА». При этом вместо «кирпичика» ЗНАК можно подставлять один из четырех символов алфавита $\Sigma$ : (+,-,*./). Это можно записать с помощью следующих четырех правил.

2. ЗНАК $\Rightarrow \!\,$ +

3. ЗНАК $\Rightarrow \!\,$ -

4. ЗНАК $\Rightarrow \!\,$ *

5. ЗНАК $\Rightarrow \!\,$ /

Такая запись обычно сокращается до следующей (символ "|" не принадлежит $\Sigma$ ).

6. ЗНАК $\Rightarrow \!\,$ + | - | * | /

«Кирпичики», обозначаемые нами большими буквами (например, ЗНАК), не являются символами рабочего алфавита $\Sigma$ (хотя и могут быть на них заменены в процессе подстановок). Они называются «нетерминалами» (или «нетерминальными символами»), в отличие от букв алфавита $\Sigma$ , называющихся терминалами. Смысл этих названий состоит в том, что нетерминал может быть заменен на цепочку других символов (как в случае с нетерминалом ФОРМУЛА), в то время как терминал уже ни на что заменен быть не может и является своеобразным «пунктом назначения» наших замен (от англ. terminal — конечный пункт). Чтобы получить слово языка, мы должны все нетерминалы в конечном итоге заменить на терминалы, а для этого в описание языка должны входить соответствующие правила.

В рассмотренном примере для определения нетерминала ЧИСЛО можно ввести такие правила

7. ЧИСЛО $\Rightarrow \!\,$ ЦИФРА | ЧИСЛО ЦИФРА

8. ЦИФРА $\Rightarrow \!\,$ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Иными словами, если к числу приписать справа еще одну цифру, то получится снова число. Одно число — это также корректная формула, что записывается следующим образом:

9. ФОРМУЛА $\Rightarrow \!\,$ ЧИСЛО

Для полного описания грамматики нам требуется также разрешить заключать формулы в скобки. Это делается с помощью правила

10. ФОРМУЛА $\Rightarrow \!\,$ ( ФОРМУЛА )

Надо отметить, что нетерминал ФОРМУЛА в нашем случае является выделенным — он задает правильные формулы, то есть слова нашего языка, в то время как, например, нетерминал ЗНАК не задает слово языка. В таком случае говорят, что нетерминал ФОРМУЛА является начальным.

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

Пример вывода

Выведем формулу (12+5) с помощью перечисленных правил вывода:

ФОРМУЛА $\Rightarrow _{10}\!\,$ (ФОРМУЛА) $\Rightarrow _{1}\!\,$ (ФОРМУЛА ЗНАК ФОРМУЛА) ${\Rightarrow _{2}\!\,}$ (ФОРМУЛА + ФОРМУЛА) ${\Rightarrow _{9}\!\,}$ (ФОРМУЛА + ЧИСЛО) ${\Rightarrow _{7}\!\,}$ (ФОРМУЛА + ЦИФРА) ${\Rightarrow _{8}\!\,}$ (ФОРМУЛА + 5) ${\Rightarrow _{9}\!\,}$ (ЧИСЛО + 5) ${\Rightarrow _{7}\!\,}$ (ЧИСЛО ЦИФРА + 5) ${\Rightarrow _{7}\!\,}$ (ЦИФРА ЦИФРА + 5) ${\Rightarrow _{8}\!\,}$ (12+5)

В приведенном примере с левой стороны от стрелки $\Rightarrow$ в каждом правиле вывода стоял только один нетерминальный символ. Такие грамматики называются контекстно-свободными. Это не единственный вид грамматик, однако наиболее распространенный в приложениях к программированию. В отличие от порождающих грамматик, пример которой был рассмотрен выше, распознающая грамматика задает алгоритм, позволяющий определить, принадлежит ли данное слово языку. Например, любой регулярный язык может быть распознан при помощи грамматики, задаваемой конечным автоматом, а любая контекстно-свободная грамматика — с помощью автомата со стековой памятью. Если слово принадлежит языку, то такой автомат строит его вывод в явном виде, что позволяет анализировать семантику этого слова.

Типы грамматик

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

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

Применение

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

См. также

Ссылки

Павел Гуданец Введение в теорию формальных систем Архивировано из первоисточника 27 апреля 2010.

Источники

А. В. Гладкий Формальные грамматики и языки. — М.: Наука, 1973.
Н. Хомский, Дж. Миллер Введение в формальный анализ естественных языков // Кибернетический сборник / Под ред. А.А.Ляпунова и О.Б.Лупанова. — М.: Мир, 1965.