ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 08.04.2021
Просмотров: 506
Скачиваний: 2
Государственное
образовательное
учреждение
высшего
профессионального
образования
Сургутский
государственный
университет
Ханты
-
Мансийского
автономного
округа
–
Югры
Факультет
автоматики
и
телекоммуникаций
Кафедра
автоматики
и
компьютерных
систем
Гришмановский
Павел
Валерьевич
,
кандидат
технических
наук
,
доцент
Теория
языков
программирования
и
методы
трансляции
Учебно
-
методическое
пособие
Сургут
, 2010
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
2
Содержание
Введение
.........................................................................................................................................3
Тематический
план
дисциплины
..................................................................................................5
Лабораторная
работа
№
1
Создание
простейшего
распознавателя
..........................................6
Лабораторная
работа
№
2
Распознаватель
числовых
констант
..............................................10
Лабораторная
работа
№
3
Алгоритм
рекурсивного
спуска
.....................................................13
Лабораторная
работа
№
4
Генерация
промежуточного
кода
..................................................18
Лабораторная
работа
№
5
Оптимизация
промежуточного
кода
.............................................21
Список
рекомендуемой
литературы
..........................................................................................24
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
3
Введение
Целью
изучения
дисциплины
«
Теория
языков
программирования
и
методы
трансляции
»
является
формирование
у
студентов
систематизированных
знаний
в
области
построения
трансляторов
языков
высокого
уровня
и
организации
вычислительного
процесса
средствами
вычислительной
техники
.
Задачи
преподавания
дисциплины
:
–
студент
должен
знать
основные
этапы
процесса
трансляции
,
способы
задания
и
описания
искусственных
языков
;
–
студент
должен
иметь
представление
об
основных
методах
и
подходах
решения
задач
,
связанных
с
конкретными
шагами
принципиальной
схемы
трансляции
,
об
основных
классах
языков
и
о
допустимых
преобразованиях
,
совершаемых
над
грамматиками
языков
;
–
студент
должен
приобрести
навыки
по
изучению
конструкций
искусственного
языка
и
применению
оптимальных
методов
для
решения
поставленной
задачи
.
Освоение
дисциплины
заключается
в
изучении
теоретического
материала
в
соответствии
с
планом
,
представленным
в
настоящем
учебно
-
методическом
пособии
.
При
этом
может
использоваться
литература
,
указанная
в
списке
рекомендуемых
источников
.
Практическое
освоение
ряда
разделов
дисциплины
осуществляется
в
результате
выполнения
комплекса
лабораторных
работ
(
лабораторного
практикума
).
Лабораторный
практикум
по
дисциплине
«
Теория
языков
программирования
и
методы
трансляции
»
направлен
на
изучение
и
практическое
освоение
основных
алгоритмов
грамматического
разбора
,
методов
их
программной
реализации
и
построения
элементов
трансляторов
программ
.
Для
выполнения
каждой
лабораторной
работы
необходимо
изучение
соответствующего
раздела
теоретической
части
курса
.
Программную
реализацию
распознавателей
и
трансляторов
,
их
отладку
и
тестирование
необходимо
выполнять
с
учетом
всех
методических
рекомендаций
,
приведенных
в
описании
каждой
лабораторной
работы
.
Для
программной
реализации
может
быть
использована
любая
распространенная
среда
программирования
.
Для
обеспечения
возможности
проверки
результатов
работы
преподавателем
,
рекомендуется
выполнять
реализацию
на
языках
C/C++
с
использованием
только
стандартных
библиотек
и
текстового
интерфейса
(
тип
приложения
–
консольное
),
что
обеспечит
хорошую
переносимость
на
уровне
исходного
кода
.
Так
как
программы
,
создаваемые
в
ходе
выполнения
лабораторных
работ
,
выполняют
преимущественно
преобразование
входного
текста
в
выходной
,
рекомендуется
имена
входного
и
выходного
файлов
передавать
в
качестве
параметров
командной
строки
.
По
каждой
лабораторной
работе
оформляется
отчет
,
который
должен
содержать
следующие
элементы
:
1.
Титульный
лист
.
2.
Цель
работы
.
3.
Задание
на
лабораторную
работу
.
4.
Основная
часть
:
–
формализованное
описание
решения
задачи
;
–
другая
информация
(
в
соответствии
с
методическими
рекомендациями
по
каждой
лабораторной
работе
);
–
описание
принципов
программной
реализации
(
желательна
иллюстрация
блок
-
схемами
алгоритмов
,
схемами
и
диаграммами
,
фрагментами
листинга
и
т
.
п
.).
5.
Выводы
(
в
соответствии
с
методическими
рекомендациями
по
каждой
лабораторной
работе
).
К
отчету
для
проверки
преподавателем
прикладывается
архив
в
формате
RAR, ZIP
или
7z,
содержащий
:
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
4
–
исходный
код
(
или
файлы
проектов
)
разработанного
приложения
(
распознавателя
или
транслятора
)
с
подробными
комментариями
;
–
входные
файлы
,
использовавшиеся
для
тестирования
,
и
соответствующие
им
выходные
файлы
;
–
файл
readme.txt
с
указанием
среды
разработки
и
,
при
необходимости
,
существенных
особенностей
настройки
среды
разработки
,
размещения
файлов
,
компиляции
и
сборки
проектов
,
использования
параметров
командной
строки
приложения
и
т
.
п
.
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
5
Тематический
план
дисциплины
Тема
1.
Введение
.
Понятие
языков
и
трансляторов
.
Группы
языков
и
парадигмы
программирования
.
Свойства
искусственных
языков
.
Аспекты
стандартизации
языков
программирования
.
Понятие
транслятора
.
Виды
трансляторов
.
Структура
транслятора
и
этапы
трансляции
.
Методы
трансляции
.
Интерпретация
и
компиляция
.
Тема
2.
Формальные
языки
и
грамматики
.
Формальный
язык
.
Способы
задания
языка
.
Понятие
формальной
грамматики
.
Способы
задания
грамматик
.
Бэкусова
нормальная
форма
(
Нормальная
форма
Бэкуса
–
Наура
).
Грамматики
Хомского
.
Иерархия
грамматик
Хомского
и
абстрактные
машины
.
Вывод
и
грамматический
разбор
.
Стратегии
синтаксического
анализа
.
СУ
-
схемы
.
Транслирующие
грамматики
.
Атрибутные
транслирующие
грамматики
.
Тема
3.
Трансляция
на
основе
польской
инверсной
записи
.
Определение
польской
инверсной
записи
.
Алгоритм
трансляции
выражений
.
Алгоритм
Дейкстры
формирования
польской
инверсной
записи
.
Трансляция
выражений
,
содержащих
переменные
с
индексом
.
Трансляция
операторов
на
основе
польской
инверсной
записи
.
Оператор
присваивания
.
Динамические
деревья
.
Трансляция
условных
операторов
.
Тема
4.
Регулярные
грамматики
,
языки
и
их
свойства
.
Преобразование
контекстно
-
свободных
и
регулярных
грамматик
в
автоматные
.
Диаграмма
состояния
автоматной
грамматики
.
Конечный
автомат
-
распознаватель
автоматных
языков
.
Построение
конечного
автомата
по
автоматной
грамматике
.
Лексический
анализ
.
Сканер
.
Блок
лексического
анализа
.
Тема
5.
Контекстно
-
свободные
грамматики
.
Типы
контекстно
-
свободных
грамматик
.
Редуцированные
и
приведенные
грамматики
.
Допустимые
преобразования
.
Устранение
левой
рекурсии
,
факторизация
,
удаление
несущественных
символов
.
Условия
порождения
бесконечных
языков
.
Распознаватель
для
контекстно
-
свободных
языков
.
Нормальные
формы
Хомского
и
Грейбах
.
Тема
6.
Нисходящие
стратегии
синтаксического
анализа
.
Нисходящий
распознаватель
.
Неформальное
описание
нисходящего
анализа
.
Алгоритм
нисходящего
анализа
.
Тема
7.
Методы
детерминированного
синтаксического
анализа
на
основе
восходящей
стратегии
.
Восходящий
распознаватель
.
Неформальное
описание
восходящего
анализа
.
Алгоритм
восходящего
анализа
.
Отношения
предшествования
.
Грамматики
предшествования
.
Распознаватель
для
грамматик
предшествования
.
Построение
отношений
предшествования
.
Матрица
предшествования
.
Построение
функций
предшествования
с
помощью
алгоритма
Флойда
.
Построение
функций
предшествования
с
помощью
графа
линеаризации
.
Метод
простого
предшествования
.
Тема
8. LR(k)-
и
LL(k)-
грамматики
.
Особенности
LR(k)-
и
LL(k)-
грамматик
и
распознавателей
.
Правила
подстановок
Флойда
-
Эванса
.
Методы
детерминированного
синтаксического
анализа
на
основе
нисходящей
стратегии
. K-
предсказывающий
алгоритм
разбора
.
Тема
9.
Контекстный
анализ
.
Атрибутная
индукция
.
Генерация
.
Основные
задачи
процесса
генерации
.
Оптимизация
.