Полоцкий государственный университет

Полоцкий
государственный
университет

УМК Системное программное обеспечение. Синтаксические анализаторы

Системное программное обеспечение. Синтаксические анализаторы: Учеб.-метод. комплекс для студ. спец. 1-40 02 01 «Вычислительные системы и сети» и 1-40 01 01 «Программное обеспечение информационных технологий» / Сост. и общ. ред. Д.О. Глухова. – Новополоцк: ПГУ, 2004. – 208 с.
Предпринята попытка решить весь комплекс задач по обучению и подготовке современного специалиста в области системного программного обеспечения при разработке компиляторов, трансляторов и интерпретаторов формальных языков, а также конструировании языков как таковых. При составлении отправной точкой являлись дидактические и познавательные цели и задачи обучения на современном этапе.

Глухов Дмитрий Олегович

Дмитрий
Олегович
ГЛУХОВ

проректор по информатизации, кандидат технических наук, доцент

В 1995г. окончил Полоцкий государственный университет, квалификация - инженер-конструктор-технолог РЭС. Окончил очную аспирантуру по специальности «Управление техническими системами» и в 1999г. защитил кандидатскую диссертацию на тему «Разработка и исследование методов повышения качества нечеткого управления сложными динамическими объектами». Читает курсы «Объектно-ориентированное программирование» и «Системное программное обеспечение».

СОДЕРЖАНИЕ

Об УМК

1. Рабочая программа

2. Модуль Вводный

3. Модуль Формальные грамматики и языки
3.1. Языки и цепочки символов. Способы задания языков
3.1.1. Цепочки символов. Операции над цепочками символов
3.1.2. Понятие языка. Формальное определение языка
3.1.3. Способы задания языков
3.1.4. Синтаксис и семантика языка
3.2. Определение грамматики
3.2.1. Особенности языков программирования
3.2.2. Определение грамматики. Форма Бэкуса–Наура
3.2.3. Принцип рекурсии в правилах грамматики
3.2.4. Другие способы задания грамматик
3.3. Классификация языков и грамматик
3.3.1. Классификация грамматик
3.3.2. Классификация языков
3.4. Контроль

4. Модуль Распознаватели, механизм вывода цепочек символов
4.1. Цепочки вывода. Сентенциальная форма
4.1.1. Сентенциальная форма грамматики. Язык, заданный грамматикой
4.1.2. Левосторонний и правосторонний выводы
4.1.3. Однозначные и неоднозначные грамматики
4.1.4. Эквивалентность и преобразование грамматик
4.2. Распознаватели. Задача разбора
4.2.1. Общая схема распознавателя
4.2.2. Виды распознавателей
4.2.3. Классификация распознавателей по типам языков
4.3. Контроль

5. Модуль Регулярные грамматики и языки
5.1. Регулярные языки и грамматики
5.2. Леволинейные и праволинейные грамматики. Автоматные грамматики
5.3. Алгоритм преобразования регулярной грамматики к автоматному виду
5.4. Конечные автоматы
5.4.1. Определение конечного автомата
5.4.2. Детерминированные и недетерминированные конечные автоматы
5.4.3. Преобразование конечного автомата к детерминированному виду
5.5. Контроль

6. Модуль Контекстно-свободные грамматики и языки
6.1. Контекстно-свободные языки
6.1.1. Распознаватели КС-языков. Автоматы с магазинной памятью. Определение МП-автомата
6.2. Классы КС-языков и грамматик. Класс LL(k)-грамматик
6.3. Принципы построения распознавателей для LL(k)-грамматик
6.4. Левая факторизация
6.5. Удаление левой рекурсии
6.6. Алгоритм разбора для LL(1)-грамматик
6.7. Алгоритм построения множества FIRST(1,A)
6.8. Алгоритм построения множества FOLLOW(1,A
6.9. Восходящие распознаватели КС-языков без возвратов
6.9.1. Определение LR(k)-грамматики
6.10. Принципы построения распознавателей для LR(k)-грамматик
6.10.1. Грамматики простого предшествования
6.11. Распознаватели для LR(0) и LR(1)-грамматик
6.11.1. Распознаватель для LR(0)-грамматики
6.11.2. Распознаватель для LR(1) грамматики
6.12. Контроль

7. Модуль Инструментальные средства для построения трансляторов
7.1. Инструментальные средства для построения компиляторов
7.1.1. Построитель лексических анализаторов Lex
7.1.2. Yacc
7.2. Контроль

8. Модуль Особенности программирования трансляторов
8.1. Использование значений произвольных типов, алгоритм разбора
8.1.1. Алгоритм синтаксического разбора
8.1.2. Семантический стек
8.2. Неоднозначности и конфликты
8.3. Старшинство операций
8.4. Дополнительные возможности программ Yacc и Lex
8.4.1. Обработка ошибок
8.5. Совместное использование Lex и Yacc
8.5.1. Кодировка лексем и интерфейс
8.5.2. Сборка yacc-программ
8.6. Советы по подготовке спецификаций
8.6.1. Стиль
8.6.2. Использование левой рекурсии
8.6.3. Уловки анализа лексики
8.6.4. Входной синтаксис Yacc'а
8.7. Контроль

9. Модуль Заключение

10. Дополнительная информация. Примеры
10.1. Функции работы со строками языка С/С++ для С, MS Visual C++, Borland C++ Builder
10.2. Функции работы с потоками языка С / С++
10.3. Функции работы с потоками в Borland C++ Builder
10.4. Пример простейшего интерпретатора формул
10.5. Простой пример
10.6. Более сложный пример
10.7. Генераторы лексических и синтаксических анализаторов
10.8. Генераторы лексических и синтаксических анализаторов на Java
10.9. Пакеты для разработки компиляторов

Список сокращений

Учебно-методическая карта дисциплины

Вопросы для зачета

Методические указания к лабораторным работам

Организация рейтингового контроля

Литература