Рабочая программа по курсу “Теория компиляции.” ( наименование дисциплины по учебному плану )
.RU

Рабочая программа по курсу “Теория компиляции.” ( наименование дисциплины по учебному плану )




Нижегородский государственный технический университет

Факультет_____ ИРИТ ___________________________

( наименование факультета )


УТВЕРЖДАЮ:

Первый проректор

Кошелев О.С.

« » ________2010 г.


Р А Б О Ч А Я П Р О Г Р А М М А
по курсу “Теория компиляции.”

( наименование дисциплины по учебному плану )
Направление подготовки 510200 Прикладная математика и информатика
( шифр и наименование )

Направление специальности 010000 Естественнонаучные специальности

( шифр и наименование )

Специальность 010200 Прикладная математика и информатика

( шифр и наименование )
^ Кафедра “Прикладная математика “
( наименование )

Курс 2
Семестр 4


Общая трудоемкость дисциплины 112 ( час )

Аудиторные занятия 72 ( час )

^ Лекции 32 ( час ) Самостоятельная
работа 40 ( час )

Лабораторные

занятия 40 ( час )


Практические Экзамен 4 ( семестр )

занятия ( час )


Курсовой проект Зачет ( семестр )

( работа ) ( час )


Расчетно-графические

Работы ( час )

^ Рабочая программа утверждена на заседании кафедры
« » ___________ 2010_ г.


Зав. кафедрой ________________ ___ Митяков С Н.__

( подпись ) ( Ф.И.О.)

Председатель координационного научно-методического совета

по направлению подготовки 510200 Прикладная математика и информатика

( шифр, наименование )

Митяков С Н.

( подпись ) ( Ф.И.О. )

« » 2010__ г.


Председатель МКС 010200 Прикладная математика и информатика

( шифр, наименование специальности )

Митяков С Н.

( подпись ) ( Ф.И.О. )

« » 2010__ г.


^ ПОЯСНИТЕЛЬНАЯ ЗАПИСКА


Рабочая программа составлена на основании Государственного стандарта высшего профессионального образования по направлению подготовки бакалавра 510200 – Прикладная математика и информатика и направлению специальности дипломированного специалиста 010200 - Прикладная математика и информатика.

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

В курсе существенно используются знания из курсов: Дискретная математика, Методы вычислений, Формальные языки и алгоритмы.


^ ОПИСАНИЕ СОДЕРЖАНИЯ ОСНОВНЫХ ТЕМ КУРСА



  1. Вводные замечания.

Процессы перевода и компиляции. Основные фазы компиляции. Перевод и семантика. Польская запись как важный пример перевода арифметических выражений. Проблема описания бесконечного перевода конечными средствами. Транслятор как устройство, реализующее заданный перевод. Желательные качества транслятора. Два основных формализма, применяемые для определения перевода: схемы синтаксически управляемой трансляции и преобразователи.

  1. ^ Синтаксически управляемые процессы обработки языков.

Транслирующие грамматики. Определение СУ-схемы. Выводимые пары цепочек. Перевод как преобразование деревьев вывода. Понятие СУ-перевода. Простые СУ-переводы. Атрибутные транслирующие грамматики. Примеры наследуемых и синтезируемых атрибутов. Представление деревьями. Перевод арифметических выражений. Неоднозначные грамматики и многозначные переводы.

  1. ^ Конечные и стековые преобразователи.

Конечный преобразователь как простейший транслятор. Общая схема. Формальное определение. Принцип работы, понятие такта и конфигурации. Понятие регулярного перевода или конечного преобразования. Проблема детерминизма для конечных преобразователей. Определение стекового преобразователя. Принцип работы. Детерминированные стековые преобразователи. Расширенные стековые преобразователи. Лемма о существовании простой СУ-схемы, реализующий тот же перевод, что и стековый преобразователь.

  1. ^ Лексический анализ.

Сущность фазы лексического анализа. Понятие лексемы. Язык расширенных регулярных выражений. Последовательность регулярных определений. Непрямой лексический анализ. Моделирование лексического анализатора на базе конечного автомата. Алгоритм построения конечного автомата по расширенному регулярному выражению. Прямой лексический анализ. Построение прямого лексического анализатора. Замечания о программном моделировании конечных преобразователей.

  1. ^ Общий подход к синтаксическому анализу.

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

  1. ^ Синтаксический анализ с возвратами.

Общий подход к проблеме. Моделирование стекового анализатора. Понятие незацикливающего анализатора. Неформальное описание нисходящего и восходящего разбора с возвратами. Понятие альтернативы. Алгоритмы разбора с возвратами (обзор).

  1. ^ Нисходящий однопроходный анализ без возвратов.

Общий подход. Левоанализируемые грамматики (LL(k)-грамматики). Их свойства. Простая (разделенная) LL(1) – грамматика. Предсказывающий алгоритм разбора для LL(k) – грамматик. Корректность k – предсказывающего алгоритма. Разбор для LL(1) – грамматик. Разбор для LL(k) – грамматик. Обработка ошибок при нисходящем разборе.

  1. ^ Нисходящие методы обработки атрибутных грамматик.

Понятие L-атрибутной грамматики. Форма простого присваивания. Построение атрибутного автомата с магазинной памятью. Примеры: условные операторы и арифметические выражения.

  1. ^ Детерминированный восходящий синтаксический анализ.

Разбор с помощью детерминированного алгоритма перенос-свертка. Правоанализирующие LR(k) – грамматики, их свойства. LR(k) алгоритм разбора. LR(0) – грамматики. Построение детерминированного правого анализатора для LR(k) – грамматик. Обработка ошибок при восходящем разборе. Замечания о реализации левых и правых анализаторов. Их временная и емкостная сложность.

  1. ^ Генерация кода.

Организация таблиц компилятора. Таблицы идентификаторов и таблицы символов. Функции расстановки. Реализация блочной структуры. Окружение компилятора и объектная машина. Динамическое распределение памяти. Назначение адресов. Трансляция арифметических выражений. Распределение регистров при обработке арифметических выражений. Особенности обработки арифметических выражений.

  1. ^ Обзор методов оптимизации объектного кода.

Понятие атома. Оптимизация одного атома и цепочки атомов. Оптимизация операторов. Оптимизация циклов.


^ ВЕДОМОСТЬ РАСПРЕДЕЛЕНИЯ ЧАСОВ ЛЕКЦИОННЫХ ЗАНЯТИЙ ПО ТЕМАМ



Наименование темы
Лекции

  1. Введение. Схемы синтаксически управляемого перевода.
4

  1. Конечные и стековые преобразователи.
4

  1. Лексический анализ.
2

  1. Общий подход к синтаксическому анализу.

4

  1. Однопроходный синтаксический анализ с возвратами.
4

  1. Методы однопроходного нисходящего анализа без возвратов.
6

  1. Методы однопроходного восходящего анализа без возвратов.
4

  1. Генерация и оптимизация кода.
4

Всего часов:
32



^ Наименование тем лабораторных работ

Проводятся бригадами 2-4 человека.

Допуск занятий осуществляется устным опросом.

Отчеты - по окончании лабораторных работ каждой рабочей группой.

Зачеты лабораторной работы опросом рабочей группы.




Тема (раздел) дисциплины

Тема (наименование) лабораторной работы

Лаб. работа

1

2

Применение программы AWK для создания текстовых процессоров.

10

2

4

Моделирование лексических анализаторов на базе системной утилиты lex.

10

3

5

Моделирование синтаксического анализатора на базе yacc

14

4

10

Реализация виртуальной стековой машины

6







Итого

40



^ ОРГАНИЗАЦИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ


Самостоятельная работа предусмотрена как работа в компьютерном классе для выполнения лабораторных работ и самостоятельного изучения системных утилит tr и sed.


^ Виды самостоятельной работы

Объем самостоятельной работы по рабочему плану (час)

1. Проработка лекционного материала (а так же дополнительных тем, указанных лектором)

12

2. Подготовка к практическим занятиям.

-

3. Подготовка к лабораторным занятиям.

12

4. Подготовка реферата по теме.

-

5. Выполнение курсовой работы (проекта)

-

6. Выполнение расчетно-графической работы.

-

7. Подготовка к текущему контролю (тестированию и т.д.)

-

8. Подготовка к промежуточному контролю.

8

9. Подготовка к экзамену (зачету).

8

Итого

40
^ Контрольные вопросы

  1. Формальные грамматики.

  2. Понятие вывода в формальной грамматике.

  3. Семантика.

  4. Классификация грамматик.

  5. Определение СУ-схемы.

  6. Контекстно-свободные грамматики.

  7. Деревья вывода.

  8. Левые и правые выводы в контекстно-свободных грамматиках.

  9. Неоднозначность КС-грамматик.

  10. Алгоритм построения исходящего МП-распознавателя.

  11. Понятие перевода.

  12. Способы задания перевода.

  13. Польская запись арифметических выражений.

  14. Понятие лексемы.

  15. Расширенные регулярные выражения.

  16. Схема СУ-перевода.

  17. Конечные преобразователи.

  18. Преобразователи с магазинной памятью.

  19. Основные части компилятора.

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

  21. Синтаксический анализ.

  22. Определение разбора.

  23. Левый разбор.

  24. СУ-схема левого разбора.

  25. Построение левого анализатора.

  26. Восходящий (правый) разбор.

  27. Построение правого анализатора.

  28. Генерация кода.

  29. Окружение компилятора и объектная машина.

  30. Методы оптимизации объектного кода.


ЛИТЕРАТУРА



^ Автор, наименование

Изд-во

Год издания

Кол-во в библиотеке НГТУ

^ А. Основная

1

Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции, т.2

М.: Мир

1978

3

2

Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов

М.:Мир

1979

8

3

Манфред Брой. Информатика

М.: Наука

1996

10

^ Б. Дополнительная

1

Яблонский С.В. Введение в дискретную математику

М.: Наука

1979

15

2

Кауфман В.Ш. Языки программирования. Концепции и принципы.

М.: Радио и связь

1970

15




Ковригин Д.А. Прикладная математика. Сайт для студентов www.kovriguineda.ucoz.ru


Н.Новгород

2010






Составил: Ковригин Д.А





referat-po-biologii-uchenici-9-klassa-simonovoj-olgi.html
referat-po-deloproizvodstvu-v-kadrovoj-sluzhbe-vipolnila-studentka.html
referat-po-disciline-otechestvennaya-istoriya-na-temu-istoricheskij-portret-ivana-groznogo.html
referat-po-discipline-anglijskij-yazik-na-temu-sravnenie-norm-i-pravil-etiketa-v-anglii-i-rossii.html
referat-po-discipline-avtomatizaciya-proizvodstva-tema-sistemi-avtomaticheskogo-upravleniya.html
referat-po-discipline-bezopasnost-i-zashita-v-chs-na-temu-krupnejshie-prirodnie-katastrofi-xx-veka-i-ih-posledstviya.html
  • ucheba.bystrickaya.ru/professor-moskovskoj-duhovnoj-akademii-posmertnaya-zhizn-dushi-stranica-3.html
  • esse.bystrickaya.ru/programma-uchebnogo-zanyatiya-zanimatelnaya-matematika-v-shkole-budushego-pervoklassnika.html
  • urok.bystrickaya.ru/prikaz-ot-200-g-usta-v-municipalnogo-obsheobrazovatelnogo-uchrezhdeniya-nachalnaya-obsheobrazovatelnaya-shkola-s-zhedrinka-novoburasskogo-rajona-saratovskoj-oblasti.html
  • uchitel.bystrickaya.ru/razdel-iv-otdelnie-vidi-obyazatelstv-glava-30-kuplya-prodazha-a-a-erlihman-organizaciya-tehnika-i-buhgalterskij.html
  • grade.bystrickaya.ru/obrashennaya-gazovaya-hromatografiya-fiziko-himicheskie-osnovi-metoda-primenenie-sovremennoe-apparaturnoe-oformlenie.html
  • predmet.bystrickaya.ru/sportivno-ozdorovitelnaya-rabota-publichnij-doklad.html
  • znaniya.bystrickaya.ru/razdel-iv-dinamika-lichnosti-lev-kulikov.html
  • composition.bystrickaya.ru/plan-raboti-prishkolnogo-lagerya-kapitoshka-1-j-den-poznakomimsya-poblizhe.html
  • kontrolnaya.bystrickaya.ru/referat-ot-lat-refere-soobshat-dokladivat-yavlyaetsya-odnim-iz-samih-rasprostranennih-pismennih-soobshenij.html
  • ekzamen.bystrickaya.ru/rossijskoj-federacii-rossijskij-gosudarstvennij-professionalno-pedagogicheskij-universitet-kafedra-teoreticheskoj-i-eksperimentalnoj-psihologii.html
  • credit.bystrickaya.ru/pamyat-29-sentyabrya-zhitie-prepodobnogo-otca-nashego-kiriaka-zhitiya-svyatih-tom-9-sentyabr.html
  • uchebnik.bystrickaya.ru/voprosi-filosofii-m-2008-12.html
  • gramota.bystrickaya.ru/zakalivanie-i-ozdorovitelnaya-rabota-programma-vospitaniya-i-obucheniya-detej-starshego-doshkolnogo-vozrasta.html
  • college.bystrickaya.ru/2016-zhili-1-31-tamiz-araliinda-ds-sanitarli-zhne-fitosanitarli-sharalar-bojinsha-komitet-zhariyalaan-habarlamalar-tzm.html
  • writing.bystrickaya.ru/korporativnaya-set-intranet.html
  • ekzamen.bystrickaya.ru/regionalnij-etap-vserossijskoj-olimpiadi-shkolnikov-po-iskusstvu-mhk-21-01-2011.html
  • textbook.bystrickaya.ru/izmenenie-organizacionnoj-strukturi-predpriyatiya.html
  • institut.bystrickaya.ru/tematicheskoe-planirovanie-kursa-matematiki-obrazovatelnaya-programma-nachalnogo-obshego-obrazovaniya-mou-sosh-47-na-2011-2015-gg.html
  • urok.bystrickaya.ru/programma-po-obshej-patologii-dlya-studentov-mediko-biologicheskih-fakultetov-s-ekzamenacionnimi-voprosami-makro-i-mikropreparatami-dlya-specialnostej.html
  • lecture.bystrickaya.ru/aktualnost-izucheniya-terminosistemi-selskohozyajstvennoj-mikrobiologii.html
  • control.bystrickaya.ru/dzhej-hejli-terapiya-ispitaniem-stranica-3.html
  • klass.bystrickaya.ru/8razreshenie-sporov-i-raznoglasij-chelyabinskij-radiozavod-polyot.html
  • studies.bystrickaya.ru/dzhangildin-alibi-togzhanovich.html
  • klass.bystrickaya.ru/adil-radzhabli-azrbaycan-respublikasi-thsil-nazirliyi.html
  • obrazovanie.bystrickaya.ru/programma-kursa-pravo-vto-moskva-2009-g.html
  • textbook.bystrickaya.ru/kak-rabotat-s-tekstovim-materialom-bez-slovarya-uchebno-metodicheskij-kompleks-disciplini-gse-f-01-inostrannij.html
  • shpora.bystrickaya.ru/zheke-adamni-negel-estetikali-azhettlgn-damuindai-dnn-alatin-orni.html
  • bukva.bystrickaya.ru/shkola-sovershenstva-richard-bah-dar-tomu-kto-rozhden-letat.html
  • ekzamen.bystrickaya.ru/rossijskoj-federacii-v-kachestve-uchebnogo-posobiya-dlya-studentov-visshih-uchebnih-zavedenij-obuchayushihsya-po-specialnosti-021100-yurisprudenciya-izdatelstvo-norma-moskva-2007-stranica-12.html
  • shpargalka.bystrickaya.ru/valerij-demin-stranica-25.html
  • doklad.bystrickaya.ru/v-oblasti-bortovogo-oborudovaniya-i-agregatov-federalnaya-celevaya-programma-razvitie-grazhdanskoj-aviacionnoj-tehniki.html
  • nauka.bystrickaya.ru/upravlenie-dinamicheskim-povedeniem-rotorov-gtd-posredstvom-opori-s-reguliruemoj-zhestkostyu.html
  • learn.bystrickaya.ru/glava-15-kogda-nebo-soedinyalos-s-zemlej-graham-hancock-robert-bauval.html
  • composition.bystrickaya.ru/plan-provedeniya-uchebnih-zanyatij-shkola-magistrata-o-v-necenko-kandidat-pedagogicheskih-nauk.html
  • tests.bystrickaya.ru/makroelementi-v-organizme-cheloveka-zabolevaniya-svyazannie-s-izbitkom-makroelementov-v-organizme-cheloveka.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.