СП - Экзаменационные вопросы

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Критерии проектирования стандартных библиотек.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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