МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

"УТВЕРЖДАЮ"

Декан АВТФ, профессор

__________

"___"___________2006г.

РАБОЧАЯ ПРОГРАММА

дисциплины "Теория языков программирования и методы трансляции" по направлению 230100 «Информатика и вычислительная техника», специальность 230105 - «Программное обеспечение вычислительной техники и автоматизированных систем». Факультет автоматики и вычислительной техники, заочное отделение

Кафедра вычислительной техники

Курс - 3, семестр – 6.

Лекции - 8 часов (в т. ч. 4 часа установочных)

Практические занятия - 6 часов

Самостоятельная работа - 126 часов

Всего - 140 часов

Контрольная работа, экзамен

Новосибирск, 2006 г.

Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования (ГОСВПО) по направлению 230100 (654600) – «Информатика и вычислительная техника».

Регистрационный номер и дата утверждения ГОСВПО по направлению 230100 (654600) – «Информатика и вычислительная техника»: 35 тех/бак, 13 марта 2000 г. (224 тех/дс, 27 марта 2000 г.)

Индекс дисциплины в ГОСВПО ‑ СД.00 (СД.04)

Компонент – национально-региональный (вузовский)

Цикл СД – Специальные дисциплины

Учебный план по направлению 230100 – «Информатика и вычислительная техника», специализация 230105 – «Программное обеспечение вычислительной техники и автоматизированных систем» (набор 2001 г. и последующие)

Рабочая программа обсуждена на заседании кафедры вычислительной техники 31 августа 2006 г., протокол №7.

Программу составил: , к. т.н., доц. каф. ВТ

Заведующий кафедрой ВТ , д. т.н., профессор

Ответственный за основную

образовательную программу

по направлению 230100 , декан АВТФ,

зав. кафедрой ВТ, д. т.н., профессор

2. Принципы построения курса

Входной уровень. Курс базируется на серьезной формальной основе, для изучения которой необходимы знания курса «Математическая логика и теория алгоритмов». Для понимания и реализации некоторых методов лексического и синтаксического, а также семантического анализа в целом необходимо иметь знания и навыки, получаемые в курсе «Программирование на языке высокого уровня».

Особенности курса. В связи с ограниченным объемом курса в его основе лежит прагматический подход к предметной области. Основное внимание уделяется содержательной интерпретации методов и средств построения трансляторов. Формальная сторона предмета несколько ограничена определениями и основными выводами из соответствующих математических моделей конечных автоматов и формальных грамматик. Основной упор сделан на умение применять полученные знания в прикладном программировании без привлечения программных средств проектирования трансляторов. Курс разделен на 4 модуля.

Модуль 1. Общие принципы трансляции и ее фазы. На этом уровне у студента должны сформироваться представления об общей структуре языков программирования, лексической, синтаксической и семантической компонентах языка, их взаимосвязи. В результате приобретаются знания об этапах трансляции, формальных методах, используемых на каждом из них, вариантах сочетания компиляции и интерпретации. Формированию целостной картины способствует понятие «времени связывания», позволяющее с единых позиций рассматривать все языки программирования.

Модуль 2. Лексический анализ. Базируется на знании основных понятий, определений и выводов теории конечных автоматов. На этой основе изучаются принципы построения лексического анализатора с использованием содержательных методов построения конечных автоматов.

Модуль 3. Синтаксический анализ. Базируется на знании основных понятий, терминов и определений формальных грамматик, выводах теории и практике использования этого формализма для представления синтаксиса. Ввиду сложности самого аппарата формальных грамматик в дополнение н формальным методам применяются содержательные интерпретации и графические иллюстрации. Дается обзор трех различных методов построения распознавателей, а также алгоритмы получения основных соотношений между символами, используемыми в управляющих структурах (множества выбора, отношения предшествования).

Модуль 4. Семантический анализ. При изучении акцент делается на неформализуемости семантики и использовании для этих целей различных структур данных (со ссылками на курсы «Программирование» и «Структуры и алгоритмы обработки данных»). Рассматриваются несколько примеров элементов семантики из различных языков программирования и способы ее реализации. В расчетно-графической работе студенты должны реализовать семантическую компоненту, встроенную в синтаксический распознаватель, основанный на методе рекурсивного спуска.

3. Цели курса

Представления

В результате изучения дисциплины у студентов должны быть сформулированы представления о:

1.  сущности трансляции, особенностях компиляции и интерпретации, фазах трансляции.

2.  времени связывания как основной характеристики процесса трансляции;

3.  структуре компилятора, связях лексической, синтаксической, семантической компонент и генератора кода (интерпретатора), способах взаимодействия компонент транслятора.

4.  особенностях семантического анализа, способах представления семантики (организации семантических таблиц), принципах компиляции и интерпретации выражений и управляющих структур программ.

Знания

После изучения дисциплины студент должен знать:

5.  определения и свойства конечных автоматов и их особенности их применения к лексическим анализаторам;

6.  методы проектирования лексических анализаторов на основе жесткой и автоматной логики.

7.  определения и свойства формальных грамматик, принципы синтаксического разбора;

8.  способы представления в формальных грамматиках таких элементов синтаксиса как альтернатива (выбор), перечисление, вложенность, ограничитель, разделитель и т. п.

9.  методы проектирования синтаксических анализаторов на основе жесткой логики (рекурсивный спуск).

10.  свойства LL(1)-грамматик, применяемых в нисходящем синтаксическом анализе, принципы организации магазинных автоматов для нисходящих распознавателей, алгоритмы построения множеств выбирающих символов.

11.  принципы восходящего синтаксического анализа, сущность метода «свертка-перенос», алгоритмы построения отношений предшествования и работы восходящего распознавателя.

12.  способы представления семантики в языках программированиях и используемые для этих целей структуры данных.

Умения и навыки

После изучения дисциплины студент должен приобрести умения и навыки:

13.  выделения лексических, синтаксических и семантических ошибок в программах, написанных на распространенных языках программирования, и объяснения их причин;

14.  проектирования лексических анализаторов с жесткой логикой и на основе конечных автоматов для заданной лексики;

15.  построения формальной грамматики для заданного синтаксиса;

16.  построения дерева синтаксического разбора для заданной грамматики, определения общего вида цепочек, порождаемых грамматикой;

17.  проектирования синтаксических анализаторов на основе метода рекурсивного спуска;

18.  построения множеств выбирающих символов для нисходящих распознавателей;

19.  проектирования управляющих таблиц восходящих распознавателей для метода "свертка-перенос".

20.  включения элементов семантического анализа в синтаксические анализаторы на основе метода рекурсивного спуска.

Практические занятия (6 часов)

1.  Свойства формальных грамматик. Представление элементов синтаксиса реальных языков программирования средствами ФГ. Построение множеств FIRST, LAST, FOLLOW для реальных и тестовых грамматик (2 часа).

2.  Нисходящий СА с использованием магазинных автоматов. Особенности грамматик для нисходящего распознавания, примеры реализации элементов синтаксиса и построения множеств выбора реальных языков программирования. Построение множеств выбора и анализ алгоритма распознавания на тестовых грамматиках. Устранение конфликтов выбора (2 часа).

3.  Восходящий синтаксический анализ методом «свертка-перенос». Особенности грамматик для нисходящего распознавания, примеры реализации элементов синтаксиса и построения отношений предшествования в реальных языках программирования. Устранение конфликтов «свертка-перенос». Построение распознавателя для тестовых грамматик и анализ алгоритма распознавания (2 часа).

5. Учебная деятельность

На основании материала установочных лекций, краткого электронного курса лекций [1] и рекомендуемой литературы студент в течение семестра изучает формальные системы (КА и ФГ) методы и алгоритмы ЛА и СА. При этом он пользуется контрольными примерами, программными распознавателями и тестовыми грамматиками из размещенного в [1] архива. Для выполнения контрольной работы он полностью изучает материал модуля 2. Материал модуля 3 закрепляется во время экзаменационной сессии (лекционные и практические занятия), модуль 4 изучается самостоятельно. Экзамен включает теоретический вопрос и задачу, аналогичную решаемым на практических занятиях.

6. Правила аттестации студентов

Предусмотрен традиционный принцип аттестации: выполнение лабораторных работ с различными вариантами заданий, оформление по ним отчетов и защита на тестовых примерах лексики и грамматик, а также выполнение контрольной работы. Экзаменационный билет включает в себя экзаменационный вопрос и тестовое задание (относительно простую задачу по лексическому или синтаксическому анализу). Уровень требований на экзамене следующий:

-  «отлично» - развернутый ответ на экзаменационный вопрос, решение тестового задания, ответы на дополнительные вопросы на предмет знания основных понятий, терминов определений, свойств и выводов в предметной области;

-  «хорошо» - полный ответ на экзаменационный вопрос, решение тестового задания с отдельными ошибками, неправильные ответы на дополнительные вопросы;

-  «удовлетворительно» - частичный ответ на экзаменационный вопрос, наличие грубых ошибок в решении тестового задания, незнание основных терминов и определений;

-  «неудовлетворительно» - отсутствие решения тестового задания, неудовлетворительный ответ на экзаменационный вопрос, незнание основных терминов и определений.

7. Список литературы

Основная литература

1.  Молчанов программное обеспечение: Учебник для вузов. СПб: Питер, 2003, 396 с., илл.

2.  http://ermak. cs. nstu. ru/trans - учебные материалы по дисциплине «Теория языков программирования и методы трансляции».

3.  Малявко формальных языков: Учеб. пособие. – Новосибирск: Изд-во НГТУ, 2002. – Ч.1, Ч2.

4.  Малявко формальных языков: Учеб. Пособие. – Новосибирск: Изд-во НГТУ, 2004. – Ч. 3.

Дополнительная литература

5.  Карпов и технология программирования. Основы построения трансляторов. СПб: БХВ-Петербург, 2005, 272 с.

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

7.  Компиляторы: принципы, технологии и инструменты. – М.: Изд. дом «Вильямс», 2001.

8.  Языки программирования: реализация и разработка. – СПб.: Питер, 2001.

9.  Рейуорд- Дж. Теория формальных языков. Вводный курс. – М.: Радио и связь, 1988.

10.  Проектирование и конструирование компиляторов. – М.: Финансы и статистика, 1984.

11.  Теоретические основы проектирования компиляторов. – М., Мир, 1979.

12.  Конструирование компиляторов для цифровых вычислительных машин. – М., Мир, 1985

8. Контролирующие материалы к аттестации студентов

При защите лабораторных работ и в экзаменационных билетах используются тестовые задания – простейшие варианты лексики и синтаксиса, для которых студент должен «вручную» провести полный цикл проектирования распознавателя. Аналогичные задания используются при проведении экзамена.

Лексический анализ

Разработать конечный автомат, распознающий лексику следующего вида:

1.  00111100 – цепочка, содержащая четное число подряд идущий единиц и нулей

2.  +01 | +10 | + | 11010010 – одиночный +, после + лексема может содержать 01 или 10, любое другое сочетание (11 или 00) считается началом другой лексемы (подсказка: возврат 2 символов).

3.  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

Экзаменационные вопросы

1.  Сущность трансляции. Компиляция и интерпретация. Фазы компиляции (на примере Си). Препроцессор. Лексический, синтаксический и семантический анализ, генерация кода, оптимизация. Связывание (компоновка). Примеры лексики, синтаксиса и семантики языка, соответствующих ошибок.

2.  Понятие связывания. Время связывания. Пример связывания различных свойств переменной. Термины статический и динамический.

3.  Лексика. Сущность лексического анализа (ЛА). Лексические анализаторы. ЛА с жесткой и автоматной логикой.

4.  Конечный автомат. Определение. ЛА на основе КА. Диаграмма состояний. Последовательность построения ЛА с использованием КА.

5.  Формальный грамматики (ФГ). Основные понятия и определения. Классификация ФГ. Понятие дерева синтаксического разбора.

6.  Пример ФГ для основных элементов синтаксиса языка Си: выражения, операторы, определения. Способы представления в ФГ элементов синтаксиса: выбора, альтернативы, вложенности, приоритетов.

7.  Отношения между символами ФГ. Множества FIRST, LAST, FOLLOW и алгоритмы их построения.

8.  Нисходящий разбор. Принципы нисходящего разбора и его рекурсивный характер. Нисходящий разбор с возвратами - рекурсивный поиск по принципу полного перебора.

9.  Рекурсивный спуск. Принципы построения распознавателей. Пример для грамматики арифметических выражений и ее расширения.

10.  Магазинный автомат (МА). S-грамматика и анализаторы на ее основе с использованием МА. Пример.

11.  Q и LL(1)-грамматики. Понятие выбирающего символа. Построение множеств выбирающих символов. Алгоритм работы распознавателя.

12.  Восходящие методы разбора. Свертка-перенос.

13.  Семантический анализ. Семантика языка. Таблицы имен. Пример семантических таблиц для подмножества типов данных в Си.

14.  Семантические ошибки. Понятие L-value.

15.  Структура компилятора. Связь лексической, синтаксической, семантической компонент и генератора кода (интерпретатора). Способы взаимодействия компонент транслятора.

16.  Интерпретация выражений. Пример интерпретатора арифметических вычислений на основе анализатора методом рекурсивного спуска.

17.  Интерпретация управляющих структур программы.

18.  Компиляция выражений. Использование стековой архитектуры для генерации кода при восходящем и нисходящем разборе выражения. Компиляция управляющих структур программы.

Варианты заданий лексики для лабораторной работы

1.  идентификаторы вида s…s (sinus, sirius, secans);

2.  идентификаторы, заканчивающиеся на ex;

3.  десятичные константы;

4.  восьмеричные константы;

5.  шестнадцатеричные константы;

6.  вещественные константы;

7.  “диапазонные” константы вида +-126

8.  комментарии вида =!…!=

9.  комментарии вида <>…<>, операции <,<<,>,>>;

10.  операции =,==,!=,++, +=,+ ;

11.  “смайлики” вида “:-)” , “:-(”, “:-)) ”, “:-((” (или другие, по выбору).

Каждое задание формируется из 3-4 пунктов перечисленного списка.

Варианты заданий синтаксиса для лабораторных работ (и семантики для РГР)

1.  Си-грамматика арифметических выражений со скобками, операторов <выражение>; , for, if (c else и без него), и блочных скобок. Семантика: форматирование исходного текста программы согласно уровню вложенности операторов.

2.  Си-грамматика арифметических выражений со скобками, операций ++,--, *,&, (), [], <точка>, -> Семантика: восстановление типа данных идентификатора по виду выражения.

3.  Определение структурированного типа struct и контекстное определение переменных на его основе: struct a{…} a,a[c]; Семантика: проверка семантической правильности выражений над этими переменными (включая арифметику со скобками).

4.  Си-грамматика арифметических выражений со скобками, операторов <выражение>; и <выражение>=<ид>;, for, if (c else и без него),while, do-whille и блочных скобок. Семантика: интерпретатор условных и циклических операторов (значение выражения =0 – ложь, =1 - истина).

5.  Грамматика определения функции вида i(,i,i,i…){ E=i;E=i;E; } Программа представляет собой последовательность определений функций. Выражение может содержать вызов функции вида i(E,E,E,…). Семантика: интерпретатор, реализующий вызов и возврат из функции. В теле функции могут использоваться только односимвольные идентификаторы – формальные параметры и целые константы.

6.  Си-грамматика контекстного определения переменных и определения функций. Семантика: структура данных, содержащая информацию о типах определенных в программе объектов.

7.  Си-грамматика выражений для арифметических операций, сравнения, логических, поразрядных, присваивания и скобок. Семантика: генератор ассемблерного кода с использованием стека.

8.  Контекстное определение типов данных для переменных, включая struct, typedef. Семантика: структура данных, содержащая информацию о типах определенных в программе объектов.

9.  Заголовок класса в Си++: метки public и private, объявление свойств (в том числе объектов ранее определенных классов) и методов. Наследование. Cемантика: структура данных, содержащая информацию о классе, всех его компонентах и правах доступа.

10.  Контекстное определение простых переменных, указателей, массивов и массивов указателей с инициализаторами. Семантика: распределение памяти и ее заполнение значениями/адресами.

11.  Определение структурированного типа struct и контекстное определение переменных на его основе: struct a{…} a,a[c],*a,**a; Семантика: структура данных, содержащая информацию о типах определенных в программе объектов.