Русская Википедия:Формальная грамматика

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Термины

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

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

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

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

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

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

Вывод

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

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

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

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

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

  • Неукорачивающиеся грамматики. Каждое правило такой грамматики имеет вид <math>\alpha \rightarrow \beta</math>, где <math>|\alpha| \leqslant |\beta|</math>. Длина правой части правила не меньше длины левойШаблон:Sfn.
  • Линейные грамматики. Каждое правило такой грамматики имеет вид <math>A \rightarrow uBv</math>, или <math>A \rightarrow u</math>, то есть в правой части правила может содержаться не более одного вхождения нетерминалаШаблон:Sfn.

Применение

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

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

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

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

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

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

Правила: 

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

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

ФОРМУЛА

Вывод:

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

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


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

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

См. также

Шаблон:Викиучебник

Примечания

Шаблон:Примечания

Литература

Шаблон:Формальные языки

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Формальная_грамматика&oldid=11199683