Теория вычислительных процессов и структур. Селиверстов М.Н. - 5 стр.

управляемые трансляции; детерминированная генерация выхода трансляции по левосто-
роннему анализу входа.
      8. LL(k)-грамматики: определение и свойства.
      9. LL(k)-трансляции: K-предсказывающие алгоритмы анализа; построение 1-
предсказывающего алгоритма анализа по LL(1)-грамматике; анализ в LL(k)-грамматиках;
тестирование LL(k)-грамматик; вычисление функции (β); вычисление функции σ(A); К-
предсказывающий алгоритм трансляции; непростые LL(k)-трансляции и магазинные про-
цессоры; непростые LL(k)-трансляции и магазинные процессоры.
      10. LR(k)-трансляции: Синтаксический анализ типа “снизу-вверх”; LR(k)-
грамматики; LR(k)-анализатор; свойства LR(k)-грамматик; тестирование LR(k)-
грамматик; канонические LR(k)-анализаторы; резюме свойств LR(k)-анализаторов; кор-
ректность LR(k)-анализаторов.

Трансляторы и методы их разработки

       11. Компиляторы и интерпретаторы. Перевод и генерация кода. Роль перевода в
процессе компиляции.
       12. Типы компиляторов: прямой компилятор, кросс-транслятор, конвертер. Вирту-
альная машина. Пример виртуальной машины: Java-машина. Фазы компиляции. Внешний
интерфейс (front-end) и внешний интерфейс (back-end).
       13. Способы описания синтаксиса языков. Форма Бэкуса-Наура как наиболее рас-
пространенный способ описания синтаксиса. Расширенная форма Бэкуса-Наура. Графиче-
ское представление синтаксиса. Грамматика ван Вейнгаардена.
       14. Семантика языка. Способы определения семантики: интерпретационная и
трансляционная семантики, аксиоматическое определение семантики, определение семан-
тики через расширение.
       15. Понятие проекции конструкции исходного языка. Представление значений.
Представление примитивных значений. Представление структурных значений, проблема
выравнивания. Представление многомерных значений. Представление строковых значе-
ний. Представление процедурных значений. Представление объектов. Стандарты, опреде-
ляющие системный интерфейс.
       16. Способы передачи информации о транслируемой программе между просмот-
рами транслятора. Древовидные и табличные структуры данных. Возможные структуры
таблиц: таблицы с прямым доступом, таблицы расстановки, функции расстановки. Разра-
ботка конкретной структуры таблиц.
       17. Методы динамического распределения памяти. Уплотнение памяти. Типы па-
мяти, используемые во время исполнения программы: стек, куча, пузырь. Проблемы обра-
зования “мусора”. Алгоритмы сборки мусора.
       18. Способы передачи и представления информации о стандартной языковой об-
становке.
       19. Методы реализации лексического анализа. Детерминированные конечные ав-
томаты. Обработка идентификаторов при лексическом анализе. Таблица идентификато-
ров, использование хеш-функций.
       20. Методы реализации синтаксического анализа. Метод рекурсивного спуска для
создания синтаксического анализатора. Метод “перенос/свертка”. Анализ снизу вверх
(сдвиг-свертка). LR(1)-элементы. LR(1)-анализатор. Понятие о LALR(1)-анализе. Нейтра-
лизация синтаксических ошибок.
       21. Семантический анализ. Атрибутные грамматики. Вычисление атрибутов. L-
атрибутные грамматики. Атрибуты типов, переменных и выражений.
       22. Обработка описаний и идентификация. Использование таблицы символов.
       23. Обработка обозначений типов и контроль типов. Таблица типов. Эквивалент-
ность типов.

                                         5