Определение контекстно-свободных грамматик

Рассмотрим пример:Пусть дан язык палиндромов. W – палиндром, если . Алфавит: . Рассмотрим - все палиндромы в этом алфавите. Используя лемму о накачке покажем, что данный язык не регулярен. От противного. Пусть указанный язык регулярен. Тогда константой из леммы назовем n. . Если язык регулярен, то w=xyz. Пусть . Значит, в слове xz (при к=0) слева от «1» будет нулей меньше, чем справа. Что противоречит регулярности рассматриваемого языка.

Существует рекурсивное определение того, что цепочка из символов «0» и «1» является палиндромом. Это описание начинается с базиса: палиндромы. Индукция: Если w – палиндром, то 0w0 и 1w1 так же палиндромы. Ни одна цепочка не является палиндромом, если не определяется этим базисом и индукцией. Контекстно-свободная грамматика представляет собой формальную запись подобных рекурсивных определений языка. Грамматика состоит из одной или нескольких переменных, которые представляют собой классы цепочек или языки. В данном примере нам нужна только одна переменная, представляющая собой множество палиндромов, т.е. класс цепочек, образующих язык . Имеются правила построения цепочек каждого класса. При построении используются символы алфавита и уже построенные цепочки из различных классов, правило определения полиномов. Выражение в виде контекстно-свободных грамматик выглядит следующим образом:

В базисе правая часть не содержит переменных.

Это понимать так: Если взять произвольную цепочку w из класса палиндромов P, то 0w0 так же будет находится в классе P.

Описание языка с помощью грамматик состоит из четырех компонент:

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

2. Существует конечное множество переменных, называемых не терминалами (синтаксические категории).

3. Одна из переменных представляет определяемый язык и она называется стартовым символом. Другие переменные представляют дополнительные классы цепочек, которые помогают определить язык, заданный стартовым символом.

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

а). Переменная, определяемая продукцией. Эту переменную часто называют «головой продукции».

б). Символ продукции:

в). Конечная цепочка, состоящая из терминалов и переменных (возможно и пустая), называемая «телом продукции» и представляющая способ образования цепочек языка, указанных в голове продукции. По этому способу мы оставляем терминалы неизменными и вместо каждой переменной в теле подставляем любую цепочку, про которую известно, что она принадлежит языку этой переменной. Обозначается: , где V – множество переменных, T – множество терминалов, P – множество продукций, S – стартовый символ.

Исходя из этого, грамматику палиндромов можно записать как: , где А – множество из 5 продукций, описанных выше. Сокращенная форма записи:

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

2 операции: + *

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

В нашей грамматики нужны 2 переменные:

E – выражение, определяемого языка, является стартовым символом

I – идентификаторы. Ее язык в действительности регулярен и задается (a+b)(a+b+0+1)*

Правила для упрощения языка программирования:

1. E I (базисное для выражений – выр-ие может быть одиночным идентификатором)

2. E E + E

3. E E*E индуктивное образование выражений

4. E (E)

5. I a

6. I b базис для идентификатора (a и b - идентификаторы)

7. I Ia

8. I Ib индуктивный переход для идентификатора

9. I I0 (имея произвольный идентификатор мы можем приписать к нему

10. I I1 справа a,b,0 или 1 и получить еще один идентификатор)

E I|E+E|E*E|(E)

I a|b|Ia|Ib|I0|I1

G=({E,I}, {a,b,0,1,+,*,(,)}, P, E)