Контекстно-свободные (КС) грамматики

Пример построения лексического анализатора

Смотреть методические указания к практическому занятию «Последовательный лексический анализатор»

Неформальный пример. Язык палиндромов над алфавитом .

Палиндром – строка, читаемая одинаково слева направо и справа налево.

Рекурсивное определение языка палиндромов над алфавитом .

Базис. палиндромы.

Индукция. Если палиндром, то палиндромы.

Ни одна цепочка не является палиндромом, если она не определяется этими базисом и индукцией.

КС грамматика – формальная запись подобных рекурсивных определений.

КС грамматика палиндромов над алфавитом :

1. Базис.

2.

3.

4. Индукция

5.

Определение. КС-грамматика - это четверка компонент:

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

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

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

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

1. переменная, (частично) определяемая продукцией. Она называется головой продукции.
2. символ продукции .
3. конечная цепочка, состоящая из терминалов и переменных, возможно, пустая. Она называется телом продукции и представляет способ образования цепочек языка, обозначаемого переменной в голове продукции. По этому способу оставляем терминалы неизменными, а вместо каждой переменной в строке подставляет любую строку, про которую известно, что она принадлежит языку этой продукции.

Описанные четыре компонента образуют контекстно-свободную грамматику (КС-грамматику, КСГ). Будем представлять КСГ ее четырьмя компонентами в виде

, где

конечное множество переменных;

конечное множество терминалов;

конечное множество правил вывода;

начальный символ грамматики.

Соглашение: КС-грамматика определяется перечислением ее правил, причем, первое правило определяет начальный символ грамматики.

Пример 1. КС-грамматика палиндромов

Более короткая запись правил:

Пример 2. КС-грамматика выражений, состоящих из цифр и знаков «+» и «-». Поскольку знаки «+» и «-» должны быть расположены между двумя цифрами, такие выражения можно рассматривать как списки цифр, разделенных знаками «+» и «-».

Из этого списка правил следует, что

;

;

перечислены выше;

начальный символ грамматики.

Пример 3. Упрощенная КС-грамматика выражений типичного языка программирования. Ограничимся операторами «+» и «-», представляющими сложение и умножение. Разрешены идентификаторы, построенные из символов .

Из этого списка правил следует, что

перечислены выше;

начальный символ грамматики.

Дата добавления: 2013-12-14