Формальные языки и методы трансляции
2024/25 учебный год г., Математический, IV курс8 семестр(ы)
Специальности: Лектор (ы): Руководители практических занятий:
В рамках учебной дисциплины рассматриваются существующие концепции формальных языков, языков программирования, известные методы трансляции для реализации этих концепций, а также некоторые другие области приложений, где возникают задачи трансляции структурированных текстов.
Рассматривается традиционное разбиение решения задачи трансляции на стадии: а) лексический анализ; б) синтаксический анализ; в) семантический анализ. Изучаются следующие проблемы формальных языков и математические модели для выполнения трансляции теста:
- Определение синтаксиса и семантики формального языка. Проблема описания формального языка.
- Задача трансляции и области ее применения в задачах разработки системного и прикладного ПО.
- Теория регулярных языков и конечные автоматы. Задача сканирования текста для распознавания лексем.
- Теория контекстно-свободных грамматик. Формы Бэкуса – Наура. Задача грамматического разбора для построения синтаксического дерева.
- Алгоритмы синтаксически управляемого семантического анализа. Задача анализа семантики на основе обхода синтаксического дерева.
Содержание лекционных занятий
Гл.0. Введение. Синтаксис и семантика. Формальные языки. Задача трансляции и ее приложения. Виды трансляторов.
Гл.1. Проблема описания языка. Формы Бэкуса – Наура (БНФ).
Гл.2. Стадии трансляции. Общая схема трансляции. Роль и особенности стадий: лексический анализ, синтаксический анализ, семантический анализ, генерация и оптимизация кода, информационная таблица, распознавание ошибок во входном тексте.
Гл.3. Лексический анализ (ЛА). Регулярные языки. Регулярные выражения. Спецификация ЛА. Конечные автоматы (ДКА, НКА, e -КА). Реализация ЛА в виде ДКА.
Гл.4. Синтаксический анализ (СинА). Контекстно-свободные грамматические правила. Нисходящий и восходящий синтаксический разборы. Синтаксическая неоднозначность. Анализ и упрощение БНФ.
Гл.5. Семантический анализ (СемА). Синтаксически управляемый семантический анализ (СУ-анализ). Расширение БНФ за счет атрибутов и семантических действий. Спецификация СУ-анализа. Реализация СУ-анализа в виде обхода синтаксического дерева в процессе его построения. Алгоритм сдвиг-свертка.
Содержание практических занятий
Тема 1. Анализ синтаксиса и семантики программ (на примере "Hello World"). Разработка БНФ для описания синтаксиса.
Тема 2. Стадии трансляции. Разработка общей схемы транслятора (на примере трансляции арифметических выражений).
Тема 3. Применение регулярных языков для реализации лексического анализатора.
Тема 4. Применение грамматических правил в виде БНФ для реализации синтаксического анализатора.
Тема 5. Синтаксически-управляемый семантический анализ на основе построения (и обхода) синтаксического дерева. Примеры использования алгоритма сдвиг-свертка.
Формулировки задач по языкам программирования и методам трансляции
1. На основе решения упр.1.2 или взять другой ЯП. Предложить набор БНФ для заданного языка программирования, в котором учтена проблема списка аргументов внутри функции/оператора. Опционально – список операторов в коде программы.
2. Синтаксис арифметических выражений. На основе представленного на занятии набора БНФ построить 2..3 синтаксических дерева. Объяснить проблему синтаксической неоднозначности БНФ. Предложить вариант набора БНФ, учитывающий приоритет арифметических операций.
3. Синтаксис языка if-then-else. Предложить набор БНФ. Разобрать примеры построения синтаксических деревьев. Объяснить проблему синтаксической неоднозначности языка.
4. Разбор стадий трансляции логических выражений в псевдомашинный код. После выполнения стадии генерации кода предложите варианты оптимизации (по числу регистров, по числу команд).
5. Построить ДКА в упр.7.2 o). Все цепочки из 0 и 1, внутри есть «01». (На практике был построен НКА)
6. Построить ДКА для сканера из упр.7.19 е). Лексический анализатор для некоторого языка программирования.
7. Предложить СУ-анализатор для транслятора арифметических выражений в обратную польскую запись на основе алгоритма «сдвиг-свертка».
Для каждой из задач выше в ходе практических занятий и самостоятельной работы готовится ПОДРОБНОЕ письменное решение. Важно приводить не только окончательное решение, но и описать логику его построения. Необходимо выполнить анализ предлагаемого решения и обязательно разобрать на конкретных примерах.
Список литературы
1. Корзун Д. Ж. Практикум по формальным грамматикам и языкам. Учебное пос. Петрозаводск: Изд-во ПетрГУ, 2004. 46 с. Электронная версия.
2. Корзун Д.Ж., Богоявленский Ю.А. Lex и Yacc: генераторы программ лексического и синтаксического анализа. Уч. пос. для математических специальностей университетов. Часть I. Введение. Сер. «Информатика: основы и приложения». Петрозаводск: Изд-во ПетрГУ, 2007. 102 с.
3. Малявко, А.А. Формальные языки и компиляторы : учебное пособие / А.А. Малявко. – Новосибирск : Новосибирский государственный технический университет, 2014. – 431 с. : табл., схем. – (Учебники НГТУ). – Режим доступа: по подписке. – URL: https://biblioclub.ru/index.php?page=book&id=436055 – Библиогр. в кн. – ISBN 978-5-7782-2318-9. – Текст : электронный.
4. Молдованова, О.В. Языки программирования и методы трансляции : учебное пособие / О. В. Молдованова ; Федеральное агентство связи, Федеральное гос. образовательное бюджетное учреждение высш. проф. "Сибирский гос. ун-т телекоммуникаций и информатики" (ФГОБУ ВПО "СибГУТИ"). - Новосибирск : ФГОБУ ВПО "СибГУТИ", 2012. - 134 с.
5. Пратт Т., Зелковиц М. Языки программирования: разработка и реализация: Пер. с англ. Под общей ред. А. Матросова. СПб.: Питер, 2002.
6. Информационный ресурс http://mathhelpplanet.com/static.php. Раздел «Дискретная математика». Подразделы: «Конечные автоматы и регулярные языки», «Контекстно-свободные языки».
