Просмотр кода страницы Формальная грамматика

<!--- concerning copyright see «legal info» section on the talk page--->
{{Генеративная лингвистика}}
'''Формальная грамматика''' или просто '''грамматика''' в теории [[формальный язык|формальных языков]] — способ описания формального языка, то есть выделения некоторого [[Подмножество|подмножества]] из [[Множество|множества]] всех слов некоторого конечного [[Алфавит (математика)|алфавита]]. Различают ''порождающие'' и ''распознающие'' (или ''аналитические'') грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.

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

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

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

Итак, грамматика определяется следующими характеристиками:
* <math>\Sigma</math> — набор ([[Алфавит (информатика)|алфавит]]) терминальных символов
* N — набор ([[Алфавит (информатика)|алфавит]]) нетерминальных символов
* P — набор правил вида: «левая часть» <math>\rightarrow</math> «правая часть», где:
** «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал
** «правая часть» — любая последовательность терминалов и нетерминалов
* S — стартовый (или начальный) символ грамматики из набора нетерминалов.

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

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

=== Типы грамматик ===
По [[иерархия Хомского|иерархии Хомского]], грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):
* тип 0. [[неограниченная грамматика|неограниченные грамматики]] — возможны любые правила
* тип 1. [[контекстно-зависимая грамматика|контекстно-зависимые грамматики]] — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.
* тип 2. [[контекстно-свободная грамматика|контекстно-свободные грамматики]] — левая часть состоит из одного нетерминала.
* тип 3. [[регулярная грамматика|регулярные грамматики]] — более простые, эквивалентны [[конечный автомат|конечным автоматам]].

Кроме того, выделяют:
* ''Неукорачивающиеся грамматики''. Каждое правило такой грамматики имеет вид <math>\alpha \rightarrow \beta</math>, где <math>|\alpha| \leqslant |\beta|</math>. Длина правой части правила не меньше длины левой{{sfn|Дискретная математика|с=486|2006}}.
* ''Линейные грамматики''. Каждое правило такой грамматики имеет вид <math>A \rightarrow uBv</math>, или <math>A \rightarrow u</math>, то есть в правой части правила может содержаться не более одного вхождения нетерминала{{sfn|Дискретная математика|с=487|2006}}.

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

=== Пример — арифметические выражения ===
Рассмотрим простой язык, определяющий ограниченное подмножество арифметических формул, состоящих из [[Натуральное число|натуральных чисел]], [[Скобки|скобок]] и знаков арифметических действий. Стоит заметить, что здесь в каждом правиле с левой стороны от стрелки <math>\rightarrow</math> стоит только один нетерминальный символ. Такие грамматики называются [[контекстно-свободная грамматика|контекстно-свободными]].

Терминальный алфавит:
 <math>\Sigma</math> = {'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}

Нетерминальный алфавит:
   { ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

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

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

 ФОРМУЛА

'''Вывод''':

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

: <u>ФОРМУЛА</u> <math>\stackrel{3}{\to}</math> <u>(ФОРМУЛА)</u>
: (<u>ФОРМУЛА</u>) <math>\stackrel{1}{\to}</math> (<u>ФОРМУЛА ЗНАК ФОРМУЛА</u>)
: (ФОРМУЛА <u>ЗНАК</u> ФОРМУЛА) <math>\stackrel{4}{\to}</math> (ФОРМУЛА <u> + </u> ФОРМУЛА)
: (ФОРМУЛА + <u>ФОРМУЛА</u>) <math>\stackrel{2}{\to}</math> (ФОРМУЛА + <u>ЧИСЛО</u>)
: (ФОРМУЛА + <u>ЧИСЛО</u>) <math>\stackrel{5}{\to}</math> (ФОРМУЛА + <u>ЦИФРА</u>)
: (ФОРМУЛА + <u>ЦИФРА</u>) <math>\stackrel{7}{\to}</math> (ФОРМУЛА + <u>5</u>)
: (<u>ФОРМУЛА</u> + 5) <math>\stackrel{2}{\to}</math> (<u>ЧИСЛО</u> + 5)
: (<u>ЧИСЛО</u> + 5) <math>\stackrel{6}{\to}</math> (<u>ЧИСЛО ЦИФРА</u> + 5)
: (<u>ЧИСЛО</u> ЦИФРА + 5) <math>\stackrel{5}{\to}</math> (<u>ЦИФРА</u> ЦИФРА + 5)
: (<u>ЦИФРА</u> ЦИФРА + 5) <math>\stackrel{7}{\to}</math> (<u>1</u> ЦИФРА + 5)
: (1 <u>ЦИФРА</u> + 5) <math>\stackrel{7}{\to}</math> (1 <u>2</u> + 5)

<!--
MadLex: сохранено — стоит описать нотацию (НЕТЕРМИНАЛЫ) и сокращение альтернатив (вертикальная черта)

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

-->

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

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

== См. также ==
* [[JFLAP]] — программа-симулятор автоматов, машины Тьюринга, грамматик
* [[Синтаксический анализ]]
* [[Неоднозначная грамматика]]
* [[Задача о наименьшей грамматике]]
* [[Грамматика с фразовой структурой]]
{{викиучебник}}

== Примечания ==
{{Примечания}}

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

{{формальные языки}}

[[Категория:Формальные языки]]
[[Категория:Формальные грамматики|*]]