Zadania_na_laboratornye_raboty


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
ЗАДАНИЯ НА ЛАБОРАТОРНЫЕ РАБОТЫ

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


ЗАДАНИЕ 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», заканчивающаяся на «01
0».


ЗАДАНИЕ 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



Приложенные файлы

  • pdf 17919613
    Размер файла: 102 kB Загрузок: 1

Добавить комментарий