Раздел 1. Языки и методы программирования

1.1. Синтаксически-ориентированная трансляция.

Понятие транслятора, компилятора, интерпретатора. Общая схема работы транслятора. Трансляция, основанная на структуре текста. Метод синтаксически-ориентированной трансляции. Формальная модель Хомского. Этапы синтаксически-ориентированной трансляции.

1.2. Языки и цепочки символов. Способы задания языков.

Понятие языка, алфавита. Терминальные, нетерминальные символы. Цепочка символов. Пустая цепочка. Способы задания языков.

1.3. Определение грамматики.

Понятие грамматики. Виды грамматики. Терминальные, нетерминальные символы. Словари: терминальный, нетерминальный, полный. Определение языков по грамматики. Определение грамматики по языку.

1.4. Классификация языков и грамматик. Сентенциальная форма грамматики.

Формальные грамматики. Классификация грамматик по Хомскому. Сентенциальная форма грамматики.

1.5. Преобразование КС-грамматик.

Эквивалентные преобразования КС-грамматик. Приведенная грамматика. Алгоритм приведения КС-грамматики к приведенной форме. Алгоритм удаления бесполезных символов. Алгоритм удаления ε-правил. Удаление цепных правил.

1.6. Грамматики в нормальной форме.

Нормальные формы КС-грамматик. Нормальная форма Хомского. Алгоритм преобразования КС-грамматики в нормальную форму Хомского. Нормальная форма Грейбах. Алгоритм перобразования КС-грамматики в нормальную форму Грейбах.

1.7. Синтаксический анализ КС-языков. Методы синтаксического анализа.

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

1.8. Конечные автоматы и преобразователи.

Распознающий автомат, составные части. Принцип работа распознавателя. Такт работы распознавателя. Конфигурации распознавателя. Понятие конечного автомата. Конфигурация автомата. Детерминированный конечный автомат.

1.9. Автоматные грамматики и конечные автоматы.

Автоматные грамматики. Решение проблемы принадлежности, проблемы пустоты языка, проблема эквивалентности для конечных автоматов. Меры сложности.

1.10. Конечные преобразователи.

Конечный преобразователь. Недетермированный конечный преобразователь. Конфигурация конечного преобразователя. Такт работы конечного преобразователя.

1.11. Автоматы и преобразователи с магазинной памятью.

Автоматы с магазинной памятью. Конфигурация автомата с магазинной памятью. Такт работы автомата с магазинной памятью. Начальная конфигурация автомата с магазинной памятью. Определение языка с помощью автомата с магазинной памятью.

Литература:

1. Свердлов С.З. Языки программирования и методы трансляции. – СПб: Питер, 2007.

2. Опалева Э.А., Самойленко В.П. Языки программирования и методы трансляции. – СПб: БХВ-Петербург, 2005.

3. Карпов Ю.Г. Основы построения трансляторов. – СПБ: БХВ-Петербург, 2005.