Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.
Термины Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спецсимволы. Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.
Порождающие грамматики Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.
Чтобы задать грамматику, требуется задать алфавиты терминалов и нетерминалов, набор правил вывода, а также выделить в множестве нетерминалов начальный.
Итак, грамматика определяется следующими характеристиками: — набор (алфавит) терминальных символов N — набор (алфавит) нетерминальных символов P — набор правил вида: «левая часть» «правая часть», где: «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал «правая часть» — любая последовательность терминалов и нетерминалов S — стартовый (или начальный) символ грамматики из набора нетерминалов.
Вывод Выводом называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путём замены некоторой подстроки по одному (любому) из правил. Конечной строкой является строка, полностью состоящая из терминалов, и следовательно являющаяся словом языка.
Существование вывода для некоторого слова является критерием его принадлежности к языку, определяемому данной грамматикой.
Типы грамматик По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу): тип 0. неограниченные грамматики — возможны любые правила тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части. тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала. тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.
Кроме того, выделяют: Неукорачивающиеся грамматики. Каждое правило такой грамматики имеет вид , где . Длина правой части правила не меньше длины левой. Линейные грамматики. Каждое правило такой грамматики имеет вид , или , то есть в правой части правила может содержаться не более одного вхождения нетерминала.
Применение Контекстно-свободные грамматики широко применяются для определения грамматической структуры в грамматическом анализе. Регулярные грамматики (в виде регулярных выражений) широко применяются как шаблоны для текстового поиска, разбивки и подстановки, в том числе в лексическом анализе.
Пример — арифметические выражения Рассмотрим простой язык, определяющий ограниченное подмножество арифметических формул, состоящих из натуральных чисел, скобок и знаков арифметических действий. Стоит заметить, что здесь в каждом правиле с левой стороны от стрелки стоит только один нетерминальный символ. Такие грамматики называются контекстно-свободными.
Терминальный алфавит: = {'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}
Нетерминальный алфавит: { ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }
Правила: 1. ФОРМУЛА ФОРМУЛА ЗНАК ФОРМУЛА (формула есть две формулы, соединенные знаком) 2. ФОРМУЛА ЧИСЛО (формула есть число) 3. ФОРМУЛА ( ФОРМУЛА ) (формула есть формула в скобках) 4. ЗНАК + | - | * | / (знак есть плюс или минус, или умножить, или разделить) 5. ЧИСЛО ЦИФРА (число есть цифра) 6. ЧИСЛО ЧИСЛО ЦИФРА (число есть число и цифра) 7. ЦИФРА 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1, или ... 9 )
Начальный нетерминал:
ФОРМУЛА
Вывод:
Выведем формулу (12+5) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.
ФОРМУЛА (ФОРМУЛА) (ФОРМУЛА) (ФОРМУЛА ЗНАК ФОРМУЛА) (ФОРМУЛА ЗНАК ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ЧИСЛО) (ФОРМУЛА + ЧИСЛО) (ФОРМУЛА + ЦИФРА) (ФОРМУЛА + ЦИФРА) (ФОРМУЛА + 5) (ФОРМУЛА + 5) (ЧИСЛО + 5) (ЧИСЛО + 5) (ЧИСЛО ЦИФРА + 5) (ЧИСЛО ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) (1 ЦИФРА + 5) (1 ЦИФРА + 5) (1 2 + 5)
Аналитические грамматики
Порождающие грамматики — не единственный вид грамматик, однако наиболее распространенный в приложениях к программированию. В отличие от порождающих грамматик, аналитическая (распознающая) грамматика задает алгоритм, позволяющий определить, принадлежит ли данное слово языку. Например, любой регулярный язык может быть распознан при помощи грамматики, задаваемой конечным автоматом, а любая контекстно-свободная грамматика — с помощью автомата со стековой памятью. Если слово принадлежит языку, то такой автомат строит его вывод в явном виде, что позволяет анализировать семантику этого слова.
См. также JFLAP — программа-симулятор автоматов, машины Тьюринга, грамматик Синтаксический анализ Неоднозначная грамматика Задача о наименьшей грамматике Грамматика с фразовой структурой
Примечания
Литература
Ссылки Формальные грамматики и языки. Элементы теории трансляции / И.А. Волкова, А.А. Вылиток, Т.В. Руденко // учеб. пос. ВМК МГУ. - М.: МГУ, 2009. - 115 с. ISBN 978-5-89407-395-8. Теория формальных языков // Вики ИТМО. Теория и реализация языков программирования / В.А. Серебряков и др. - М.: МЗ Пресс, 2006. - 352 с. - ISBN 5-94073-094-9.
Категория:Формальные языки *