Языки программирования и методы трансляции
2022/23 учебный год г., Математический, IV курс7 семестр(ы)
Специальности: Лектор (ы): Руководители практических занятий:
В рамках учебной дисциплины рассматриваются существующие концепции языков программирования, известные методы трансляции для реализации этих концепций, а также некоторые другие области приложений, где возникают задачи трансляции структурированных текстов.
Рассматривается традиционное разбиение решения задачи трансляции на стадии: а) лексический анализ; б) синтаксический анализ; в) семантический анализ. Изучаются следующие проблемы формальных языков и математические модели для выполнения трансляции теста:
- Определение синтаксиса и семантики формального языка. Проблема описания формального языка.
- Задача трансляции и области ее применения в задачах разработки системного и прикладного ПО.
- Теория регулярных языков и конечные автоматы. Задача сканирования текста для распознавания лексем.
- Теория контекстно-свободных грамматик. Формы Бэкуса – Наура. Задача грамматического разбора для построения синтаксического дерева.
- Алгоритмы синтаксически управляемого семантического анализа. Задача анализа семантики на основе обхода синтаксического дерева.
Формулировки задач по языкам программирования и методам трансляции
- [Анализ синтаксиса и семантики программ, лекции: гл.0-1]. Анализ программы «Hello World» (упр. 1.1-1.10). Выбрать программу на любом языке программирования. Разобрать ее синтаксис. Т.е. описать, как устроен текст программы. Как правило, программа имеет древовидную структуру. Есть ли общие правила для построения такого дерева, применимые для других программ на этом языке. Ключевые шаги решения следующие.
- Выбрать ЯП и вариант программы «Hello World» (текст программы с комментариями).
- Определить практическую задачу, для которой требуется проводить анализ программы «Hello World». (для изучения языка программистом, для разработки транслятора)
- Выполнить анализ примера программы с построением синтаксического дерева (как текст программы делится на части, как затем каждая часть делится). В листьях дерева будут подстроки из текста программы (необязательно одиночные символы!).
- Выполнить анализ построения дерева и выделить «общие» синтаксические правила построения программ (не только «Hello World») на выбранном языке.
- Привязать полученное решение (конкретное синтаксическое дерево и набор общих синтаксических правил) к практической задаче из шага 1. В какой степени решается поставленная практическая задача?
- [разбор синтаксиса, лекции: гл.0-1]. Задачи на построение БНФ (упр. 2.1, 2.2., 2.10).
- Упражнение 2.1 из задачника. По образу задачи, рассмотренной на лекции для предложений естественного языка. Выбрать одно из предложений на естественном языке, построить синтаксическое дерево, сформулировать набор БНФ.
- Упражнение 2.2 из задачника. Исследовать случай, когда перед существительным (peanut) может быть произвольное число прилагательных (salted, big, brown, roasted, …).
- Упражнение 2.10 из задачника. Аналогично задачам по построению БНФ для заданного языка (разобраны на лекции: язык идентификаторов, язык арифметических выражений). Выбрать одну из конструкций (объектов), для которой предложить набор БНФ.
- [стадии трансляции, лекции: гл.1]. Разбор стадий трансляции арифметических выражений в псевдомашинный код (упр.3.1). Шаги решения следующие.
- предложить псевдомашинный код (система команд для вычисления арифметических операций, похоже на ассемблер).
- описать информационную таблицу (для хранения информации о переменных, числовых константах и пр.).
- описать стадию лексического анализа (какие лексемы распознавать, работа с инф. таблицей). Привести пример (ручной) работы лексического анализатора.
- описать стадию синтаксического анализа (синтаксис в виде БНФ, работа с инф. таблицей). Привести пример (ручной) работы синтаксического анализатора.
- описать стадию семантического анализа (схема обхода синтаксического дерева, правила генерации кода при обработке вершин дерева). Привести пример (ручной) работы семантического анализатора с генерацией конкретной программы на псевдомашинном коде.
- разобрать варианты оптимизации генерируемого кода (изменение синтаксического дерева, изменение обхода дерева и др.). Привести пример оптимизации для уменьшения используемой памяти (число регистров) или повышения скорости работы (уменьшение размера программы – число инструкций в программе).
- [Регулярные языки, лекции: гл.2]. Построение ДКА для заданного языка.Часть I. Рассмотреть упр.7.2. Выбрать любой пример a)..t). Для заданного примера построить:
- регулярное выражение (РВ), описывающее заданное множество цепочек (строк);
- конечный автомат (КА), допускающий заданное множество цепочек (строк); Построен НКА, ДКА или e-КА?
Часть I’. Полученный КА преобразовать (если требуется) в ДКА. - Использовать интуитивный способ преобразования (для данного конкретного КА).
Часть II’. Кратко сформулировать общий алгоритм преобразования НКА к ДКА. - Соответствующую теорию можно найти в одном из учебников:
- Грис Д. Конструирование компиляторов для цифровых вычислительных машин.
- Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов.
- Детерминизация конечных автоматов, http://mathhelpplanet.com/static.php?p=determinizatsiya-konechnykh-avtomatov
- Использовать общий алгоритм преобразования НКА к ДКА.
- [Применение регулярных языков для реализации лексического анализатора, лекции: гл.2]. Разработка лексического анализатора для транслятора арифметических выражений.
- Рассмотреть спецификацию лексического анализатора для транслятора арифметических выражений в псевдомашинный код (задача №3, упр.3.1). Построить регулярные выражения для каждого типа распознаваемых лексем.
- Для каждого РВ предложить КА, который распознает тексты соответствующих лексем. Обосновать предлагаемый КА, проверить работу на нескольких примерах.
- Объединить полученный набор КА в один КА (с общим начальным состоянием).
- Преобразовать общий КА в ДКА. Охарактеризовать лексический смысл каждого финального состояния полученного ДКА.
- Показать работу ДКА как ЛА на примере. Какие лексические ошибки могут быть обнаружены с помощью данного ДКА?
- [Грамматические правила в виде БНФ, лекции: гл.3]. Задана КС-грамматика (в виде набора БНФ, первая синтаксическая переменная - начальная). Построить эквивалентную однозначную грамматику, которая содержит только достижимые и производящие символы.
- Выбрать грамматику в упр. 8.5 задачника. Какие цепочки она описывает?
- Найти и удалить бесплодные синтаксические переменные.
- Найти и удалить недостижимые символы (синтаксические переменные и синтаксические константы).
- Если приведённая грамматика является неоднозначной, то предложить эквивалентную однозначную грамматику.
- [Синтаксически-управляемый семантический анализ, лекции: гл.4].
Задана КС-грамматика (в виде набора БНФ, первая синтаксическая переменная - начальная). Выполнить разбор некоторой цепочки, используя алгоритм «сдвиг-свертка». Семантические действия и атрибуты применять не требуется.
- Выбрать грамматику в упр. 9.1 или 9.2 задачника.
- Предложите пример синтаксически правильной цепочки для выбранной грамматике. Нужно построить синтаксическое дерево.
- Выполните разбор данной цепочки в соответствии с алгоритмом «сдвиг-свертка». Убедитесь, что в работе алгоритма появляется то же дерево, что было построено на шаге б).
Содержание лекционных занятий
- Гл.0. Введение. Синтаксис и семантика. Формальные языки. Задача трансляции и ее приложения. Виды трансляторов.
- Гл.1. Стадии трансляции. Общая схема трансляции. Роль и особенности стадий: лексический анализ, синтаксический анализ, семантический анализ, генерация и оптимизация кода, информационная таблица, распознавание ошибок во входном тексте.
- Гл.2. Лексический анализ (ЛА). Регулярные языки. Регулярные выражения. Спецификация ЛА. Конечные автоматы (ДКА, НКА, e-КА). Реализация ЛА в виде ДКА.
- Гл.3. Синтаксический анализ (СинА). Контекстно-свободные грамматические правила. Формы Бэкуса – Наура (БНФ). Нисходящий и восходящий синтаксический разборы. Синтаксическая неоднозначность. Анализ и упрощение БНФ.
- Гл.4. Семантический анализ (СемА). Синтаксически управляемый семантический анализ (СУ-анализ). Расширение БНФ за счет атрибутов и семантических действий. Спецификация СУ-анализа. Реализация СУ-анализа в виде обхода синтаксического дерева в процессе его построения. Алгоритм сдвиг-свертка.
Содержание практических занятий
- Тема 1. Анализ синтаксиса и семантики программ (на примере "Hello World"). Разработка БНФ для описания синтаксиса.
- Тема 2. Стадии трансляции. Разработка общей схемы транслятора (на примере трансляции арифметических выражений).
- Тема 3. Применение регулярных языков для реализации лексического анализатора.
- Тема 4. Применение грамматических правил в виде БНФ для реализации синтаксического анализатора.
- Тема 5. Синтаксически-управляемый семантический анализ на основе построения (и обхода) синтаксического дерева. Примеры использования алгоритма сдвиг-свертка.
Список литературы
- Корзун Д.Ж. Практикум по формальным грамматикам и языкам. Учеб. пособие. Петрозаводск: Изд-во ПетрГУ, 2004. 46 с. Электронная версия.
- Корзун Д.Ж., Богоявленский Ю.А. Lex и Yacc: генераторы программ лексического и синтаксического анализа. Уч. пос. для математических специальностей университетов. Часть I. Введение. Сер. «Информатика: основы и приложения». Петрозаводск: Изд-во ПетрГУ, 2007. 102 с.
- Малявко, А.А. Формальные языки и компиляторы : учебное пособие / А.А. Малявко. – Новосибирск : Новосибирский государственный технический университет, 2014. – 431 с. : табл., схем. – (Учебники НГТУ). – Режим доступа: по подписке. – URL: https://biblioclub.ru/index.php?page=book&id=436055 – Библиогр. в кн. – ISBN 978-5-7782-2318-9. – Текст : электронный.
- Молдованова, О.В. Языки программирования и методы трансляции : учебное пособие / О. В. Молдованова ; Федеральное агентство связи, Федеральное гос. образовательное бюджетное учреждение высш. проф. "Сибирский гос. ун-т телекоммуникаций и информатики" (ФГОБУ ВПО "СибГУТИ"). - Новосибирск : ФГОБУ ВПО "СибГУТИ", 2012. - 134 с.
- Пратт Т., Зелковиц М. Языки программирования: разработка и реализация: Пер. с англ. Под общей ред. А. Матросова. СПб.: Питер, 2002.
- Грис Д. Конструирование компиляторов для цифровых вычислительных машин. Москва: Мир, 1975. — 544 с.
- Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. Addison Wesley Publishing company,1976 г. - 655 c. Перевод книги под ред. Агафонова В.Н. - изд."Мир", 1979 г.
- Информационный ресурс http://mathhelpplanet.com/static.php. Раздел «Дискретная математика». Подразделы: «Конечные автоматы и регулярные языки», «Контекстно-свободные языки».
