2.3. Общие методы синтаксического анализа 81

Алгоритм нахождения левого разбора по таблице разбора 86

1. Класс контекстно-свободных языков (V-3.0 28.02.2009)

1.1. Свойства кс-языков

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

: , , .

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

: , , .

Определение: Пусть - класс языков и язык принадлежит . Допустим, что алфавит , где , является алфавитом языка и языки принадлежат классу . Тогда класс замкнут относительно операции подстановки, если для произвольного набора язык

,

где

; ; ,

также принадлежит классу КС-языков.

Теорема: Класс контекстно-свободных языков (КС-языков) замкнут относительно операции подстановки.

Пример :

;

;

.

Решение:

.

Домашнее задание: Построить язык , используя операцию подстановки.

;

;

.

Следствие: Класс контекстно-свободных языков (КС-языков) замкнут относительно следующих операций:

1. Объединение;

2. Конкатенация;

3. Итерация;

4. Положительная итерация;

5. Гомоморфизм;

6. Маркированного объединения;

;

7. Маркированной конкатенации;

8. Маркированной итерации.

.

1.1.1. Теорема Огдена. Лемма о разрастании кс-языков

Лемма позволяет определить является ли язык контекстно-свободным. Она дает необходимое условие, но не достаточное условие того, что язык является контекстно-свободным, то есть при наличии удовлетворяющих лемме условий язык не обязательно является контекстно-свободным.

Лемма: Пусть язык является КС-языком, тогда существует такое число  - целое и положительное, для которого можно выделить цепочку , причем длина, которой не меньше, чем и которую можно представить в следующем виде

,

где

;

.

Тогда вновь получаемая цепочка , будет иметь вид

, ,

также будет принадлежать исходному языку .

Пример : Проверить необходимое условие для языка

.

Решение:

, ;

;

;

;

;

;

;

: ;

: ;

: ;

;

: ;

Данный язык удовлетворяет условиям теоремы Огдена.

Пример : Проверить необходимое условие для языка

;

Решение:

Пусть . Тогда . Так как , то в цепочке не могут быть вхождения каждого из символов , и . Таким образом цепочка , которая по лемме о разрастании КС-языков принадлежит , содержит либо символов , либо символов . Но она не может иметь вхождений каждого из символов , и , потому что . Значит вхождений какого-то из символов в больше, чем другого, и, следовательно, . Полученное противоречие позволяет заключить, что - не КС-язык.

Пример : Проверить необходимое условие для языка

;

.

Решение:

;

;

;

;

;

Данный язык удовлетворяет условиям теоремы Огдена, но не является контекстно-свободным.

Домашнее задание: Написать грамматику типа 2 и грамматику типа 1 для языка .

Домашнее задание: Проверить равенства

1.

.

2.

.

1.2. Приведение кс-грамматик

Алгоритм приведения состоит из шести шагов: