Основными объектами изучения научного направления "Лингвистическое и программное обеспечение САПР" являются различные программы, представимые в памяти компьютера, языки для реализации интерфейса и написания программ. Методы построения подобных программ в различных предметных областях основаны на моделях конечных автоматов и теории формальных грамматик. Широкое использование таких моделей в теоретических исследованиях и разработке систем, используемых на практике, позволяет рассматривать их как одну из основ образования по направлению "Лингвистическое и программное обеспечение САПР". Главным назначением дисциплины "Формальные языки, грамматики и автоматы" является ознакомление студентов, обучающихся по направлению "Лингвистическое и программное обеспечение САПР" с основами теории, методами и приемами практического использования аппарата формальных грамматик и конечных автоматов.
Глава 1. Формальные языки, грамматики и автоматы
1.1. Трансляторы, интерпретаторы и компиляторы
1.2. Стадии работы компилятора
1.3. Определение формальной грамматики и языка
1.4. Типы формальных языков и грамматик. Классификация по Хомскому
1.5. Вывод в КС-грамматиках и правила построения дерева вывода
1.6. Синтаксический разбор
1.7. Левый и правый выводы
1.8. Неоднозначные и эквивалентные грамматики
1.9. Способы задания схем грамматик. Форма Наура-Бэкуса
1.10. Итерационная форма
1.11. Синтаксические диаграммы
1.12. Приведенные грамматики
1.13. Непроизводящие символы
1.14. Недостижимые символы
1.15. Бесполезные символы
1.16. Исключение леворекурсивных правил
1.17. Исключение цепных правил
1.18. Преобразование неукорачивающих грамматик
1.19. Магазинные автоматы
1.20. Представление арифметических, алгебраических и логических выражений в виде польской записи
Приложение 1.
Список литературы
Глава 2. Генератор лексических анализаторов LEX
2.1. Введение
2.2. Регулярные выражения
2.3. Элементы регулярных выражений
2.4. Конкатенация литералов
2.5. Экранирование метасимволов
2.6. Коды символов и литеральные константы
2.7. Якорные метасимволы
2.8. Выбор альтернатив
2.9. Классы символов
2.10. Квантификаторы
2.11. Обработка контекста
2.12. Группировка и ограничение регулярных фрагментов
2.13. Структурный анализ регулярных выражений
2.14. Нерегулярные множества
2.15. Конечные автоматы регулярных выражений
2.16. Структура файла спецификации лексем
2.17. Секция описаний
2.18. Спецификация правил
2.19. Элементарные действия правил
2.20. Блоки действий
2.21. Встроенные переменные действий
2.22. Стандартные функции действий
2.23. Операторы действий
2.24. Неоднозначные правила
2.25. Функциональная реализация правил
2.26. Секция подпрограмм
2.27. Обработка спецификаций лексем
2.28. Пример разработки лексического анализатора
2.29. Индивидуальные задания к лабораторной работе по теме "Автоматизированное проектирование лексических анализаторов с использованием генератора LEX"
2.30. Варианты контрольных работ по теме "Автоматизация проектирования лексических анализаторов c использованием генератора LEX"
Приложение 2.
Список литературы
Глава 3. Генератор синтаксических анализаторов YACC
3.1. Введение
3.2. Спецификации
3.3. Действия
3.4. Лексический анализ
3.5. Как работает построитель
3.6. Неоднозначности и конфликты
3.7. Предшествование
3.8. Обработка ошибок
3.9. Среда выполнения YACC
3.10. Подготовка спецификаций
3.11. Простой настольный калькулятор
3.12. Описание входного синтаксиса
3.13. Пример использования
3.14. Устаревшие конструкции
3.15. Задания к лабораторной работе по теме "Автоматизированное проектирование синтаксических анализаторов с использованием генератора YACC"
3.16. Варианты контрольных работ по теме "Автоматизированное проектирование синтаксических анализаторов с использованием генератора YACC"
3.17. Задания к лабораторной работе по теме "Автоматизированное проектирование трансляторов с использованием генераторов LEX и YACC"
Приложение 3.
Список литературы