Пример языка, порожденного (задаваемого) грамматикой

1) Язык Algol.

Пусть - грамматика:

1) называется контекстно-зависимой, если для каждого правила выполняется ;

2) называется контекстно-свободной, если для каждого правила выполняется ;

3) называется праволинейной, если все правила в отношении имеют вид или , где , , ;

4) называется леволинейной, если все правила в отношении имеют вид или , где , , ;

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

ДОПОНИТЕЛЬНАЯ ИНФОРМАЦИЯ НА ТЕМУ “ФОРМАЛЬНЫХ ГРАММАТИК”

Термины

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

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

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

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

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

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

Σ — набор (алфавит) терминальных символов

N — набор (алфавит) нетерминальных символов

P — набор правил вида: «левая часть» «правая часть», где:

«левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал

«правая часть» — любая последовательность терминалов и нетерминалов

S — стартовый (начальный) символ из набора нетерминалов.

Вывод

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

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

Виды грамматик

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

тип 0. неограниченные грамматики — возможны любые правила

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

тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала.

тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.