Учебное пособие. Новосибирск/СибГУТИ, 2012. – 134 с.Учебное пособие предназначено для студентов, обучающихся по направлению 230100 «Информатика и вычислительная техника» и изучающих дисциплину «Теория языков программирования и методы трансляции». В нём содержится материал, предназначенный для проведения практических или лабораторных занятий по указанному учебному курсу с целью изучения основных принципов теории формальных языков и грамматик, а также методов лексического и синтаксического анализа современных языков программирования.Введение
Основные концепции языков программирования
Языки программирования
Классификация языков программирования
Критерии оценки языков программирования
Влияние языков программирования на трансляторы
Контрольные вопросы
Формальные языки и грамматики
Основные понятия и определения
Классификация грамматик и языков
Цепочки вывода
Сентенциальная форма грамматики
Левосторонний и правосторонний выводы
Дерево вывода
Преобразование грамматик
Контрольные вопросы
Регулярные грамматики и конечные автоматы
Контрольные вопросы
Принципы построения трансляторов
Схема работы компилятора
Многопроходные и однопроходные компиляторы
Системы программирования
Контрольные вопросы
Таблицы идентификаторов
Простейшие методы построения таблиц идентификаторов
Построение таблиц идентификаторов по методу бинарного дерева
Хэш-функции и хэш-адресация. Принципы работы хэш-функций
Построение таблиц идентификаторов на основе хэш-функции
Построение таблиц идентификаторов по методу цепочек
Выбор хэш-функции
Контрольные вопросы
Лексический анализатор
Разработка лексического анализатора
Генератор лексических анализаторов Flex
Контрольные вопросы
Синтаксический анализатор
Распознавание цепочек КС-языков
Виды распознавателей для КС-языков
Алгоритмы нисходящего синтаксического анализа
Алгоритмы восходящего синтаксического анализа
Программный инструментарий Bison
Контрольные вопросы
Список литературы
Приложение
1. Задания на лабораторные работы
Лабораторная работа №
1. Формальные языки, грамматики и их свойства
Лабораторная работа №
2. Регулярные грамматики и конечные автоматы
Лабораторная работа №
3. Таблицы идентификаторов
Лабораторная работа №
4. Лексический анализатор
Лабораторная работа №
5. Синтаксический анализатор
