НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
"УТВЕРЖДАЮ"
Декан АВТФ, профессор
____________
"___"___________2009г.
РАБОЧАЯ ПРОГРАММА
дисциплины "Системное программное обеспечение"
по направлению 230100 «Информатика и вычислительная техника»,
специальность 230101 - «Вычислительные машины, системы, комплексы и сети».
Факультет автоматики и вычислительной техники, заочное отделение
Курс - 4, семестр – 7.
Лекции - 12 часов (в т. ч. 2 часа установочных)
Лабораторные занятия - 12 часов
Самостоятельная работа - 120 часов
Всего - 144 часа
Контрольная работа, экзамен
Новосибирск, 2009 г.
Рабочая программа составлена на основании Гос. ВПО по направлениям 230100 - Информатика и вычислительная техника
Рабочая программа обсуждена на заседании кафедры вычислительной техники 31 августа 2009 г., протокол №7.
Программу составил: , к. т.н., доц. каф. ВТ
Заведующий кафедрой ВТ , д. т.н., профессор
Ответственный за основную
по направлению 230100 , зав. кафедрой ВТ,
д. т.н., профессор
1.Требования к курсу
Содержание раздела дисциплины соответствует государственному образовательному стандарту высшего профессионального образования по направлению 230100 «Информатика и вычислительная техника», специальность 230101 «Вычислительные машины, системы, комплексы и сети».
СД.05 | Системное программное обеспечение: | 170 |
Пользовательский интерфейс операционной среды; управление задачами; управление памятью; управление вводом-выводом; управление файлами; пример современной операционной системы; программирование в операционной среде; ассемблеры; мобильность программного обеспечения; макроязыки; трансляторы; формальные языки и грамматики, типы грамматик; вывод цепочек; конечный и магазинный автоматы, распознаватели и преобразователи, построение автомата по заданной грамматике; структура компиляторов и интерпретаторов, лексический, синтаксический и семантический анализаторы, генератор кода; распределение памяти, виды переменных; статическое и динамическое связывание; загрузчики; функции загрузчика; настраивающий и динамический загрузчики; подключение библиотек. |
2. Принципы построения курса
Входной уровень. Курс базируется на серьезной формальной основе, для изучения которой необходимы знания курса «Математическая логика и теория алгоритмов». Для понимания и реализации некоторых методов лексического и синтаксического, а также семантического анализа в целом необходимо иметь знания и навыки, получаемые в курсе «Программирование на языке высокого уровня».
Особенности курса. В связи с ограниченным объемом курса в его основе лежит прагматический подход к предметной области. Основное внимание уделяется содержательной интерпретации методов и средств построения трансляторов. Формальная сторона предмета несколько ограничена определениями и основными выводами из соответствующих математических моделей конечных автоматов и формальных грамматик. Основной упор сделан на умение применять полученные знания в прикладном программировании с использованием программных средств проектирования трансляторов. Курс разделен на 4 модуля.
Модуль 1. Общие принципы трансляции и ее фазы. На этом уровне у студента должны сформироваться представления об общей структуре языков программирования, лексической, синтаксической и семантической компонентах языка, их взаимосвязи. В результате приобретаются знания об этапах трансляции, формальных методах, используемых на каждом из них, вариантах сочетания компиляции и интерпретации. Формированию целостной картины способствует понятие «времени связывания», позволяющее с единых позиций рассматривать все языки программирования.
Модуль 2. Лексический анализ. Базируется на знании основных понятий, определений и выводов теории конечных автоматов. На этой основе изучаются принципы построения лексического анализатора с использованием содержательных методов построения конечных автоматов.
Модуль 3. Синтаксический анализ. Базируется на знании основных понятий, терминов и определений формальных грамматик, выводах теории и практике использования этого формализма для представления синтаксиса. Рассматриваются свойства грамматик и отношения между символами грамматик, используемые при создании синтаксических анализаторов (множества выбора, отношения предшествования и последования). Ввиду сложности самого аппарата формальных грамматик в дополнение к формальным методам применяются содержательные интерпретации и графические иллюстрации. Дается обзор различных процедурных и автоматных методов построения синтаксических анализаторов, а также алгоритмов их построения и функционирования.
Модуль 4. Семантический анализ. При изучении акцент делается на неформализуемости семантики и использовании для этих целей различных структур данных (со ссылками на курсы «Программирование» и «Структуры и алгоритмы обработки данных»). Рассматриваются несколько примеров элементов семантики из различных языков программирования и способы ее реализации.
3. Цели курса
Представления
В результате изучения дисциплины у студентов должны быть сформулированы представления о:
сущности трансляции, особенностях компиляции и интерпретации, фазах трансляции. времени связывания как основной характеристики процесса трансляции; структуре компилятора, связях лексической, синтаксической, семантической компонент и генератора кода (интерпретатора), способах взаимодействия компонент транслятора. особенностях семантического анализа, способах представления семантики (организации семантических таблиц), принципах компиляции и интерпретации выражений и управляющих структур программ.Знания
После изучения дисциплины студент должен знать:
определения и свойства конечных автоматов и их особенности их применения к лексическим анализаторам; методы проектирования лексических анализаторов на основе жесткой и автоматной логики; определения и свойства формальных грамматик, принципы синтаксического разбора; способы представления в формальных грамматиках таких элементов синтаксиса как альтернатива (выбор), перечисление, вложенность, ограничитель, разделитель и т. п.; свойства LL(1)-грамматик, применяемых в нисходящем синтаксическом анализе, принципы организации магазинных автоматов для нисходящих распознавателей, алгоритмы построения множеств выбирающих символов. принципы восходящего синтаксического анализа, сущность метода «свертка-перенос», алгоритмы построения таблиц конфигураций, управляющих таблиц и работы восходящего распознавателя. методы преобразования текста транслируемой программы в постфиксную запись; способы представления семантики в языках программированиях и используемые для этих целей структуры данных, методы преобразования постфиксной записи в последовательность тетрад.Умения и навыки
После изучения дисциплины студент должен приобрести умения и навыки:
выделения лексических, синтаксических и семантических ошибок в программах, написанных на распространенных языках программирования, и объяснения их причин; проектирования лексических анализаторов с жесткой логикой и на основе конечных автоматов для заданной лексики; построения формальной грамматики для заданного синтаксиса; построения дерева синтаксического разбора для заданной грамматики, определения общего вида цепочек, порождаемых грамматикой; проектирования синтаксических анализаторов на основе метода рекурсивного спуска; построения множеств выбирающих символов для нисходящих распознавателей; проектирования управляющих таблиц восходящих распознавателей для метода "свертка-перенос". включения элементов семантического анализа в синтаксические анализаторы.4. Структура и содержание курса
4.1. Структура курса
Номер и | Объем (в часах) | Номер удовлетво-ряемых требований ГОС | Результаты изучения | ||||
Лекции | Лаб. раб. | Сам. раб. | Представления | Знания | Умения и навыки | ||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Модуль 1. Общие принципы трансляции и ее фазы | |||||||
1 | 0 | 10 | 1,2,3 | 13 | |||
Модуль 2. Лексический анализ | |||||||
1 | 0 | 30 (к. р.) | 2,3 | 5,6 | 14 | ||
Модуль 3. Синтаксический анализ | |||||||
Формальные грамматики | 2 | 0 | 10 | 1,3,4 | 7,8 | 15,16 | |
Нисходящие распознаватели. Магазинные автоматы | 3 | 4 | 25 | 5 | 9,10 | 15,17, 18 | |
Восходящие распознаватели | 3 | 4 | 25 | 6 | 11 | 15,19 | |
Модуль 4. Семантический анализ | |||||||
2 | 4 | 20 | 7 | 4 | 12 | 20 |
4.2. Содержание курса
Лекции (12 часов)
Общие принципы трансляции и ее этапы (1 час, установочная лекция). Формальные языки и языки программирования, основные понятия, связь с задачами автоматического анализа и эквивалентного преобразования программ с одного языка на другой. Системы правил и метаязыки для определения лексики, синтаксиса и семантики формальных языков. Этапы процесса трансляции, промежуточные формы представления программы.
Лексический анализ (1 час, установочная лекция). Сущность лексического анализа (ЛА).
Процедурная и автоматная реализации ЛА. Описание лексики языка с помощью регулярных выражений. Алгоритм преобразования регулярного выражения в граф состояний и переходов недетерминированного конечного автомата без памяти. Типы недетерминированности и методы их устранения. Алгоритм преобразования недетерминированного конечного автомата в детерминированный лексический акцептор. Оптимизация управляющей таблицы лексического акцептора. Алгоритм функционирования автоматного ЛА.
Синтаксический анализ (8 часов).
Формальные грамматики. Основные понятия и классификация формальных грамматик. Алфавиты терминальных и нетерминальных символов. Цепочки символов, порождающие правила, понятие непосредственного вывода. Свойства грамматик. Свойства нетерминальных символов грамматики. Аннулируемые, недостижимые и бесплодные нетерминалы. Отношения между символами грамматики. Понятие символа-предшественника. Алгоритм определения множеств предшественников для символа грамматики. Понятие символа-последователя. Алгоритм определения множеств непосредственных последователей для символов грамматики. Алгоритм определения множеств символов, замыкающих цепочки, выводимые из символов грамматики. Алгоритм определения отношения «символ – последователь» для всех символов грамматики. Эквивалентные преобразования грамматик. Понятие дерева грамматического разбора и его связь с задачами синтаксического анализа. Нисходящие и восходящие группы методов синтаксического анализа, их основные идеи. Понятие конечного автомата со стековой памятью в качестве основы синтаксического акцептора. Нисходящие методы синтаксического анализа. Основной алгоритм нисходящего синтаксического анализа, критерии выбора грамматики для реализации этого алгоритма. Множества выбора для правила грамматики. Понятие и определение LL(1)-грамматики. Алгоритм определения принадлежности грамматики к классу LL(1). Алгоритмы преобразования LL(1)-грамматики в управляющие таблицы автоматов с одним состоянием и с несколькими состояниями. Алгоритмы функционирования автоматных синтаксических акцепторов (распознавателей). Метод преобразования LL(1)-грамматики в программу, реализующую синтаксический анализ рекурсивным спуском. Восходящие методы синтаксического анализа. Восходящий акцептор в виде конечного автомата со стековой памятью и единственным рабочим состоянием. Операции сдвига и свёртки, состояние стека автомата до и после их выполнения. Понятия конфликтов «свертка/свертка» и «сдвиг/свертка». Введение нескольких рабочих состояний и стека номеров состояний для устранения конфликтов. Алгоритмы выполнения операций сдвига и свёртки для такого автомата. Возможность ликвидации стека символов. Задача определения множества состояний восходящего акцептора. Понятие конфигурации, связь между подмножествами конфигураций и состоянием автомата. Алгоритм построения подмножеств эквивалентных конфигураций. Разметка грамматики. Структура управляющей таблицы восходящего акцептора. Первый этап заполнения управляющей таблицы: занесение знаков операции сдвига. Второй этап: формирование знаков операции свёртки. Понятие xLR(k)-грамматик. Случай LR(0) – отсутствие конфликтов при построении управляющей таблицы. Случай SLR(1)-грамматик – разрешение конфликтов методом использования полных множеств символов-последователей для нетерминалов из правой части правила, по которому осуществляется свёртка. Случай LR(1)-грамматик – понятие правого контекста и расширенной конфигурации. Их связь с полными множествами последователей и предысторией восходящего анализа. Правила определения правого контекста для расширенных конфигураций. Метод использования правого контекста для предотвращения конфликтов при формировании управляющей таблицы. Случай LALR(1)-грамматики и понятие объединенной конфигурации. Алгоритм функционирования восходящего акцептора. Обработка ошибок при синтаксическом анализе, методы нейтрализации ошибок.Семантический анализ и генерация кода (2 часа). Понятие постфиксной формы записи, её связь с деревом грамматического разбора. Понятие грамматики действий (синтаксически управляемой или СУ-схемы), как расширения формальной грамматики, позволяющей определять операции синтаксического анализатора по формированию постфиксной записи. Задача генерации уникальных символов для преобразования в постфиксную запись структурированных управляющих конструкций языка. Операции, операнды и результаты. Виды переменных, наименования и значения, типы значений, классы памяти, области действия и зоны видимости, их связь с понятием блока. Статическое и динамическое связывание. Неименованные промежуточные результаты вычислений. Задача преобразования постфиксной записи в последовательность тетрад. Состав и структура таблицы идентификаторов, операции над таблицей при обработке входа в блок и выхода из блока. Задача проверки правильности употребления наименований объектов (операций, операндов и результата) в последовательности тетрад. Обработка семантических ошибок.
Самостоятельная работа (120 часов)
Наименование раздела и его содержание для самостоятельного изучения | Часов | Формы работы |
Общие принципы трансляции и ее этапы. Понятие времени связывания. Сравнительная характеристика языков программирования с точки зрения времени связывания. | 10 | Изучение литературы. Консультации преподавателя. |
Лексический анализ. Конечные автоматы без памяти. Управляющие таблицы КА и алгоритмы их функционирования. | 30 | Изучение литературы. Консультации преподавателя. Выполнение контрольной работы |
Формальные грамматики. Свойства символов, отношения между символами, множества предшественников, последователей и выбора правил, алгоритмы их построения. | 10 | Изучение литературы. Консультации преподавателя. Работа с учебным пакетом автоматизации проектирования трансляторов Вебтранслаб. |
Нисходящие синтаксические анализаторы на основе магазинных автоматов. Построение множества выбора для LL(1)-грамматики. Алгоритм функционирования автоматных нисходящих распознавателей. Процедурная реализация рекурсивного спуска. | 25 | Изучение литературы. Консультации преподавателя. Работа с учебным пакетом автоматизации проектирования трансляторов Вебтранслаб, изучение прилагаемых к нему примеров LL(1)-грамматик. |
Восходящие распознаватели. Алгоритм преобразования формальной грамматики в управляющую таблицу. Конфликты «свертка/свертка» и «сдвиг/свертка», их обнаружение и устранение/предотвращение. | 25 | Изучение литературы. Консультации преподавателя. Работа с учебным пакетом автоматизации проектирования трансляторов Вебтранслаб, изучение прилагаемых к нему примеров SLR(1)- и LALR(1)-грамматик. |
Семантический анализ и генерация кода. Постфиксная запись (ПФЗ), ее получение. Грамматика действий. Преобразование ПФЗ в последовательность тетрад. Проверка правильности сочетания типов операндов со знаком операции в каждой тетераде как основная задача семантического анализа. | 20 | Изучение литературы, консультации преподавателя, подготовка к экзамену |
Контрольная работа
Изучение методов лексического анализа. С использованием материалов лекций, учебного пакета автоматизации проектирования трансляторов Вебтранслаб и задания на контрольную работу из [1] программируются и отлаживаются два варианта лексического анализатора: на основе «жесткой логики» и в форме конечного автомата.
Лабораторные занятия (12 часов)
Методы синтаксического анализа. Нисходящий синтаксический анализ. Разрабатывается формальная грамматика класса LL(1), на основе которой строится программа нисходящего распознавания. Проверяется ее работоспособность, устраняются конфликты выбора (4 часа). Методы синтаксического анализа. Восходящий синтаксический анализ.. Разрабатывается формальная грамматика класса не выше LALR(1), на основе которой строится программа восходящего распознавания. Проверяется ее работоспособность, устраняются конфликты «сдвиг/свертка» и «свертка/свертка». (4 часа). Методы семантического анализа. Одна из грамматик (любая), разработанных на лабораторной работе №1 или №2, преобразуется в грамматику действий для формирования постфиксной записи анализируемой программы и последующего преобразования ее в последовательность тетрад. (4 часа).5. Учебная деятельность
На основании материалов установочных лекций, электронного курса [1], сайта дисциплины «Теория языков программирования и методы трансляции» для студентов очного отделения (http://vt. cs. nstu. ru/~malyavko) и рекомендуемой литературы студент в течение семестра изучает формальные системы (КА и ФГ) и методы и алгоритмы лексического, синтаксического и семантического анализа. Для выполнения контрольной работы он самостоятельно полностью изучает материал модуля 2. Материал модулей 3 и 4 закрепляется во время экзаменационной сессии (лекционные и лабораторные занятия). Экзамен включает два теоретических вопроса.6. Правила аттестации студентов
Предусмотрен традиционный принцип аттестации: выполнение и защита контрольной работы, работа с тестовыми грамматиками на лабораторных занятиях, консультации преподавателя и сдача итогового экзамена.
7. Список литературы
http://courses. edu. nstu. ru/courses. php? show=155&curs=1615 - учебные материалы по дисциплине «Системное программное обеспечение. Методы трансляции». омпиляторы: принципы, технологии и инструменты. – М.: Изд. дом «Вильямс», 2001. Молчанов программное обеспечение: Учебник для вузов. СПб: Питер, 2003, 396 с., илл. Малявко формальных языков: Учеб. пособие. – Новосибирск: Изд-во НГТУ, 2001. – Ч.1 Малявко формальных языков: Учеб. пособие. – Новосибирск: Изд-во НГТУ, 2002. – Ч.2. Малявко формальных языков: Учеб. Пособие. – Новосибирск: Изд-во НГТУ, 2004. – Ч. 3. зыки программирования: реализация и разработка. – СПб.: Питер, 2001. роектирование и конструирование компиляторов. – М.: Финансы и статистика, 1984. еоретические основы проектирования компиляторов. – М., Мир, 1979. Рейуорд-ж. Теория формальных языков. Вводный курс. – М.: Радио и связь, 1988. онструирование компиляторов для цифровых вычислительных машин. – М., Мир, 19858. Контролирующие материалы к аттестации студентов
При защите контрольной работы и на лабораторных занятиях используются тестовые задания – простейшие варианты лексики и синтаксиса (тестовые грамматики), для которых студент должен провести полный цикл проектирования распознавателя с использованием учебного пакета программ автоматизации проектирования трансляторов. Выборочные примеры тестовых заданий:
Лексический анализ
Разработать конечный автомат, распознающий лексику следующего вида:
00111100 – цепочка, содержащая четное число подряд идущий единиц и нулей +01 | +10 | + | 11010010 – одиночный символ +, после него лексема может содержать 01 или 10, любое другое сочетание (11 или 00) считается началом другой лексемы (подсказка: требуется реализовать возврат 2-х символов). aaaaaaabc | aaaaa | bbbbbca | bbbbbb | cccccab | cccccc – повторяющаяся цепочка из 2 и более символов a, b или с, имеющая (или не имеющая) соответствующий суффикс.Нисходящий синтаксический анализ
Для заданных грамматик определить вид порождаемых цепочек, построить нисходящий распознаватель с определением множеств выбирающих символов и продемонстрировать принципы его работы на заданном или предложенном примере.
1) Z:U U:EU U: E:aSb S:aSb S:
2) Z:UM M:,UM M: U:SN N:SN N: S:a S:b S:c
3) Z:N N:UM M:,UM M: U:aSK S:aS S: K:[N] K:
4) U:ST T:,ST T: S:BA B:*B B: A:aA A:
Восходящий синтаксический анализ
Для заданных грамматик определить вид порождаемых цепочек и построить восходящий распознаватель. Продемонстрировать принципы его работы на заданном или предложенном примере.
1) Z:E E:E, T E:T T:a T:b T:Ta T:Tb
2) Z:U U:UE U:E E:Abc E:bc A:Aa A:a
3) Z:U U:UE U:E E:ab E:aEb
4) Z:E E:E, T E:T T:S[E] T:S S:Sa S:a
Экзаменационные вопросы
Сущность трансляции. Компиляция и интерпретация. Этапы компиляции. Лексический, синтаксический и семантический анализ, генерация кода, оптимизация. Компоновка. Загрузка. Исполнение. Понятие связывания. Моменты времени связывания. Пример связывания различных свойств переменной. Лексика. Сущность лексического анализа (ЛА). Лексические анализаторы. ЛА с жесткой и автоматной логикой. Конечный автомат. Определение. ЛА на основе КА. Диаграмма состояний. Регулярные выражения (РВ). Преобразование РВ в ЛА с использованием КА. Формальные грамматики (ФГ). Основные понятия и определения. Классификация ФГ. Понятие дерева синтаксического разбора. Способы представления в ФГ элементов синтаксиса: выбора, альтернативы, вложенности, приоритетов. Отношения между символами ФГ. Множества предшественников символов грамматики и алгоритм их построения. Множества последователей символов грамматики и алгоритм их построения. Множества выбора правил грамматики и алгоритм их построения. Нисходящий разбор. Принципы нисходящего разбора и его рекурсивный характер. Нисходящий разбор с возвратами - рекурсивный поиск по принципу полного перебора. LL(1)-грамматики. Понятие выбирающего символа. Построение множеств выбирающих символов. Алгоритм работы распознавателя. Рекурсивный спуск. Принципы построения распознавателей. Пример для грамматики арифметических выражений и ее расширения. Автоматная реализация нисходящего синтаксического анализа Автомат нисходящего анализа с одним состоянием. Автомат нисходящего анализа с несколькими состояниями. Восходящие методы разбора. Операции сдвига и свертки. Построение таблицы конфигураций. Построение управляющей таблицы восходящего синтаксического анализатора. Обнаружение и устранение конфликтов «сдвиг-свертка» и «свертка-свертка». Постфиксная запись и алгоритм ее формирования. Последовательность тетрад. Преобразование ПФЗ в последовательность тетрад. Семантический анализ. Семантика языка. Таблицы имен. Пример семантических таблиц для подмножества типов данных в Си. Семантические ошибки. Понятие L-value. Структура компилятора. Связь лексической, синтаксической, семантической компонент и генератора кода (интерпретатора). Способы взаимодействия компонент транслятора. Интерпретация выражений. Пример интерпретатора арифметических вычислений на основе анализатора методом рекурсивного спуска. Интерпретация управляющих структур программы. Компиляция выражений. Использование стековой архитектуры для генерации кода при восходящем и нисходящем разборе выражения. Компиляция управляющих структур программы.Варианты заданий лексики для контрольной работы
идентификаторы вида s…s (sinus, sirius, secans); идентификаторы, заканчивающиеся на ex; десятичные константы; восьмеричные константы; шестнадцатеричные константы; вещественные константы; “диапазонные” константы вида +-126 комментарии вида =!…!= комментарии вида <>…<>, операции <,<<,>,>>; операции =,==,!=,++, +=,+ ; “смайлики” вида “:-)” , “:-(”, “:-)) ”, “:-((” (или другие, по выбору).Каждое задание формируется из 3-4 пунктов перечисленного списка.
