Контекстно-свободные грамматики и языки

КС грамматики широко используются в практике программирования как способ задания формализованных языков. КС грамматики способны выразить большую часть синтаксиса языков программирования. Применяются также при описании языков HTML, XML, языка описания документов DTD и других.

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

Пример. Возьмем язык палиндромов. Это цепочки символов, читающиеся одинаково справа и слева.

otto madam madamimadam

Для упрощения рассмотрим палиндромы в алфавите {0, 1}.

00100 10101

Выразим определение языка палиндромов в виде КС-грамматики:

Первые три правила говорят, что язык палиндромов включает цепочки из пустых символов, 0 и 1.

Четвертое и пятое правила – если взять произвольную цепочку w из языка Р, то 0 w 0 и 1 w 1 также будут в языке Р.

Эти 4 компонента образуют КС-грамматику. Будем представлять КС-грамматику в виде:

G = (V, T, P, S),

где V – множество переменных, T – терминалов, P – правил вывода, S – стартовый символ.

Пример 1.

G_pal = ({P}, {0, 1}, A, P)

где А – вышеприведенные правила вывода.

Грамматика G_pal порождает цепочки языка палиндромов: 10101, 01010, 0110, …

Выведем первую цепочку с помощью грамматики палиндромов:

P → 1P1 → 10P01 → 10101

Пример 2.

Допустим язык выражений типичного языка программирования состоит из идентификаторов, которые начинаются с буквы a или b, за которой следует цепочка { a,b,0,1 } и арифметических операторов + и *.

(a + b) * (a + b + a0 + a1)

Введем для грамматики 2 переменные:

Е – выражения языка, стартовый символ

I – идентификаторы языка

G_выр= ({Е, I}, {a, b, 0, 1, +, *}, A, E)

где A = { E→I | E+E | E*E | (E), I→a | b | Ia | Ib | I0 | I1 }

Упрощенная запись грамматики:

G_выр = { E→I | E+E | E*E | (E), I→a | b | Ia | Ib | I0 | I1 }

Теперь рассмотрим, как выводится из построенной грамматики вышеуказанная цепочка

(a + b) * (a + b + a0 + a1)

E → E*E → (E)*(E) → (E+E)*(E+E) → (I+I)*(E+E+E+E) → (a+b)*(I+I+I+I) →

→ (a+b)*(a+b+I0+I1) → (a+b)*(a+b+a0+a1)

Вывод в КС-грамматике удобно представлять с помощью дерева вывода.

Закрепление материала:

1. Составить последовательность вывода цепочки 101101 из грамматики палиндромов.

2. Составить последовательность вывода цепочки (a+b0)*a0+b из грамматики выражений.