- •1. Грамматики
- •Пример.
- •2. Лексический анализ
- •3. Синтаксический анализ
- •4. Генератор кода
- •Алгоритм.
- •5. Оптимизация кода
- •6. Регулярные множества, их распознавание
- •7. Компиляторы и интерпретаторы.
- •8. Эквивалентность мп-автоматов и кс-грамматик
- •9. Разбор снизу вверх
- •10. Lr(1) - таблица разбора
- •10. Lr(1) - таблица разбора
- •11. Построение lr – таблицы разбора
- •12. Сравнение ll – и lr – методов разбора
- •13. Нормальная форма Хомского
- •14. Нормальная формула Грейбах
- •15. Ll(1)-грамматики
- •16. Ll(1)-таблица разбора
- •17. Контекстно-свободные языки
- •18. Циклы
6. Регулярные множества, их распознавание
и порождение
Рассмотрим методы задания языков программирования и класс множеств, образующий этот класс языков. Основным аппаратом задания будут регулярные множества и регулярные выражения на них.
Определение.
Пусть - конечный алфавит. Регулярное множество в алфавите определяется рекурсивно следующим образом:
– (пустое множество) – регулярное множество в алфавите ;
{e} – регулярное множество в алфавите ;
{a} – регулярное множество в алфавите для каждого а;
если Р и Q – регулярное множество в алфавите , то таковы же и множества:
а) PQ;
б) PQ;
в) P*;
ничто другое не является регулярным множеством в алфавите .
Таким образом, множество в алфавите регулярно тогда и только тогда, когда оно либо , либо {e}, либо {а} для некоторого а, либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации.
Определение.
Регулярные выражения в алфавите и регулярные множества, которые они обозначают, определяются рекурсивно следующим образом:
– регулярное выражение, обозначающее регулярное множество ;
е – регулярное выражение, обозначающее регулярное множество {e};
если а, то а – регулярное выражение, обозначающее регулярное множество {a};
если р и q – регулярные выражения, обозначающие регулярные множества Р и Q, то
а) (p+q) – регулярное выражение, обозначающее РQ;
б) pq – регулярное выражение, обозначающее PQ;
в) (р)* - регулярное выражение, обозначающее Р*;
ничто другое не является регулярным выражением.
Принято обозначать р+ для сокращенного обозначение рр*. Расстановка приоритетов:
* (итерация)- наивысший приоритет;
конкатенация;
+.
Таким образом, 0 + 10* = (0 + (1 (0*)))
Пример.
01 означает {01}
0* {0*}
(0+1)* {0, 1}*
(0+1)* 011 – означает множество всех цепочек, составленных из 0 и 1 и оканчивающихся цепочкой 011.
(а+b) (а+b+0+1)* означает множество всех цепочек {0,1,a,b}*, начинающихся с а или b.
(00+11)* ((01+10)(00+11)* (01+10)(00+11)*) обозначает множество всех цепочек нулей и единиц, содержащих четное число 0 и чётное число 1. Таким образом для каждого регулярного множества можно найти регулярное выражение, его обозначающее, и наоборот.
Введем леммы, обозначающие основные алгебраические свойства регулярных выражений.
Пусть и регулярные выражения, тогда:
+
* = е
е = е =
*=+*
(*)*=*
.
При работе с языками часто удобно пользоваться уравнениями, коэффициентами и неизвестными которых служат множества. Такие уравнения будем называть уравнениями с регулярными коэффициентами
,
где а и b– регулярные выражения. Можно проверить прямой подстановкой, что решением этого уравнения будет а*b.
,
т.е. получаем одно и то же множество. Таким же образом можно установить и систему уравнений.
Определение. Систему уравнений с регулярными коэффициентами назовём стандартной системой с множеством неизвестных , если она имеет вид:
где – регулярные выражения в алфавите, не пересекающемся с . Коэффициентами уравнения являются выражения.
Если =, то в уравнении нет числа, содержащего. Аналогично, если=е, то в уравнении для член, содержащий- это просто. Иными словами, играет роль коэффициента 0, ае – роль коэффициента 1 в обычных линейных уравнениях.
Алгоритм решения стандартной системы уравнений с регулярными выражениями.
Вход. Стандартная система Q уравнений с регулярными коэффициентами в алфавите и множеством неизвестных .
Выход. Решение системы Q .
Метод: Аналог метода решения системы линейных уравнений методом исключения Гаусса.
Шаг 1. Положить i = 1.
Шаг 2. Если i = n, перейти к шагу 4. В противном случае с помощью тождеств леммы записать уравнения для в виде, где - регулярное выражение в алфавите , а - регулярное выражение вида:, причём все– регулярные выражения в алфавите . Затем в правых частях для уравненийзаменимрегулярным выражением.
Шаг 3. Увеличить i на 1 и вернуться к шагу 2.
Шаг 4. Записать уравнение для в виде, где и - регулярные выражения в алфавите . Перейти к шагу 5 (при этомi=n).
Шаг 5. Уравнение для имеет вид, где и - регулярные выражения в алфавите . Записать на выходев уравнениях дляподставляя вместо .
Шаг 6. Если i=1, остановиться, в противном случае уменьшить i на 1 и вернуться к шагу 5.
Однако следует отметить, что не все уравнения с регулярными коэффициентами обладают единственным решением. Например, если
- уравнение с регулярными коэффициентами и означает множество, содержащее пустую цепочку, то будет решением этого уравнения для любого . Таким образом, уравнение имеет бесконечно много решений. В такого рода ситуациях мы будем брать наименьшее решение, которое назовемнаименьшей неподвижной точкой. В нашем случае наименьшая неподвижная точка .
Лемма.
Каждая стандартная система уравнений Q с неизвестными обладает единственной наименьшей неподвижной точкой.
Определение.
Пусть Q – стандартная система уравнений с множеством неизвестных в алфавите . Отображениеf множества во множество языков в алфавите называется решением системы Q, если после подстановки в каждое уравнение f(x) вместо Х для каждого Х уравнения становятся равенствами множеств.
Отображение f:P(*) называется наименьшей неподвижной точкой системы Q, если f решение, и для любого другого решения g f(x)g(x) для всех Х..
Лемма. Пусть Q – стандартная система уравнений с неизвестными , и уравнение для имеет вид
.
Тогда наименьшей неподвижной точкой системы Q будет такое отображение
для некоторой последовательности чисел , гдеm, km, j1=i.
Примем в качестве аксиомы утверждение, что язык определяется праволинейной грамматикой тогда и только тогда, когда он является регулярным множеством. Таким образом, констатируем:
класс регулярных множеств – наименьший класс языков, содержащих множества , {e} и {a} для всех символов а и замкнутый относительно операций объединения, конкатенации и итерации;
регулярные множества – множества, определённые регулярными выражениями;
регулярные множества – языки, порождаемые праволинейными грамматиками.