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

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

ТерминыПравить

• Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спецсимволы.
• Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

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

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

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

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

• $\mathrm{\Sigma <!--\; \Sigma \; -->}$$\Sigma$  — набор (алфавит) терминальных символов
• N — набор (алфавит) нетерминальных символов
• P — набор правил вида: «левая часть» $\to <!--\; \to \; -->$$\rightarrow$  «правая часть», где:
  • «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал
  • «правая часть» — любая последовательность терминалов и нетерминалов
• S — стартовый (или начальный) символ грамматики из набора нетерминалов.

ВыводПравить

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

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

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

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

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

Кроме того, выделяют:

• Неукорачивающиеся грамматики. Каждое правило такой грамматики имеет вид $\mathrm{\alpha <!--\; \alpha \; -->}\to <!--\; \to \; -->\mathrm{\beta <!--\; \beta \; -->}$$\alpha \rightarrow \beta$ , где $|\mathrm{\alpha <!--\; \alpha \; -->}|⩽<!--\; ⩽\; -->|\mathrm{\beta <!--\; \beta \; -->}|$$|\alpha |\leqslant |\beta |$ . Длина правой части правила не меньше длины левой.
• Линейные грамматики. Каждое правило такой грамматики имеет вид $A\to <!--\; \to \; -->uBv$$A\rightarrow uBv$ , или $A\to <!--\; \to \; -->u$$A\rightarrow u$ , то есть в правой части правила может содержаться не более одного вхождения нетерминала.

ПрименениеПравить

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

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

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

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

$\mathrm{\Sigma <!--\; \Sigma \; -->}$$\Sigma$  = {'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}

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

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

Правила:

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

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

ФОРМУЛА

Вывод:

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

ФОРМУЛА $\stackrel{3}{\to <!--\; \to \; -->}$${\stackrel {3}{\to }}$  (ФОРМУЛА)

(ФОРМУЛА) $\stackrel{1}{\to <!--\; \to \; -->}$${\stackrel {1}{\to }}$  (ФОРМУЛА ЗНАК ФОРМУЛА)

(ФОРМУЛА ЗНАК ФОРМУЛА) $\stackrel{4}{\to <!--\; \to \; -->}$${\stackrel {4}{\to }}$  (ФОРМУЛА + ФОРМУЛА)

(ФОРМУЛА + ФОРМУЛА) $\stackrel{2}{\to <!--\; \to \; -->}$${\stackrel {2}{\to }}$  (ФОРМУЛА + ЧИСЛО)

(ФОРМУЛА + ЧИСЛО) $\stackrel{5}{\to <!--\; \to \; -->}$${\stackrel {5}{\to }}$  (ФОРМУЛА + ЦИФРА)

(ФОРМУЛА + ЦИФРА) $\stackrel{7}{\to <!--\; \to \; -->}$${\stackrel {7}{\to }}$  (ФОРМУЛА + 5)

(ФОРМУЛА + 5) $\stackrel{2}{\to <!--\; \to \; -->}$${\stackrel {2}{\to }}$  (ЧИСЛО + 5)

(ЧИСЛО + 5) $\stackrel{6}{\to <!--\; \to \; -->}$${\stackrel {6}{\to }}$  (ЧИСЛО ЦИФРА + 5)

(ЧИСЛО ЦИФРА + 5) $\stackrel{5}{\to <!--\; \to \; -->}$${\stackrel {5}{\to }}$  (ЦИФРА ЦИФРА + 5)

(ЦИФРА ЦИФРА + 5) $\stackrel{7}{\to <!--\; \to \; -->}$${\stackrel {7}{\to }}$  (1 ЦИФРА + 5)

(1 ЦИФРА + 5) $\stackrel{7}{\to <!--\; \to \; -->}$${\stackrel {7}{\to }}$  (1 2 + 5)

Аналитические грамматикиПравить

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

См. такжеПравить

• JFLAP — программа-симулятор автоматов, машины Тьюринга, грамматик
• Синтаксический анализ
• Неоднозначная грамматика
• Задача о наименьшей грамматике
• Грамматика с фразовой структурой

ЛитератураПравить

• Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 743 с. — ISBN 5-7038-2886-4.
• Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973.
• Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. — 112 с.
• Хомский Н., Миллер Дж. Введение в формальный анализ естественных языков // Кибернетический сборник / Под ред. А.А.Ляпунова и О.Б.Лупанова. — М.: Мир, 1965.
• Гросс М., Лантен А. Теория формальных грамматик. — М.: Мир, 1971. — 296 с.