Реферат: Языки программирования и методы трансляции

Наименование дисциплины: Языки программирования и методы трансляции

Направление подготовки: 010400 Прикладная математика и информатика

Квалификация (степень) выпускника: бакалавр

Форма обучения: очная

Авторы: д-р физ.-мат.наук, профессор, зав.кафедрой теоретической информатики В.А.Соколов, к.ф.-м.н., доцент, доцент кафедры теоретической информатики Д.Ю.Чалый.


1. Дисциплина «Языки программирования и методы трансляции» обеспечивает приобретение знаний и умений в соответствии с государственным образовательным стандартом, содействует фундаментализации образования, формированию системного мышления. Целью преподавания дисциплины является ознакомление слушателей с основами построения компиляторов для языков высокого уровня, алгоритмами обработки и хранения специфической текстовой информации.


2. Дисциплина «Языки программирования и методы трансляции» является базовой в профессиональном цикле. Дисциплина «Языки программирования и методы трансляции» относится к области системного программирования, ее преподавание основывается на знаниях полученных слушателями при изучении дисциплин «Основы информатики», «Основы программирования», «Языки и методы программирования», «Дискретная математика», «Математическая логика» и «Практикум по ЭВМ». Знания и навыки, полученные при изучении дисциплины, используются слушателями при изучении специальных дисциплин и при подготовке выпускной дипломной работы.


3. В результате освоения дисциплины обучающийся должен:


Знать:

- алгоритмы эквивалентных преобразований детерминированных и недетерминированных конечных автоматов;

- основные алгоритмы анализа и преобразования регулярных и контекстно-свободных грамматик;

- алгоритмы лексического, восходящего и нисходящего синтаксического анализа,

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


Уметь:

- описывать формальные языки с помощью грамматик различных типов, автоматов-

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

- применять на практике алгоритмы эквивалентных преобразований грамматик и

конечных автоматов;

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

- понимать идеологию построения формальных языков и грамматик;

описывать исходные данные посредством грамматик;

разрабатывать и реализовывать на компьютере компилятор для языка высокого уровня типа С;

разрабатывать тесты и отлаживать сложные программные комплексы.

Владеть:

-навыками практического применения алгоритмов эквивалентных преобразований грамматик и конечных автоматов;

навыками разработки тестов и отладки программных комплексов.





4. Общая трудоемкость дисциплины составляет 5 зачетных единиц, 180 часов.


5. Содержание дисциплины:


№ п/п

Раздел дисциплины

1

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

1.1. Введение. Формальные языки и грамматики.

1.2. Основные понятия и определения формальных языков и грамматик.

2

Раздел 2. Детерминированные и недетерминированные конечные автоматы-распознаватели

2.1. Конечные автоматы.

2.2. Детерминированные конечные автоматы (распознаватели).

2.3. Языки и детерминированные конечные автоматы.

2.4. Недетерминированные конечные автоматы (распознаватели).

2.5. Эквивалентность детерминированных и недетерминированных конечных автоматов.

2.6. Минимизация конечных автоматов.

3

Раздел 3. Регулярные грамматики и регулярные языки

3.1. Регулярные выражения.

3.2. Связь между регулярными выражениями и языками, распознаваемыми конечными автоматами.

3.3. Регулярные грамматики.

3.4. Связь между регулярными выражениями и регулярными языками.

3.5. Свойства регулярных языков. Замкнутость класса регулярных языков.

3.6. Алгоритмические проблемы регулярных языков.

3.7. Лемма о расширении регулярных языков.

4

Раздел 4. Контекстно-свободные грамматики и языки. Нормальные формы.

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

4.2. Методы преобразования контекстно-свободных грамматик.

4.3. Нормальные формы контекстно-свободных грамматик.

4.4. Свойства контекстно-свободных языков. Лемма о расширении. Свойства замкнутости класса контекстно-свободных языков.

4.5. Некоторые алгоритмические проблемы для контекстно-свободных языков.

5

Раздел 5. Недетерминированные и детерминированные магазинные автоматы-распознаватели

5.1. Магазинные автоматы.

5.2. Недетерминированные магазинные автоматы.

5.3. Детерминированные магазинные автоматы.

5.4. Магазинные автоматы и контекстно-свободные языки.

5.5. Детерминированные языки.

6

Раздел 6. Контекстно-свободные языки и проблема грамматического разбора.

6.1. Грамматический разбор.

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

7

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

7.1. Описание языка программирования.

7.2. Методы описания синтаксиса языка (формальные грамматики, форма Бэкуса-Наура).

7.3. Классификация грамматик. Понятие вывода и дерева вывода. Эквивалентные преобразования грамматик.

7.4. Определение задачи трансляции.

8

Раздел 8. Лексический анализ

8.1. Задачи, решаемые на этапе лексического анализа.

8.2. Описание лексических конструкций языка программирования при помощи регулярных грамматик и регулярных выражений.

8.3. Использование конечных автоматов для построения лексического анализатора.

8.4. Формирование таблиц имен.

9

Раздел 9. Синтаксический анализ

9.1. Универсальные методы синтаксического анализа – метод Ангера и метод Кока-Янгера-Касами.

9.2. Автоматы с магазинной памятью. Алгоритмы синтаксического анализа с использованием магазинных автоматов.

9.3. Метод исчерпывающего рекурсивного спуска с возвратами.

9.4. Определение LL(1)-грамматики и методы синтаксического анализа для этого класса грамматик. LL(k)-грамматики.

9.5. Определение LR(0)-грамматик и методы синтаксического анализа для этого класса грамматик. LR(k>1)-грамматики.

9.6. Виды ошибок, их классификация по сложности и фазам компилятора. Методы обработки ошибочных ситуаций в компиляторе.

10

Раздел 10. Семантический анализ и генерация промежуточного кода

10.1. Формальное определение перевода.

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

10.3. Атрибутные грамматики. Классификация атрибутных грамматик. Применение атрибутных грамматик для генерации промежуточного кода и проверки семантических условий.



6. Учебно-методическое и информационное обеспечение дисциплины:


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

Ахо А., Ульман Дж.Д. Теория синтаксического анализа, перевода и компиляции. - М.: Мир, 1978.- т.1.-616с.; т.2.-488с.

Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. - М.: Вильямс, 2002.

Aho A.V., Sethi R., Ullman J.D. Compiles: Principles, Techniques and Tools, Standford University, Standford, California, 1988. - 796p.

Грис Д. Конструирование компиляторов для цифровых вычислительных машин. - М.:Мир, 1975. - 544с.

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

Вайнгартен Ф. Трансляция языков программирования.- М.: Мир, 1977.- 192с.

Касьянов В.И., Поттосин И.В. Методы построения трансляторов. - Новосибирск: Наука, 1986. - 344с.

Хантер Р. Проектирование и конструирование компиляторов. - М.: Финансы и статистика, 1984. - 232с.

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

Соколов В.А. Формальные языки и грамматики: Учебное пособие (с грифом: Рекомендовано Министерством общего и профессионального образования РФ в качестве учебного пособия для студентов университетов по специальности 010200 «Прикладная математика и информатика» и по направлению 510200 «Прикладная математика и информатика») / Яросл. гос. ун-т. Ярославль, 1998, 152 с.

Соколов В.А. Формальные языки и грамматики. Курс лекций: Учебное пособие / Яросл. гос. ун-т. Ярославль, 2003. - 152 с.

Соколов В.А., Чалый Д.Ю. Технологии трансляции. Учебное пособие / ЯрГУ, 2008. 124 с.

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

Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение: учебник для вузов. - СПб.: Питер, 2001.-736с.

Соколов В.А. Языки, автоматы, грамматики. Методические указания. Изд. 2-е, испр. ЯрГУ, Ярославль, 2003.


б) дополнительная литература:

Ахо А., Ульман Дж.Д. Принципы машинного проектирования. - М.: Мир, 1983. - 352с.

Вайнгартен Ф. Трансляция языков программирования.- М.: Мир, 1977.- 192с.

Зелковиц М., Шоу А., Бынон Дж. Принципы разработки программного обеспечения. - М.: Мир, 1982.

Бекхауз Р.Ч. Синтаксис языков программирования. - М.:Мир. 1986. - 281с.

Бек Л. Введение в системное программирование. - М.: Мир, 1988.

Хэндрикс Д. Компилятор языка Си для микро-ЭВМ. -М.: Радио и Связь, 1989. – 239