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

Разделы:

.ts-Боковая_навигационная_таблица-preTitle{padding-top:0}.mw-parser-output .ts-Боковая_навигационная_таблица-image{padding:0.4em 0 0.4em}.mw-parser-output .ts-Боковая_навигационная_таблица-title{padding:0.2em 0.4em 0.2em;font-size:125%;line-height:1.15em;font-weight:bold;background:#cfe3ff}.mw-parser-output .ts-Боковая_навигационная_таблица-above,.mw-parser-output .ts-Боковая_навигационная_таблица-below{padding:0.2em 0.4em 0.2em;font-weight:bold}.mw-parser-output .ts-Боковая_навигационная_таблица-heading{padding:0.2em 0;font-weight:bold;background:#eaf3ff}.mw-parser-output .ts-Боковая_навигационная_таблица-list{padding:0.2em 0}]]>

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

Содержание

1 Термины
2 Порождающие грамматики
3 Аналитические грамматики
4 См. также
5 Источники

Термины

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

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

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

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

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

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

Вывод

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

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

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

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

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

Применение

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

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

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

$Rightarrow$ стоит только один нетерминальный символ. Такие грамматики называются контекстно-свободными.

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

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

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

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

Правила:

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

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

ФОРМУЛА

Вывод:

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

ФОРМУЛА ⇒3{displaystyle Rightarrow _{3}!,}

{displaystyle Rightarrow _{3}!,}

(ФОРМУЛА)

(ФОРМУЛА) ⇒1{displaystyle Rightarrow _{1}!,}

{displaystyle Rightarrow _{1}!,}

(ФОРМУЛА ЗНАК ФОРМУЛА)

(ФОРМУЛА ЗНАК ФОРМУЛА) ⇒4{displaystyle {Rightarrow _{4}!,}}

{displaystyle {Rightarrow _{4}!,}}

(ФОРМУЛА + ФОРМУЛА)

(ФОРМУЛА + ФОРМУЛА) ⇒2{displaystyle {Rightarrow _{2}!,}}

{displaystyle {Rightarrow _{2}!,}}

(ФОРМУЛА + ЧИСЛО)

(ФОРМУЛА + ЧИСЛО) ⇒5{displaystyle {Rightarrow _{5}!,}}

{displaystyle {Rightarrow _{5}!,}}

(ФОРМУЛА + ЦИФРА)

(ФОРМУЛА + ЦИФРА) ⇒7{displaystyle {Rightarrow _{7}!,}}

{displaystyle {Rightarrow _{7}!,}}

(ФОРМУЛА + 5)

(ФОРМУЛА + 5) ⇒2{displaystyle {Rightarrow _{2}!,}}

{displaystyle {Rightarrow _{2}!,}}

(ЧИСЛО + 5)

(ЧИСЛО + 5) ⇒6{displaystyle {Rightarrow _{6}!,}}

{displaystyle {Rightarrow _{6}!,}}

(ЧИСЛО ЦИФРА + 5)

(ЧИСЛО ЦИФРА + 5) ⇒5{displaystyle {Rightarrow _{5}!,}}

{displaystyle {Rightarrow _{5}!,}}

(ЦИФРА ЦИФРА + 5)

(ЦИФРА ЦИФРА + 5) ⇒7{displaystyle {Rightarrow _{7}!,}}

{displaystyle {Rightarrow _{7}!,}}

(1 ЦИФРА + 5)

(1 ЦИФРА + 5) ⇒7{displaystyle {Rightarrow _{7}!,}}

{displaystyle {Rightarrow _{7}!,}}

(1 2 + 5)

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

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

См. также

Имеется викиучебник по теме «Формальная грамматика»

Источники

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

Это статья-заготовка по математике. Помогите Википедии, дополнив эту статью, как и любую другую.