Клуб студентов «Технарь». Уникальный сайт с дипломами и курсовыми для технарей.
Все разделы / Теория языков программирования и методы трансляции /
Лабы №1-№5, для всех вариантов. Теория языков программирования и методы трансляции.
Тип работы: Работа Лабораторная
Сдано в учебном заведении: ДО СИБГУТИ
Описание:
Лабораторная работа № 1 Генерация цепочек языка
Пусть язык задан контекстно-свободной грамматикой (теоретический материал разделов 1.1–1.4). Написать программу, которая по заданной грамматике будет генерировать ВСЕ цепочки языка в некотором диапазоне длин. Использовать только левосторонний или правосторонний вывод! Диапазон длин генерируемых цепочек должен задаваться пользователем при запуске программы.
Предусмотреть возможность выбора пользователю – использовать заданную в программе грамматику или вводить свою с клавиатуры.
На вход программы подаётся КС-грамматика (терминальный и нетерминальный алфавиты, целевой символ, правила вывода), задаётся диапазон длин цепочек, указывается тип вывода (левосторонний или правосторонний).
Рекомендуется для ввода исходных данных использовать соответствующую форму. При вводе правил грамматики не рекомендуется предоставлять пользователю излишнюю свободу действий, например, удобнее запретить ввод в левой части правил более чем одного нетерминального символа, чем проверять введённые правила на соответствие контекстно-свободному типу.
На выходе должен быть список построенных цепочек. Все цепочки в списке должны быть различны. При получении одинаковых цепочек (разными способами) их следует сохранять в списке выводимых цепочек только в случае выполнения дополнительного задания.
Проверить программу на примерах из лекционного курса и на заданиях из контрольных вопросов к теоретической части.
Дополнительно: Дополнить предыдущую программу таким образом, чтобы для одной или нескольких цепочек (цепочки выбирает пользователь из числа построенных на предыдущем этапе работы) строилось дерево вывода, т.е. была структурно представлена последовательность правил, использованных при построении цепочки.
Лабораторная работа № 2 Моделирование работы ДКА
Пусть регулярный язык задаётся конечным автоматом – ДКА (теоретический материал разделов 1.5, 2.2). Написать программу, которая будет проверять по заданному автомату вводимую цепочку и делать вывод о том, принадлежит ли она рассматриваемому регулярному языку. В случае отрицательного ответа необходимо давать пояснение, по какой причине цепочка не принадлежит языку – например, “в цепочке присутствуют посторонние символы”, “после прочтения цепочки автомат не пришёл в конечное состояние” и т.п. Исходный автомат вводить с клавиатуры в соответствии с определённым форматом. Ввод цепочек также производить с клавиатуры.
На вход программы подаётся ДКА (множество состояний, алфавит языка, начальное состояние, множество заключительных состояний, функция переходов в виде таблицы) и проверяемая цепочка символов (может вводиться многократно, т.е. возможно проверить любое количество цепочек). При этом в проверяемую цепочку могут входить и символы, не принадлежащие алфавиту языка; цепочка может быть и пустой.
Программа должна предоставлять пользователю возможность изменять начальное и конечные состояния с сохранением введённой функции переходов для заданного автомата.
Выход – отображение на экране процесса проверки цепочки в виде последовательной смены конфигураций и вывод результата – сообщения, принадлежит ли цепочка языку.
Проверить работу программы на примерах из лекций и задачах из контрольных вопросов.
Дополнительно:
Предоставить пользователю возможность не только вводить данные с клавиатуры, но и загружать автомат из файла (выбор – в соответствующем пункте меню или нажатием кнопки в исходном окне программы). При этом следует накладывать определённые ограничения на формат файла и производить соответствующие проверки во избежание загрузки некорректных данных.
Также по желанию пользователя результаты помимо вывода на экран сохранять в файле. Выбор – аналогично загрузке данных.
Лабораторная работа № 3 Моделирование работы МПА
Пусть контекстно-свободный язык задаётся детерминированным автоматом с магазинной памятью – ДМПА (теоретический материал раздела 3.1). Написать программу, которая будет проверять для вводимой цепочки, принадлежит ли она заданному КС-языку. В случае отрицательного ответа необходимо давать пояснение, по какой причине цепочка не принадлежит языку (аналогично лаб. раб №2) Исходный автомат вводить с клавиатуры в соответствии с определённым форматом. Ввод цепочек также производить с клавиатуры, выполняя его до тех пор, пока не возникнет желание закончить работу.
На вход программы подаётся ДМПА (множество состояний, алфавит языка, алфавит магазина, начальное состояние, начальное содержимое стека, множество заключительных состояний, функция переходов в виде списка правил) и проверяемая цепочка символов (может вводиться многократно, т.е. возможно проверить любое количество цепочек). При этом в проверяемую цепочку могут входить и символы, не принадлежащие алфавиту языка; цепочка может быть и пустой.
Рекомендуется для ввода исходных данных использовать соответствующую форму с полями выбора. При вводе функции переходов не рекомендуется предоставлять пользователю излишнюю свободу действий.
Выход – отображение на экране процесса проверки цепочки в виде последовательной смены конфигураций и вывод результата – сообщения, принадлежит ли цепочка языку.
Внимание. В ходе проверки цепочки ДМПА может проделывать пустые такты не только после прочтения всей цепочки, но и в её середине. Внимательно прочтите соответствующий раздел лекций 3.1.
Проверить работу программы на примерах из лекций и задачах из контрольных вопросов.
Дополнительно: Предоставить пользователю возможность вносить некоторые изменения в исходные данные без полного их обновления.
Лабораторная работа № 4 Перевод с помощью СУ-схемы
Пусть дана схема синтаксически управляемого перевода (теоретический материал раздела 4.2). Написать программу, которая будет выполнять перевод цепочек с одного языка на другой в соответствии с этой схемой. При невозможности выполнить перевод (цепочка не строится по правилам входной грамматики) необходимо выводить на экран соответствующее сообщение.
Правила СУ-схемы считывать из файла (предоставив пользователю возможность редактировать их на экране); цепочки вводить с клавиатуры, процесс перевода отображать на экране. Предусмотреть возможность выполнения перевода любого количества цепочек для заданной схемы.
На вход программы подаётся схема СУ-перевода (алфавиты входного и выходного языков, множество нетерминальных символов, правила вывода, целевой символ) и цепочка языка, которую необходимо перевести (может вводиться многократно, т.е. возможно перевести любое количество цепочек). Цепочка может быть и не относящейся к исходному языку…
Работа программы может быть организована по-разному. В качестве основного задания допустимо использовать материалы лабораторной работы №1. На первом этапе в соответствии с входной грамматикой схемы СУ-перевода попытаться сгенерировать цепочку, поданную на вход (поскольку её длина известна, можно генерировать только цепочки этой длины). При генерации фиксировать номера использованных правил. В случае успешной генерации выполнить второй этап – применяя номера использованных правил, получать одновременно входную и выходную цепочки по правилу вывода и соответствующему ему элементу перевода.
На выходе – отображение процесса перевода и результирующая цепочка языка.
Дополнительно: Вместо попыток генерации исходной цепочки сделать её разбор каким-либо способом из числа рассмотренных в теоретическом курсе. Например, использовать разбор с возвратами, нисходящий или восходящий (). В таком случае первый этап работы программы изменится на распознавание цепочки, т.е. на нём будет выполняться проверка цепочки построенным распознавателем. На выходе будут получены номера правил, по которым цепочка строилась. Второй этап – перевод с помощью схемы СУ-перевода – полностью совпадает с основным заданием.
Лабораторная работа № 5
Перевод с помощью МП-преобразователя
Пусть дан преобразователь с магазинной памятью; написать программу, которая будет выполнять перевод цепочек с одного языка на другой с помощью заданного преобразователя (теоретический материал раздела 4.2). При невозможности выполнить перевод (цепочка не принадлежит исходному языку) необходимо выводить на экран соответствующее сообщение.
Исходный преобразователь вводить с клавиатуры в соответствии с определённым форматом. Ввод цепочек также производить с клавиатуры, выполняя его до тех пор, пока не возникнет желание закончить работу. Процесс перевода цепочки в виде последовательной смены конфигураций отображать на экране.
На вход программы подаётся ДМП-преобразователь (множество состояний, алфавиты входного и выходного языков, алфавит магазина, начальное состояние, начальное содержимое стека, множество заключительных состояний, функция переходов в виде списка правил) и проверяемая цепочка символов (аналогично лаб. раб. №3).
Рекомендуется за основу взять программу лабораторной работы №3, дополнив исходные данные выходным алфавитом, функцию переходов – в соответствии с определением преобразователя, а конфигурации – выходными цепочками.
Выход: отображение на экране процесса перевода цепочки в виде последовательной смены конфигураций преобразователя, результат перевода – полученная цепочка.
Проверить работу программы на примерах из лекций и задачах из контрольных вопросов.
Дополнительно:
Предоставить пользователю возможность не только вводить данные с клавиатуры, но и загружать преобразователь из файла (аналогично лабораторной работе №2).
Комментарии: Все лабы сданы и зачтены в марте 2017г.
Без нареканий и исправлений.
Теория языков программирования и методы трансляции
1 Государственное бюджетное образовательное учреждение высшего профессионального образования Московской области «Международный университет природы, общества и человека «Дубна» (университет «Дубна») Институт системного анализа и управления Кафедра системного анализа и управления УТВЕРЖДАЮ проректор по учебной работе С.В. Моржухина 20 г. П Р О Г Р А М М А Д И С Ц И П Л И Н Ы Теория языков программирования и методы трансляции (наименование дисциплины) Направление подготовки Информатика и вычислительная техника Профиль подготовки Технологии разработки программного обеспечения Квалификация (степень) выпускника бакалавр Форма обучения Очная Дубна, 2013
2 Автор программы (ученое звание, степень, ФИО полностью): Автор программы: доцент, канд. физ-мат. наук, Дедович Т.Г. (подпись) Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению подготовки «Информатика и вычислительная техника» профиль подготовки: «Технологии разработки программного обеспечения» Программа рассмотрена на заседании кафедры системного анализа и управления Протокол заседания от 20 г. Заведующий кафедрой, /_Чермисина Е.Н./ (ученое звание) (подпись) (фамилия, имя, отчество) СОГЛАСОВАНО Заведующий выпускающей кафедрой, профессор /Е.Н. Черемисина / (ученое звание) (подпись) (фамилия, имя, отчество) 20 г. И.о. директора института САУ, профессор / Е.Н. Черемисина / (ученое звание, степень) (подпись) 20 г. Рецензент: (ученая степень, ученое звание, Ф.И.О., место работы, должность) 20 г. Руководитель библиотечной системы / В.Г. Черепанова/ (подпись) (ФИО) 20 г. 2
3 Оглавление 1. Цели и задачи освоения дисциплины Место дисциплины в структуре ООП ВПО Требования к результатам освоения содержания дисциплины Содержание и структура дисциплины Объем дисциплины и виды учебных работ Структура дисциплины Содержание разделов дисциплины Практические занятия (семинары) Самостоятельное изучение разделов дисциплины Образовательные технологии Интерактивные образовательные технологии, используемые в аудиторных занятиях Оценочные средства для текущего контроля успеваемости и промежуточной аттестации Учебно-методическое обеспечение дисциплины Основная литература Дополнительная литература Периодические издания Интернет-ресурсы Методические указания к практическим занятиям Материально-техническое обеспечение дисциплины
4 1. Цели и задачи освоения дисциплины Теория языков программирования и методы трансляции дисциплина, объединяющая знания в области теории формальных языков, формальных грамматик, теории автоматов и методов трансляции. Целью данной дисциплины является систематическое рассмотрение основ формального описания языков программирования и методов трансляции, формальных моделей, методов и алгоритмов синтаксически управляемого разбора и перевода. В результате изучения курса студенты должны: ЗНАТЬ формальные способы задания синтаксиса и семантики языков программирования, основные положения теории формальных грамматик языков и автоматов, методы синтаксического анализа и перевода для классов формальных грамматик, используемых для описания основных конструкций языков программирования; УМЕТЬ самостоятельно формально описывать синтаксис и семантику несложных процедурно-ориентированных и проблемно-ориентированных языков программирования, разрабатывать алгоритмы синтаксического анализа для наиболее часто используемых классов формальных грамматик, пользоваться стандартной терминологией и определениями, читать научные статьи и пользоваться литературой для самостоятельного решения научно-исследовательских задач, связанных с разработкой языков и методов трансляции; ИМЕТЬ представление о перспективных направлениях работ и методологических подходах в области формальных методов описания языков и методов трансляции. 2. Место дисциплины в структуре ООП ВПО Дисциплина «Теория языков программирования и методы трансляции» относится к обязательным дисциплинам вариативной части профессионального цикла (Б3.В.ОД.11). Предшествующими курсами, на которых непосредственно базируется данная дисциплина, являются: «Алгоритмические языки и программирование», «Дискретная математика», «Математическая логика и теория алгоритмов», «Операционные системы», «Теория вычислительных процессов». Знания, умения и навыки, приобретенные при изучении данной дисциплины, используются при изучении курсов: «Технология разработки программного обеспечения», «Человеко-машинное взаимодействие», «Программное обеспечение сетей ЭВМ». Формы работы студентов: в ходе изучения дисциплины предусмотрены лекционные, семинарские занятия, выполнение домашних заданий. Самостоятельная студентов, предусмотренная учебным планом выполняется в ходе семестра в форме выполнения домашних заданий и написанию программ из раздела теории графов. 4
6 4. Различные виды грамматик: LL(k),LR(k), грамматики предшествования. Способы анализа данных грамматик 5. Промежуточные формы представления программ ПРК-1 ПК-2 Л13,Л14,Л15 С7,С8 Л16 С8 Умения: Результат обучения Компетенция Образовательная технология 1. Определять язык и ПК-2 Л5,Л6,Л7,Л8,Л9 тип грамматики. С3,С4,С5 Выполнять преобразования грамматик. Строить деревья вывода и синтаксический разбор 2. Строить различные типы автоматов по КС грамматике 3.Выполнять восходящий и нисходящий синтаксический разбор 4.Уметь анализировать различные типы грамматик 5.Составлять различные формы промежуточного представления программ ПК-2 ПРК-1 ПРК-1 ПК-2 Л2,Л3,Л4,Л10,Л11,Л12 С1,С2,С5,С6 Л11,Л12 С6 Л13,Л14,Л15 С7,С8 Л16 С8 Вид задания Применение: Результат обучения Компетенция Образовательная технология Применять знания, ПК-2, ПРК-1 Л1-Л16 полученные при С1-С8 изучении формальных грамматик и автоматов в практическом выполнении лексического и синтаксического 6 Вид задания
7 анализа в трансляторах Владение: Результат обучения Компетенция Образовательная технология 1. методами ПК-2 Л1-Л4 построения диаграммы С1,С2 лексического анализатора; Вид задания 2.Методами проведения синтаксического анализа ПК-2 Л5-Л16 С3-С8 Анализ: Результат обучения Компетенция Образовательная технология Для выбранного языка ПРК-1 Л5-Л16 программирования С3-С8 провести анализ для выбора соответствующего типа грамматики, автомата и типа анализа Вид задания Оценка: Результат обучения Компетенция Образовательная технология 1.Дать оценку ПРК-1 Л1-Л16 проблемных ситуаций, С1-С8 в том числе необходимость сочетать фазы лексического и синтаксического анализа, а также необходимость разрабатывать формальные методы для семантического анализа в трансляторах Вид задания Устный опрос 4. Содержание и структура дисциплины 4.1 Объем дисциплины и виды учебных работ 7
9 программ в трансляторах Итого Содержание разделов дисциплины Языки программирования. Классификация языков программирования по поколениям и типу вычислений. Критерии оценки языков прогр аммирования. Общая структура компилятора Лексический анализ и конечные автоматы. Лексический анализатор. Лексемы. Таблицы лексем и индентификаторов. Конечные автоматы (КА). Способы из залания. Детерменированные ДКА, недетерминированные НКА и полностью определенные конечные автоматы. Преобразование недетерминированного КА к детерминированному КА. Недостижимые состояния КА. Удаление недостижимых состояний КА. Эквивалентные состояния КА. Объединение эквивалентных состояний. Минимальный конечный автомат. Конечные преобразователиконечные преобразователи и лексический анализ. Синтаксический анализ. Формальные грамматики. Отношения выводимости. Язык порождаемый грамматикой. Формальные грамматики. Формальные грамматики. Алгоритмы проверку существования непустого языка, бесконечного языка. Классификация формальных грамматик Построение синтаксического дерева для КС грамматики. Свойства КСграмматик. Неоднозначные грамматики. Бесплодные и недостижимые символы грамматики. Удаление бесплодных и недостижимых символов. Алгоритмы удаления пустых цепочек, цепных правил, произвольного правила, левой факторицации. Приведенная грамматика. Нормальная форма Хомского. Преобразование к НФХ. Рекурсивные грамматики. Устранение левой рекурсии. Эквивалентность конечных автоматов и КС-грамматик. МП-автоматы. Расширенные МП-автоматы. Автоматы с магазинной паматью (МПавтоматы). Определение, конфигурация, такт работы и язык допускаемый МП-автоматом. Построение МП-автомата по КС грамматике. Работа анализатора с подбором альтернатив. Недетерминированные и детерминированные МП-автоматы. Расширенного автомат с МП. Определение, конфигурация, такт работы. Построение расширенного МП-автомата по КСграмматике. Работа восходящего анализатора. Детерминированный и недетерминированный расширенный МП-автомат. Определение МП-преобразователя и расширенного МП-преобразователя. Синтаксический анализ. Восходящий и нисходящий разбор. Методы синтаксического анализа. Нисходящий и восходящий разбор. Незацикливающиеся МП-преобразователи. Нисходящий и восходящий разбор с возвратом LL(k), LR(k) грамматики и грамматики предшествования. LL(1)-грамматика. Множества FIRST, FOLLOW, SELECT. Алгоритм разбора LL(1)-грамматик. LL(k)- грамматики. Рекурсивный спуск. Детерминированный разбор с помощью алгоритма «перенос-свертка». LR(k)-грамматика. Алгоритм разбора для LR(k)-грамматик. Грамматики предшествования. Понятия отношения предшествования. Алгоритм типа «перенос-свертка». Промежуточные формы представления программ. Польская запись. Тетрады. Триады. Байт-коды JVM 4.4 Практические занятия (семинары) Семинарские занятия призваны закрепить теоретические знания студентов и познакомить их с методами решения конкретных задач, возникающих при практическом приложении знаний. 9
10 Список семинаров Тема семинарского задания Неделя С1 С2 С3 С4 С5 С6 С7 С8 7 семестр Конечный автомат (КА). Способы задания КА. Разбор цепочки автоматом. Преобразование НКА в ДКА. Удаление недостижимых состояний в КА. Объединение эквивалентных состояний в КА. Конечные преобразователи. Вывод слов в грамматике. Классификация грамматик по Хомскому. Алгоритмы проверки пустого и конечного языка грамматики. Дерево вывода. Неоднозначные грамматики. Алгоритмы удаления бесплодных и недостижимых символов, пустых цепочек, произвольного правила, левой факторизации, цепных правил. Преобразование грамматик к НФХ. Алгоритм удаления левой рекурсии. Построение КА по КС грамматике. Работа МП-автомата и расширенного МП-автомата. Работа МП-преобразователя и расширенного МПпреобразователя. Нисходящий и восходящий разбор. Построение множеств FIRST, FOLLOW, SELECT для LL(1)-грамматик. Детерминированный разбор с помощью алгоритма «пе-ренос-свертка» Грамматики предшествования. Разбор алгоритма типа «перенос-свертка». Промежуточные формы представления: ПОЛИЗ, Тетрады, Триады Контрольные работы Для обобщающей аттестации студентов выполняются письменные контрольные работы по основным разделам (модулям) дисциплины и коллоквиумы. Тема работы неделя КР 1 Способы задания КА. Разбор цепочки автоматом. 3 КР 2 Преобразование НКА в ДКА. Удаление недостижимых состояний в КА. Объединение эквивалентных состояний в КА. Конечные преобразователи. КР 3 Вывод слов в грамматике. Классификация грамматик по 5 Хомскому. Алгоритмы проверки пустого и конечного языка грамматики. Дерево вывода. Неоднозначные грамматики. КР4 Алгоритмы удаления бесплодных и недостижимых 7 символов, пустых цепочек, произвольного правила, левой факторизации, цепных правил. КР 5 Преобразование грамматик к НФХ. Алгоритм 9 удаления левой рекурсии. Построение КА по КС грамматике. Работа МП-автомата и расширенного МП-автомата. КР6 Работа МП-преобразователя и расширенного МПпреобразователя. 11 Нисходящий и восходящий разбор. КР7 Построение множеств FIRST, FOLLOW, SELECT 13 для LL(1)-грамматик. Детерминированный разбор с 10
11 КР8 помощью алгоритма «перенос-свертка» Разбор алгоритма типа «перенос-свертка». Промежуточные формы представления: ПОЛИЗ, Тетрады, Триады Самостоятельное изучение разделов дисциплины Организация самостоятельной работы Самостоятельная студентов предполагается в виде: изучения отдельных вопросов тематического плана дисциплины; подготовка к практическим занятиям; выполнение домашних работ подготовка к зачету с оценкой Домашние работы Тема задания неделя семестр Д 1 Способы задания КА. Разбор цепочки автоматом. 3 Д 2 Преобразование КА. 5 Д3 Формальные грамматики и их преобразования 7 Д4 Работа МП-автомата и расширенного МП-автомата 9 Д5 Построение множеств FIRST, FOLLOW, SELECT для LL(1)-грамматик. Детерминированный разбор с помощью алгоритма «перенос-свертка» 5. Образовательные технологии В учебном процессе, помимо чтения лекций, которые составляют не более 50% аудиторных занятий, широко используются активные и интерактивные формы (компьютерных симуляций, деловых и ролевых игр, разбор конкретных ситуаций, психологические и иные тренинги). В сочетании с внеаудиторной работой это способствует формированию и развитию профессиональных навыков обучающихся. 13 Перечень обязательных видов работы студента посещение лекционных занятий; ответы на теоретические вопросы на семинаре; решение практических задач и заданий на семинаре; выполнение контрольных работ; выполнение домашних работ. 5.1 Интерактивные образовательные технологии, используемые в аудиторных занятиях Семестр Вид занятия (Л, ПР, ЛР) Используемые интерактивные образовательные технологии 7 Л Компьютерные 10 Количество часов 11
12 ПР презентации, Выполнение семестровых заданий 10 При изучении теоретического курса на лекциях предусматривается заложение материала в виде презентации. Отдельные лекции излагаются по проблемной технологии. Некоторые разделы теоретического курса изучаются с использованием опережающей самостоятельной работы: студенты получают задания на ознакомление с новым материалом до его изложения на лекциях. 6. Оценочные средства для текущего контроля успеваемости и промежуточной аттестации Вид контроля Форма учебной работы Текущий Обобщающий Итоговый 7 семестр Опросы Домашние работы Зачет с оценкой Вопросы к зачету с оценкой по дисциплине «Теория языков программирования и методы трансляции» 1. Классификация языков программирования по поколениям и типу вычислений 2. Критерии оценки языков прогр аммирования. Общая структура компилятора 3.Цели и задачи лексического анализатора. 4. Лексемы. Таблицы лексем и индентификаторов. 5. Конечные автоматы (КА). Способы из задания. 6. Детерменированные ДКА, недетерминированные НКА и полностью определенные конечные автоматы. 7.Преобразование недетерминированного КА к детерминированному КА. 8. Недостижимые состояния КА. Удаление недостижимых состояний КА. 9.Эквивалентные состояния КА. Объединение эквивалентных состояний. 10.Минимальный конечный автомат. 11.Конечные преобразователи 12.Конечные преобразователи и лексический анализ. 13.Формальные грамматики. Отношения выводимости. 14.Язык, порождаемый грамматикой 15.Алгоритмы проверку существования непустого языка 16.Алгоритмы проверку существования бесконечного языка. 17.Классификация формальных грамматик по Хомскому. 18.Построение синтаксического дерева для КС грамматики. 19.Свойства КС-грамматик. 20.Неоднозначные грамматики. 21.Бесплодные символы грамматики. Удаление бесплодных символов. 22. Недостижимые символы. Алгоритм удаления недостижимых символов 23.Алгоритмы удаления пустых цепочек, 12