КС грамматики широко используются в практике программирования как способ задания формализованных языков. КС грамматики способны выразить большую часть синтаксиса языков программирования. Применяются также при описании языков 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.
Gpal = ({P}, {0, 1}, A, P)
где А – вышеприведенные правила вывода.
Грамматика Gpal порождает цепочки языка палиндромов: 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 из грамматики выражений.