Zadania_na_laboratornye_raboty

ЗАДАНИЯ НА ЛАБОРАТОРНЫЕ РАБОТЫ ПО КУРСУ «ТЕОРИЯ АВТОМАТОВ И ФОРМАЛЬНЫХ ЯЗЫКОВ»

ЗАДАНИЕ 1 Тема: «Конечные автоматы и автоматные языки»

1.1.Описать заданный язык регулярными выражениями

1.2.Построить конечный автомат по полученным регулярным выражениям

1.3.Разработать программную реализацию построенного автомата

1.4.Разработать программную реализацию автомата по регулярным выражениям с помо-

щью flex

1.5.Описать заданный язык автоматной грамматикой

Описания языков

1) Цепочка символов «а» произвольной длины, после которой следует символ «b»; цепочка символов «а» произвольной длины, после которой следует символ «с»; цепочка символов «b» произвольной длины, после которой следуют «а» или «с».

2) Цепочка пар символов «а» «b» произвольной длины, после которой следует «b»; цепочка пар символов «b» «а» произвольной длины, после которой следует «с»; символ «с».

3) Произвольная цепочка символов из «а»,«b»,«с», заканчивающаяся на «аbс»; произвольная цепочка символов из «а»,«b»,«с», заканчивающаяся на «сbа».

4)Три подряд пришедших символа «а» в произвольной цепочке из «а» и «b», после которых следует «b»;

три подряд пришедших символа «b» в произвольной цепочке из «а» и «b», после которых следует «а»;

три подряд пришедших символа «b» в произвольной цепочке из «а» и «b», после которых следует «с».

5)Произвольное число символов «а» между двумя символами «b»;

произвольное число символов «b» между двумя символами «с»; три подряд пришедших символа «с».

6)Произвольная цепочка из «0» и «1», заканчивающаяся тремя символами «1»; произвольная цепочка символов «0» и «1», заканчивающаяся тремя символами «0».

7)Произвольная цепочка чередующихся символов «0» и «1», после которой следует «.»; цепочка длины, кратной 3, из символов «0» между двумя символами «.»; два символа «.».

8)Цепочка четной длины из «0» между двумя «1»;

цепочка нечетной длины из «1» между двумя «0»; две «1» подряд.

9) «1» между двумя цепочками из «0»,четной длины каждая; «0» между двумя цепочками из «1»,четной длины каждая.

10) Произвольная цепочка из «0» и «1», заканчивающаяся на «101»; произвольная цепочка из «0» и «1», заканчивающаяся на «010».

ЗАДАНИЕ 2 Тема: «Нисходящий разбор с использованием автоматов с магазинной памятью»

2.1.Проверить, обладает ли заданная грамматика свойством LL(1), и при необходимости, выполнить ее преобразование к этому виду.

2.2.Построить для полученной в п.1 грамматики LL(1)-таблицу разбора.

2.3.Разработать программную реализацию синтаксического анализатора на основе полученной LL(1)-грамматики и соответствующей таблицы разбора. Результат анализа представить в виде последовательности номеров правил грамматики, примененных в процессе разбора.

	Описания грамматик
1)	2)	3)
G::=E	O::=p|E	P::=bDfLe
E::=AT	E::=YB	D::=dcD|d
A::=E+|B	Y::=YStBe|	L::=scL|s
T::=MP	S::=iv
M::=T*|B	B::=p	P - аксиома
P::=x|y|(E)
B::=	O - аксиома
G - аксиома
4)	5)	6)
D::=(L)M	S::=caA	S::=aA|bB
L::=a,L|D,L|a|D	A::=(L)|	A::=0A1|01
M::=i|j	L::=e,L|e	B::=0B11|011
D - аксиома	S - аксиома	S - аксиома
7)	8)	9)
S::=t(L)	S::=aAd|aBc	S::=A|D
L::=E|E;L	A::=bA|b	A::=ab|ac|Ab
F::=a|a,F	B::=Bf|f	D::=cD|b
E::=iF
S - аксиома	S - аксиома	S - аксиома
10)
A::=B|D

B::=BCC|a

C::=ba

D::=CaD|b

A - аксиома

ЗАДАНИЕ 3 Тема: «Восходящий разбор с использованием автоматов с магазинной памятью»

3.1.Для заданной грамматики построить LR(1)-таблицу разбора

3.2.Разработать программную реализацию синтаксического анализатора на основе полученной таблицы разбора. Результат анализа представить в виде последовательности номеров правил грамматики, примененных в процессе разбора.

3.3.Разработать программную реализацию LR(1)-разбора с помощью bison

ЗАДАНИЕ 4 Тема: «Синтаксически управляемый анализ текстовых документов»

Выполнить лабораторную работу «Средства автоматизации построения синтаксических анализаторов».

ГРАФИК ВЫПОЛНЕНИЯ ЗАДАНИЙ

№ п/п	Номер задания	Номер недели отчет-	Рейтинг
		ности
1	1.1, 1.2, 1.3	3	5
2	1.4, 1.5	6	5
3	2.1, 2.2	8	5
4	2.3	10	10
5	3.1, 3.2	13	10
6	3.3	15	5
7	4	17	5