Алёшин А.В. Теория языков программирования и методы трансляции. Практикум
Подождите немного. Документ загружается.
Рисунок 2.3 Учет количественных ограничений
U=TRUE
Да
Нет
...
БУКВА
COUNT := 0
COUNT :=
COUNT +1
COUNT
>5
Нет
Да
Сообщен
ие об
ошибке
БУКВА
1
2
3
5
6
7
4
11
11
11
8,10
11
8
ЦИФРА
11
Рисунок 2.3 Окончание
Задача синтаксического анализа упрощается, если программа
предварительно обработана лексическим анализатором и поступает на
вход синтаксического анализатора в форме последовательности кодов
лексем. Тогда любой модуль блок-схемы, соответствующий элементу
диаграммы, в начале по коду таблицы определяет допустимость данного
вида лексем в структуре предложения и если допустим, тогда по
спецификатору проверяется допустимость лексемы.
2.3 Задание на практическую работу
Составить определение заданного понятия в БНФ. Варианты
исходных данных приведены в Таблице 2.1.
U=TRUE
Нет
Да
ЦИФРА
КОНЕЦ
U=TRUE
8
Нет
Да
10
4
10
5
10
7
9
10
11
12
Таблица 2.1 Варианты исходных данных
№ варианта Исходные данные
1 Подмножество языка Pascal. Допускается:
– в описаниях – переменные целого типа;
– в операторной части – оператор присваивания
и оператор IF ... THEN.
2 Подмножество языка Pascal. Допускается:
– в описаниях – переменные целого типа;
– в операторной части – оператор присваивания и
оператор FOR.
3 Подмножество языка Pascal. Допускается:
– в описаниях – переменные целого типа;
– в операторной части – оператор присваивания и
оператор WHILE.
4 Подмножество языка Pascal. Допускается:
– в описаниях – переменные целого типа;
– в операторной части – оператор присваивания,
в правой части которого несколько соотношений
соединяются знаками логических операций.
5 Подмножество языка Pascal. Допускается:
– в описаниях – переменные целого типа;
– в операторной части – оператор присваивания и
оператор REPEAT.
6 Подмножество языка Pascal. Допускается:
– в описаниях – переменные целого типа;
– в операторной части – оператор присваивания и
оператор CASE.
7 Подмножество языка Pascal. Допускается:
– в описаниях – переменные целого типа;
– в операторной части – оператор присваивания с
арифметическим выражением над целыми переменными.
8 Подмножество языка Pascal. Допускается:
- в описаниях - переменные и массивы вещественного
типа;
- в операторной части - оператор присваивания с
выражением над вещественными переменными;
13
2.4 Контрольные вопросы
1. Перечислите достоинства и недостатки синтаксических
диаграмм.
2. В чем преимущества алгоритмического задания синтаксиса
языков по сравнению с БНФ?
14
ПРАКТИЧЕСКАЯ РАБОТА 3 ПРОЕКТИРОВАНИЕ
СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА
3.1 Цель и порядок выполнения работы
Цель занятия: Получение практических навыков по
проектированию синтаксических блоков компиляторов.
Порядок выполнения практической работы:
– прочитать описание работы;
– получить задание у преподавателя;
– в соответствии с вариантом исходных данных разработать
формальную грамматику реализуемого подмножества языка Паскаль;
– составить, ввести и отладить программу, реализующую
алгоритм синтаксического анализатора;
– составить тестовые наборы данных (позитивные и негативные);
– получить листинги исходного модуля программы, входных
данных и результатов работы;
– оформить отчет по практической работе.
3.2 Теоретические сведения
Теоретические основы разработки формальных грамматик,
построения и программной реализации автоматов с магазинной памятью
рассмотрены в главах 3, 4, 5, 8 и 9 конспекта лекций по данной
дисциплине.
3.3 Задание на практическую работу
Вариант индивидуального задания складывается из заданий по
практической работе №№ 1 и 2, а также приведенных ниже требований.
Общие требования к синтаксическому блоку:
1. Операции: "+", "-", "/", "*" ("<",">","=","<=",">=","and", "or" –
дополнительно по желанию).
2. Операторы: присваивания (обязательно для всех вариантов),
условия и цикла (по варианту).
15
3. Для ввода данных и вывода результатов обязательно
реализовать соответствующие функции (операторы), например, "read" и
"write".
4. Процедуры, функции и модули могут быть разработаны по
желанию и оцениваются как дополнительные возможности.
Синтаксический блок компилятора необходимо объединить с
лексическим блоком.
На входе – программа на выбранном языке, разработанная в
соответствии с правилами грамматики.
На выходе – сообщение о том, что текст программы
соответствует грамматике (программа без ошибок), либо сообщение об
ошибке. Дополнительно можно представить дерево синтаксического
разбора (например, в виде логического файла, показывающего
промежуточные действия компилятора или дерево синтаксического
разбора).
В случае разработки типизированного языка необходимо
продемонстрировать семантическую работу компилятора.
3.4 Порядок защиты практической работы
Практическая работа сдается в два этапа:
Первый этап – преподавателю предоставляется формальная
грамматика, записанная в РБНФ. Дополнительно можно представить
графическое представление в форме диаграмм Вирта.
Грамматика имеет два вида: пользовательский и преобразованная
для реализации грамматика. В последней грамматике для каждого
правила должно быть определено множество «ВЫБОР» (Множество
входных символов, для которых может быть применимо правило).
Второй этап – программная реализация автомата с магазинной
памятью, функционирующего по разработанной формальной грамматике.
Для сдачи практической работы студент должен подготовить
набор позитивных и негативных тестов.
3.5 Содержание отчета по практической работе
1. Постановка задачи:
16
– формулировка задачи (ограничения реализуемого
подмножества языка Паскаль);
– формальная грамматика пользователя;
– формальная грамматика разбора (атрибуты и множество
выбора).
2. Описание реализации:
– описание выбора метода решения;
– описание структуры блока синтаксического анализа;
– алгоритмы функционирования компонент (блоков) анализатора.
3. Обработка ошибок.
4. Выводы.
3.6 Дополнительные возможности, оцениваемые при защите
практической работы
1. Наличие семантического разбора (атрибутная грамматика).
2. Наличие построенных диаграмм Вирта.
3. Наличие дополнительных логических функций ("or", "and" и
так далее) и смешанных выражение арифметических и логических
выражений.
4. Наличие процедур и функций.
5. Удобный интерфейс для представления результатов
синтаксического разбора (можно использовать log-файл).
6. Эффективные сообщения об ошибках.
17
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Пратт Т., Зелковиц М. Языки программирования: разработка и
реализация / Под общей ред. А. Матросова. – СПб.: Питер, 2002. – 688 с.:
ил.
2. Серебряников В.А. Теория и реализация языков
программирования. – М.: МЗ-Пресс, 2003.
3. Альфред В. Ахо, Рави Сети, Джеффри Д. Ульман.
Компиляторы: принципы, технологии и инструментарий. – М.: Вильямс,
2001.
4. Системное программирование. Основы построения
трансляторов. Учебное пособие. – М.: КОРОНА-принт, 2001.
5. Кауфман В. Ш. Языки программирования. Концепции и
принципы. - М.: Радио и связь, 1993. - 432 с.
6. Льюис Ф., Розенкранц Д., Стринз Р. Теоретические основы
проектирования компиляторов. - М.: Мир, 1979.
7. Маккиман У. Генератор Компиляторов. - М.: Статистика, 1980.
8. Рейоурд-Смит В.Дж. Теория формальных языков. Вводный
курс. - М.: Радио и связь, 1988.
9. Фостер Дж. Автоматический синтаксический анализ. - М.: Мир,
1975.
10. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978.
11. Шишмарев А.И., Заморин А.П. Англо-русско-немецко-
французский толковый словарь по вычислительной технике. М.:
Издательство «Русский язык», 1978.
12. Браун П. Макропроцессоры и мобильность программного
обеспечения. - М.: Мир, 1977.
13. Легалов А.И. Процедурно-параметрическая парадигма
программирования. Возможна ли альтернатива объектно-
ориентированному стилю? - Красноярск: 2000. Деп. рук. № 622-В00 Деп.
в ВИНИТИ 13.03.2000. - 43 с.
14. Ахо А., Ульман Дж. Теория синтаксического анализа,
перевода и компиляции. - М.: Мир, 1978.
15. Грис Д. Наука программирования. М.: Мир, 1984.
16. Льюис Ф., Розенкранц Д., Стринз Р. Теоретические основы
проектирования компиляторов. - М.: Мир, 1979.
17. Легалов А.И. Основы разработки трансляторов. Конспект
лекций.
18. Вайнгартен Ф. Трансляция языков программирования. - М.:
Мир, 1977.
18
СОДЕРЖАНИЕ
ПРАКТИЧЕСКАЯ РАБОТА 1 ЛЕКСИЧЕСКИЙ АНАЛИЗ..........................3
1.1 ЦЕЛЬ И ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ................................................3
1.2 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ.....................................................................3
1.3 ЗАДАНИЕ НА ПРАКТИЧЕСКУЮ РАБОТУ....................................................5
1.4 КОНТРОЛЬНЫЕ ВОПРОСЫ.........................................................................6
ПРАКТИЧЕСКАЯ РАБОТА 2 СИНТАКСИЧЕСКИЙ АНАЛИЗ................7
2.1 ЦЕЛЬ И ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ................................................7
2.2 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ.....................................................................7
2.3 ЗАДАНИЕ НА ПРАКТИЧЕСКУЮ РАБОТУ..................................................11
2.4 КОНТРОЛЬНЫЕ ВОПРОСЫ.......................................................................13
ПРАКТИЧЕСКАЯ РАБОТА 3 ПРОЕКТИРОВАНИЕ
СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА....................................................14
3.1 ЦЕЛЬ И ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ..............................................14
3.2 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ...................................................................14
3.3 ЗАДАНИЕ НА ПРАКТИЧЕСКУЮ РАБОТУ..................................................14
3.4 ПОРЯДОК ЗАЩИТЫ ПРАКТИЧЕСКОЙ РАБОТЫ.........................................15
3.5 СОДЕРЖАНИЕ ОТЧЕТА ПО ПРАКТИЧЕСКОЙ РАБОТЕ...............................15
3.6 ДОПОЛНИТЕЛЬНЫЕ ВОЗМОЖНОСТИ, ОЦЕНИВАЕМЫЕ ПРИ ЗАЩИТЕ
ПРАКТИЧЕСКОГО ЗАНЯТИЯ...........................................................................16
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ......................................17
19
ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
И МЕТОДЫ ТРАНСЛЯЦИИ
Методические указания и варианты заданий для выполнения
практических занятий для студентов очной формы обучения
специальности 220400 – Программное обеспечение ВТ и АС
Алёшин Александр Владимирович
20