(c) Larry Ewing, Simon Budig, Garrett LeSage
с 1994 г.

Кафедра Информатики и Математического Обеспечения

ПетрГУ | ИМиИТ | О кафедре | Проекты | Лаборатория ИТС | Семинары НФИ/AMICT
Сотрудники | Учебный процесс | Табель-календарь | Курсовые и выпускные работы
Вычислительные ресурсы | Публикации | Архив новостей | Контактная информация

Языки программирования и методы трансляции I

2020/21 учебный год г., Математический, III курс
5 семестр(ы)
Специальности: Лектор (ы): Руководители практических занятий:

В рамках учебной дисциплины рассматриваются существующие концепции языков программирования, известные методы трансляции для реализации этих концепций, а также некоторые другие области приложений, где возникают задачи трансляции структурированных текстов.

Рассматривается традиционное разбиение решения задачи трансляции на стадии: а) лексический анализ; б) синтаксический анализ; в) семантический анализ. Изучаются следующие проблемы формальных языков и математические модели для выполнения трансляции теста:

Инструкции по дистанционному обучению

  1. В соответствии с темами лекционных и практических занятий ниже сформулированы условия задач по языкам программирования и методам трансляции.
  2. По теме каждой задачи обучающийся изучает теоретический материал в соответствии с указанным списком литературы и дистанционных лекционных занятиях. При необходимости обучающийся по эл.почте консультируется с лектором, который уточняет конкретные разделы для изучения в литературе.
  3. Обучающийся готовит в эл.виде решения по задачам. Отправляет решение очередной задачи по email лектору. Данный пункт требует отправки не менее одного решения каждую неделю (либо первую версию решения по новой задаче, либо скорректированный вариант по одному из предыдущих решений).
  4. Лектор оценивает решение и высылает комментарии по ее улучшению. Соответствующее обсуждение также проводится во время дистанционных занятий (1 ч. лекции + 2 ч. практики).
  5. Шаги 1-4 повторяются еженедельно. Ведется учет в журнале учебной дисциплины.

В итоге, к концу семестра каждый обучающийся должен сформировать набор из решений задач, каждая должна быть скорректирована не менее 1 раза по результатам комментариев от лектора. Аттестационное занятие будет построено в виде индивидуального собеседования с обучающимся по представленным решениям. Представленный список задач следует рассматривать как список теоретических вопросов по учебной дисциплине.

Формулировки задач по языкам программирования и методам трансляции

  1. [Анализ синтаксиса и семантики программ, лекции: гл.0-1]. Анализ программы «Hello World» (упр. 1.1-1.10). Выбрать программу на любом языке программирования. Разобрать ее синтаксис. Т.е. описать, как устроен текст программы. Как правило, программа имеет древовидную структуру. Есть ли общие правила для построения такого дерева, применимые для других программ на этом языке. Ключевые шаги решения следующие.
    • Выбрать ЯП и вариант программы «Hello World» (текст программы с комментариями).
    • Определить практическую задачу, для которой требуется проводить анализ программы «Hello World». (для изучения языка программистом, для разработки транслятора)
    • Выполнить анализ примера программы с построением синтаксического дерева (как текст программы делится на части, как затем каждая часть делится). В листьях дерева будут подстроки из текста программы (необязательно одиночные символы!).
    • Выполнить анализ построения дерева и выделить «общие» синтаксические правила построения программ (не только «Hello World») на выбранном языке.
    • Привязать полученное решение (конкретное синтаксическое дерево и набор общих синтаксических правил) к практической задаче из шага 1. В какой степени решается поставленная практическая задача?
  2. [разбор синтаксиса, лекции: гл.0-1]. Задачи на построение БНФ (упр. 2.1, 2.2., 2.10).
    • Упражнение 2.1 из задачника. По образу задачи, рассмотренной на лекции для предложений естественного языка. Выбрать одно из предложений на естественном языке, построить синтаксическое дерево, сформулировать набор БНФ.
    • Упражнение 2.2 из задачника. Исследовать случай, когда перед существительным (peanut) может быть произвольное число прилагательных (salted, big, brown, roasted, …).
    • Упражнение 2.10 из задачника. Аналогично задачам по построению БНФ для заданного языка (разобраны на лекции: язык идентификаторов, язык арифметических выражений). Выбрать одну из конструкций (объектов), для которой предложить набор БНФ.
  3. [стадии трансляции, лекции: гл.1]. Разбор стадий трансляции арифметических выражений в псевдомашинный код (упр.3.1). Шаги решения следующие.
    • предложить псевдомашинный код (система команд для вычисления арифметических операций, похоже на ассемблер).
    • описать информационную таблицу (для хранения информации о переменных, числовых константах и пр.).
    • описать стадию лексического анализа (какие лексемы распознавать, работа с инф. таблицей). Привести пример (ручной) работы лексического анализатора.
    • описать стадию синтаксического анализа (синтаксис в виде БНФ, работа с инф. таблицей). Привести пример (ручной) работы синтаксического анализатора.
    • описать стадию семантического анализа (схема обхода синтаксического дерева, правила генерации кода при обработке вершин дерева). Привести пример (ручной) работы семантического анализатора с генерацией конкретной программы на псевдомашинном коде.
    • разобрать варианты оптимизации генерируемого кода (изменение синтаксического дерева, изменение обхода дерева и др.). Привести пример оптимизации для уменьшения используемой памяти (число регистров) или повышения скорости работы (уменьшение размера программы – число инструкций в программе).
  4. [Регулярные языки, лекции: гл.2]. Построение ДКА для заданного языка.Часть I. Рассмотреть упр.7.2. Выбрать любой пример a)..t). Для заданного примера построить:
    • регулярное выражение (РВ), описывающее заданное множество цепочек (строк);
    • конечный автомат (КА), допускающий заданное множество цепочек (строк); Построен НКА, ДКА или e-КА?
      Часть I’. Полученный КА преобразовать (если требуется) в ДКА.
    • Использовать интуитивный способ преобразования (для данного конкретного КА).
      Часть II’. Кратко сформулировать общий алгоритм преобразования НКА к ДКА.
    • Соответствующую теорию можно найти в одном из учебников:
      • Грис Д. Конструирование компиляторов для цифровых вычислительных машин.
      • Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов.
      • Детерминизация конечных автоматов, http://mathhelpplanet.com/static.php?p=determinizatsiya-konechnykh-avtomatov
      Часть II. Рассмотреть упр. 7.3 или 7.4. Выбрать любой пример в одном из этих упражнений. Построить эквивалентный ДКА по заданному КА.
    • Использовать общий алгоритм преобразования НКА к ДКА.
    Каждое предлагаемое решение на шагах а)-д) необходимо обосновывать, например, подробно описывая шаги построения решения. Проверку каждого предлагаемого решения необходимо выполнять на примерах (положительных и отрицательных).
  5. [Применение регулярных языков для реализации лексического анализатора, лекции: гл.2]. Разработка лексического анализатора для транслятора арифметических выражений.
    • Рассмотреть спецификацию лексического анализатора для транслятора арифметических выражений в псевдомашинный код (задача №3, упр.3.1). Построить регулярные выражения для каждого типа распознаваемых лексем.
    • Для каждого РВ предложить КА, который распознает тексты соответствующих лексем. Обосновать предлагаемый КА, проверить работу на нескольких примерах.
    • Объединить полученный набор КА в один КА (с общим начальным состоянием).
    • Преобразовать общий КА в ДКА. Охарактеризовать лексический смысл каждого финального состояния полученного ДКА.
    • Показать работу ДКА как ЛА на примере. Какие лексические ошибки могут быть обнаружены с помощью данного ДКА?
  6. [Грамматические правила в виде БНФ, лекции: гл.3]. Задана КС-грамматика (в виде набора БНФ, первая синтаксическая переменная - начальная). Построить эквивалентную однозначную грамматику, которая содержит только достижимые и производящие символы.
    • Выбрать грамматику в упр. 8.5 задачника. Какие цепочки она описывает?
    • Найти и удалить бесплодные синтаксические переменные.
    • Найти и удалить недостижимые символы (синтаксические переменные и синтаксические константы).
    • Если приведённая грамматика является неоднозначной, то предложить эквивалентную однозначную грамматику.
  7. [Синтаксически-управляемый семантический анализ, лекции: гл.4]. Задана КС-грамматика (в виде набора БНФ, первая синтаксическая переменная - начальная). Выполнить разбор некоторой цепочки, используя алгоритм «сдвиг-свертка». Семантические действия и атрибуты применять не требуется.
    • Выбрать грамматику в упр. 9.1 или 9.2 задачника.
    • Предложите пример синтаксически правильной цепочки для выбранной грамматике. Нужно построить синтаксическое дерево.
    • Выполните разбор данной цепочки в соответствии с алгоритмом «сдвиг-свертка». Убедитесь, что в работе алгоритма появляется то же дерево, что было построено на шаге б).

Содержание лекционных занятий

Содержание практических занятий

Список литературы


Вопросы к зачетному заданию.