Лектор: Певзнер Людмила Владимировна

4-й курс, 7-й семестр 2001-2002 учебного года.

1. Структура транслятора. Основные блоки. Связи между ними. Базовый математический аппарат.
2. Формальные грамматики как математический аппарат для описания языков программирования. Классификация формальных языков. Задачи использования формальных языков (порождение, распознавание, однозначность).
3. Описание языков программирования с помощью формальных грамматик. Нормальная форма Бекуса-Наура. Синтаксические диаграммы.
4. Конечные автоматы как математический аппарат для построения лексического анализатора. Связь формальных грамматик и конечных автоматов.
5. Задача синтаксического анализа. Описание языка и стратегии синтаксического анализа. Основные ограничения, накладываемые на грамматику языка программирования, при использовании различных стратегий.
6. Синтаксический анализ с использованием алгоритма рекурсивного спуска. Преобразование грамматики.
7. Преобразование грамматики - устранение левой рекурсии.
8. Преобразование грамматики - замена левого или правого края.
9. Преобразование грамматики - удаление пустых правил.
10. Функция FIRST(k), FOLLOW(k).
11. LL(k) - грамматики. Общие свойства.
12. Алгоритм определения - является ли грамматика LL(k) при заданном k.
13. Синтаксический анализ с использованием LL(k) - грамматик.
14. Алгоритм построения управляющей LL(k) - таблицы.
15. LR(k) - грамматики. Общие свойства.
16. Алгоритм определения - является ли грамматика LR(k) при заданном k.
17. Синтаксический анализ с использованием LR(k) - грамматик.
18. Алгоритм построения управляющей LL(k) - таблицы.
19. Функция EFF(k).
20. Грамматики предшествования. Общие свойства.
21. Алгоритм определения - является ли данная грамматика грамматикой предшествования.
22. Синтаксический анализ с использованием грамматик предшествования.
23. Алгоритм построения матрицы предшествования.
24. Сравнительный анализ последовательных алгоритмов трансляции.
25. Атрибутные транслирующие грамматики (АТГ). Использование АТГ для проверки контекстных условий и построения тетрад.
26. Атрибутные транслирующие грамматики (АТГ). Использование АТГ для проверки контекстных условий и построения триад.
27. Атрибутные транслирующие грамматики (АТГ). Использование АТГ для проверки контекстных условий и построения ПОЛИЗ.
28. Атрибутные транслирующие грамматики (АТГ). Использование АТГ преобразования чисел из одной системы счисления в другую.