Печатается по решению редакционно-издательского совета ОрелГТУ

А.П. Гордиенко, Н.И. Салина

ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ

Методические указания по выполнению лабораторных и

Практических работ

Дисциплина - «Теория языков программирования и методы

трансляции»

Специальностей:

Программное обеспечение вычислительной техники и

автоматизированных систем»

- 080801 «Прикладная информатика (в экономике)»

- 080800.62 «Прикладная информатика (бакалавры)»

- 230201 «Информационные системы и технологии»

- 230100.62 «Информатика и вычислительная техника»

Печатается по решению редакционно-издательского совета ОрелГТУ

ОРЕЛ 2007

Авторы: доцент кафедры «Информационные системы»

А.П. Гордиенко и ст. преподаватель Н.И. Салина

Рецензент: канд.техн.наук, доцент

кафедры «Информационные системы» А.В. Чижов

Настоящие методические указания предназначены для выполнения лабораторных и практических работ по дисциплине «Теория языков программирования и методы трансляции» студентов очной формы обучения для специальностей: 230105 «Программное обеспечение вычислительной техники и автоматизированных систем», 230100.62 «Информатика и вычислительная техника», 080801 «Прикладная информатика (в экономике)», 080800.62 «Прикладная информатика (бакалавры)», 230201 «Информационные системы и технологии».

Редактор

Технический редактор

Орловский государственный технический университет

Лицензия ИД 00670 от 5.01.2000

АНО «ОрелГТУ-РЦФИО»

Подписано к печати Формат 60 84 1\16

Печать офсетная Усл. печ. л.. Тираж экз.

Заказ №

Отпечатано с готового оригинал-макета

на полиграфической базе ОрелГТУ,

302030, г. Орел, ул. Московская, 65

© ОрелГТУ, 2007

© АНО «ОрелГТУ-РЦФИО»

© Гордиенко А.П.,

Салина Н.И. 2002-2007

СОДЕРЖАНИЕ

1 ЦЕЛЬ ПРАКТИКУМА.. 6

2 ПОДГОТОВКА К ВЫПОЛНЕНИЮ РАБОТЫ... 6

3 Лабораторная работа №1 “Использование конечного автомата для построения лексического анализатора”. 9

3.1 Цель работы... 9

3.2 Построение лексического анализатора. 9

3.2.1 Описание распознаваемого языка в форме регулярного.. 10

3.2.2 Преобразование регулярного выражения в недетерминированный конечный автомат 11

3.2.3 Преобразование недетерминированного конечного автомата к детерминированному 15

3.2.4 Минимизация конечного автомата.. 19

3.2.5 Конечный автомат для распознавания нескольких лексем... 20

3.2.6 Распознавание ключевых слов.. 22

3.3 Реализация лексического анализатора в виде конечного автомата.. 23

3.4 Контрольные вопросы... 27

3.5 Задание.. 27

3.6 Содержание отчета.. 28

3.7 Защита лабораторной работы... 29

4. Лабораторная работа №2 “Построение лексического анализатора с использованием генератора лексических анализаторов Lex”. 29

4.1 Цель работы... 29

4.2 Общие сведения о генераторе лексических анализаторов Lex.. 29

4.3 Lex-программа.. 30

4.3.1 Регулярные выражения.. 30

4.3.2 Разделы Lex-программы... 31

4.3.3 Функции и переменные, используемые при работе с.. 32

4.4 Работа анализатора, построенного с помощью генератора Lex.. 33

4.5 Пример построения лексического анализатора с использованием Lex. 34

4.6 Контрольные вопросы... 37

4.7 Задание.. 37

4.8 Защита лабораторной работы... 38

5 Лабораторная работа № 3. “Использование метода рекурсивного спуска для построения синтаксического анализатора”. 38

5.1 Цель работы... 38

5.2 Общие сведения.. 39

5.3 Рекурсивный спуск.. 42

5.4 Пример реализации метода рекурсивного спуска.. 44

5.5 Контрольные вопросы... 50

5.6 Задание.. 50

5.7 Содержание отчета.. 51

6 Лабораторная работа № 4 “Таблично управляемый синтаксический разбор сверху вниз” 52

6.1 Цель работы... 52

6.2 Структура анализатора.. 52

6.3 Построение множества first.. 53

6.4 Построение множества follow... 55

6.5 Построение таблицы разбора.. 58

6.6 Алгоритм разбора.. 60

6.7 Контрольные вопросы... 65

6.8 Задание.. 65

6.9 Содержание отчета.. 66

6.10 Защита лабораторной работы... 66

7 Лабораторная работа № 5 “Синтаксический разбор снизу вверх”. 67

7.1 Цель работы... 67

7.2 Разбор снизу вверх.. 67

7.3 Структура LR(k)-анализаторов.. 68

7.4 Построение таблиц анализа.. 70

7.4.1 Понятие ситуации.. 70

7.4.2 Каноническая совокупность множеств ситуаций.. 70

7.4.3 Заполнение таблиц action и goto.. 73

7.5 Алгоритм LR-разбора.. 77

7.6 Контрольные вопросы... 81

7.7 Задание.. 82

7.8 Содержание отчета.. 82

7.9 Защита лабораторной работы... 82

8 Лабораторная работа № 6 “Генерация кода и реализация машины”. 82

8.1 Цель работы... 82

8.2 Построение транслятора на основе синтаксического анализа методом рекурсивного спуска.. 83

8.2.1 Входной язык.. 83

8.2.2 Структура машины... 85

8.2.3 Генерация кода из синтаксического анализатора.. 90

8.2.4 Работа машины... 94

8.3 Контрольные вопросы... 95

8.4 Задание.. 95

8.5 Защита лабораторной работы... 96

9 Лабораторная работа № 7 “Автоматизированное построение трансляторов с использованием генератора YACC”. 96

9.1 Цель работы... 96

9.2 Общие сведения.. 96

9.3 Структура Yacc-программы... 98

9.4 Примеры трансляторов, построенных в Yacc.. 100

9.5 Контрольные вопросы... 107

9.6 Задание.. 107

9.7 Защита лабораторной работы... 107

10 Задания к практическим работам... 108

СПИСОК ЛИТЕРАТУРЫ... 109