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

Материал из Википедии — свободной энциклопедии

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

[править] Порождающие грамматики

Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.

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

Итак, грамматика определяется следующими характеристиками:

$Σ$ — набор (алфавит) терминальных символов
N — набор (алфавит) нетерминальных символов
R — набор правил вида: «левая часть» «правая часть», где:
- «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал
- «правая часть» — любая последовательность терминалов и нетерминалов
S — стартовый (начальный) символ из набора нетерминалов.

[править] Вывод

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

Существование вывода для некоторого слова является доказательством его принадлежности к языку, определяемому данной грамматикой.

[править] Типы грамматик

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

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

[править] Применение

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

[править] Пример — арифметические выражения

Рассмотрим простой язык, определяющий ограниченное подмножество арифметических формул, состоящих из натуральных чисел, скобок и знаков арифметических действий. Стоит заметить, что здесь в каждом правиле с левой стороны от стрелки $\Rightarrow$ стоит только один нетерминальный символ. Такие грамматики называются контекстно-свободными.

Терминальный алфавит:

 $Σ$ ={'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}.

Нетерминальный алфавит:

  { ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

Правила:

1. ФОРМУЛА  ФОРМУЛА ЗНАК ФОРМУЛА                (формула есть две формулы, соединенные знаком)
2. ФОРМУЛА  ЧИСЛО                               (формула есть число)
3. ФОРМУЛА  ( ФОРМУЛА )                         (формула есть формула в скобках)
4. ЗНАК  + | - | * | /                          (знак есть плюс или минус или умножить или разделить)
5. ЧИСЛО  ЦИФРА                                 (число есть цифра)
6. ЧИСЛО  ЧИСЛО ЦИФРА                           (число есть число и цифра)
7. ЦИФРА  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1 или ... 9 )

Начальный нетерминал:

ФОРМУЛА

Вывод:

Выведем формулу (12+5) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.

ФОРМУЛА $\Rightarrow_3\!\,$ ( ФОРМУЛА )

( ФОРМУЛА ) $\Rightarrow_1\!\,$ ( ФОРМУЛА ЗНАК ФОРМУЛА )

( ФОРМУЛА ЗНАК ФОРМУЛА ) ${\Rightarrow_4\!\,}$ (ФОРМУЛА + ФОРМУЛА )

( ФОРМУЛА + ФОРМУЛА ) ${\Rightarrow_2\!\,}$ ( ФОРМУЛА + ЧИСЛО )

( ФОРМУЛА + ЧИСЛО ) ${\Rightarrow_5\!\,}$ ( ФОРМУЛА + ЦИФРА )

( ФОРМУЛА + ЦИФРА ) ${\Rightarrow_7\!\,}$ ( ФОРМУЛА + 5)

( ФОРМУЛА + 5) ${\Rightarrow_2\!\,}$ ( ЧИСЛО + 5 )

( ЧИСЛО + 5 ) ${\Rightarrow_6\!\,}$ ( ЧИСЛО ЦИФРА + 5)

( ЧИСЛО ЦИФРА + 5 ) ${\Rightarrow_5\!\,}$ ( ЦИФРА ЦИФРА + 5)

( ЦИФРА ЦИФРА + 5 ) ${\Rightarrow_7\!\,}$ ( 1 ЦИФРА + 5)

(1 ЦИФРА + 5) ${\Rightarrow_7\!\,}$ ( 1 2 + 5)

[править] Аналитические грамматики

Порождающие грамматики - не единственный вид грамматик, однако наиболее распространенный в приложениях к программированию. В отличие от порождающих грамматик, аналитическая (распознающая) грамматика задает алгоритм, позволяющий определить, принадлежит ли данное слово языку. Например, любой регулярный язык может быть распознан при помощи грамматики, задаваемой конечным автоматом, а любая контекстно-свободная грамматика — с помощью автомата со стековой памятью. Если слово принадлежит языку, то такой автомат строит его вывод в явном виде, что позволяет анализировать семантику этого слова.

[править] См. также

Грамматический анализ

[править] Источники

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