Грамматика формальная

Грамматика формальная

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

Содержание

Термины

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

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

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

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

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

Вывод

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

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

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

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

Применение

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

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

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

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

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

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

Правила:

1. ФОРМУЛА \Rightarrow\!\, ФОРМУЛА ЗНАК ФОРМУЛА                (формула есть две формулы, соединенные знаком)
2. ФОРМУЛА \Rightarrow\!\, ЧИСЛО                               (формула есть число)
3. ФОРМУЛА \Rightarrow\!\, ( ФОРМУЛА )                         (формула есть формула в скобках)
4. ЗНАК \Rightarrow\!\, + | - | * | /                          (знак есть плюс или минус или умножить или разделить)
5. ЧИСЛО \Rightarrow\!\, ЦИФРА                                 (число есть цифра)
6. ЧИСЛО \Rightarrow\!\, ЧИСЛО ЦИФРА                           (число есть число и цифра)
7. ЦИФРА \Rightarrow\!\, 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.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. - Новосибирск: НГУ. - 1995. - 112 с.
  • Хомский Н., Миллер Дж. Введение в формальный анализ естественных языков // Кибернетический сборник / Под ред. А.А.Ляпунова и О.Б.Лупанова. — М.: Мир, 1965.



Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Грамматика формальная" в других словарях:

  • Грамматика формальная — (в лингвистике)         логическая система, или исчисление, задающая некоторое множество («правильных») цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого «алфавитом» или «основным… …   Большая советская энциклопедия

  • грамматика формальная — В лингвистике: логическая система, или исчисление, задающая некоторое множество ( правильных ) цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого алфавитом или основным (терминальным)… …   Словарь лингвистических терминов Т.В. Жеребило

  • Грамматика формальная —    В лингвистике: логическая система, или исчисление, задающая некоторое множество («правильных») цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого «алфавитом» или «основным (терминальным)… …   Общее языкознание. Социолингвистика: Словарь-справочник

  • Грамматика (наука) — Грамматика (от греч. γράμμα  «запись»), как наука, есть раздел языкознания, изучающий грамматический строй языка, закономерности построения правильных осмысленных речевых отрезков на этом языке (словоформ, синтагм, предложений, текстов). Эти …   Википедия

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

  • Формальная грамматика — ФОРМАЛЬНАЯ ГРАММАТИКА. Грамматика, последовательно проводящая принцип изучения только форм языка и исключающая из своего состава все явления, не обозначенные формами языка. Ф. Г. противополагается т. н. логической (название неточное) грамматике,… …   Литературная энциклопедия

  • Формальная грамматика — Генеративная лингвистика …   Википедия

  • Грамматика — У этого термина существуют и другие значения, см. Грамматика (значения). Грамматика (др. греч. γραμματική от γράμμα  «буква») как наука является разделом языкознания, который изучает грамматический строй языка, закономерности построения… …   Википедия

  • формальная грамматика — см. грамматика формальная (в статье грамматика) …   Словарь лингвистических терминов

  • грамматика описательная — 1) Грамматика, рассматривающая строй слова, словосочетания и предложения в синхронном плане. грамматика формальная. Грамматика, изучающая те отношения в строе предложения, которые имеют формальное выражение. 2) То же, что грамматический строй.… …   Словарь лингвистических терминов


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»