Вопросы к экзамену по курсу «Системы программирования» (2007)

Экзамен по курсу «Системы программирования» будет проходить в письменной форме. Итоговая оценка по курсу будет выставляться в соответствии с баллами, получеными на коллоквиуме и экзамене, учтенными соответственно с коэффициентами 2 и 3:

итоговая оценка = ( баллы-коллоквиум ) x 2 + ( баллы-экзамен ) x 3

Теоретические вопросы

Этапы жизненного цикла программного продукта.

Состав и схема функционирования классической системы программирования.

Типы трансляторов, особенности интерпретаторов и компиляторов. Смешанная стратегия трансляции.

Общая схема работы компилятора.

Основные понятия теории формальных грамматик и языков.

Эквивалентные грамматики.

Классификация формальных грамматик и языков по Хомскому.

Соотношения между типами грамматик.

Соотношения между типами языков.

10.

Задача разбора. Дерево вывода.

11.

Неоднозначность грамматик и языков.

12.

Недостижимые и бесполезные (бесплодные) символы грамматики. Алгоритмы удаления недостижимых и бесполезных (бесплодных) символов. Приведенная грамматика.

13.

Определение недетерминированного конечного автомата (НКА).

14.

Диаграмма состояний (ДС) конечного автомата.

15.

Леволинейные регулярные грамматики и конечные автоматы.

16.

Определение детерминированного конечного автомата (КА).

17.

Алгоритм построения детерминированного конечного автомата по НКА.

18.

Задачи лексического анализа.

19.

Лексический анализ на основе регулярных грамматик.

20.

Объектная модель лексического анализатора. Схема его работы.

21.

Задачи синтаксического анализа.

22.

Метод рекурсивного спуска (РС-метод): назначение, семантика процедур метода рекурсивного спуска.

23.

Достаточные условия применимости метода рекурсивного спуска.

24.

Исследование применимости РС-метода в случае наличия ε-альтернативы и итерационных правил.

25.

Задачи семантического анализа. Грамматики с действиями.

26.

Объектная модель синтаксического анализатора.

27.

Использование исключений С++ при обработке синтаксических ошибок и нарушении контекстных условий.

28.

Свойства языка внутреннего представления программы, примеры таких языков.

29.

Синтаксически управляемый перевод: идея, принципы организации, примеры.

30.

ПОЛИЗ выражений.

31.

ПОЛИЗ операторов языков программирования.

32.

Генерация ПОЛИЗа выражений и операторов.

33.

Интерпретация ПОЛИЗа.

34.

Использование исключений С++ при обработке ошибок периода выполнения.

35.

Основные стратегии распределения памяти.

36.

Принципы реализации виртуальных функций.

37.

Машинно-независимая и машинно-зависимая оптимизация. Примеры оптимизирующих преобразований.

38.

Интегрированная среда разработки программного обеспечения (ИСР).

39.

Основные функции редактора текстов в рамках ИСР. Примеры его интегрированности с другими компонентами ИСР.

40.

Отладчики, их возможности. Примеры интегрированности отладчика с другими компонентами ИСР.

41.

Редактор внешних связей, его назначение и принципы работы. Загрузчик.

42.

Библиотеки. Основные типы библиотек.

43.

Критерии проектирования стандартных библиотек.

44.

Стандартная библиотека С++.

45.

Стандартная библиотека шаблонов STL: контейнеры, итераторы, алгоритмы, аллокаторы.

46.

Стандартная библиотека шаблонов STL: шаблонные классы vector и list.

Практические навыки

Определить, к какому типу по Хомскому относится заданная грамматика.

Определить тип языка, порождаемого данной грамматикой.

Построить грамматику [определенного типа], порождающую заданный язык.

Определить, какой язык порождает заданная грамматика.

Построить дерево вывода (разбора) заданной цепочки по заданной КС-грамматике.

Получение приведенной грамматики.

Дана леволинейная регулярная грамматика. Построить по ней ДС конечного автомата, по ДС написать анализатор на С++.

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

Дан текст анализатора на С++. Восстановить леволинейную регулярную грамматику по данному анализатору.

10.

Дана леволинейная регулярная грамматика, которой соответствует НКА. Построить эквивалентный детерминированный КА (использовать алгоритм построения детерминированного КА по НКА).

11.

Применим ли метод рекурсивного спуска к заданной КС-грамматике. Ответ обосновать.

12.

Для заданной КС-грамматики построить анализатор методом рекурсивного спуска.

13.

Дан анализатор, написанный методом рекурсивного спуска. Восстановить КС-грамматику.

14.

Дана грамматика с действиями. Какой язык она порождает?

15.

Дана КС-грамматика. Дополнить ее действиями, позволяющими учесть дополнительные ограничения на цепочки определяемого языка.

16.

Дана грамматика (или написать грамматику) языка L1. Вставить в грамматику действия по переводу цепочек языка L1 в цепочки языка L2.

17.

Дана грамматика с действиями, осуществляющими перевод цепочек языка L1 в цепочки языка L2. Описать языки L1 и L2.

18.

Записать в ПОЛИЗе заданный фрагмент программы на языке Х.

19.

Задан фрагмент программы в ПОЛИЗе. Восстановить текст на языке Х.

20.

Определить, является ли данная запись ПОЛИЗом заданной конструкции.

21.

Разработать ПОЛИЗ заданной конструкции некоторого языка. Вставить в грамматику действия, порождающие ПОЛИЗ этой конструкции.

22.

Решение простейших задач с использованием компонент библиотеки STL (vector и list).