МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ
РЕСПУБЛИКИ КАЗАХСТАН
АЛМАТИСНКАЯ АКДЕМИЯ ЭКОНОМИКИ И СТАТИСТИКИ
ФАКУЛЬТЕТ ДЕЛОВОГО АДМИНСИТРИРОВАНИЯ
Кафедра Информатики
РАБОЧАЯ ПРОГРАММА
по дисциплине
“ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ”
специальности: “ИМ ”, «ИиАЯ»
форма обучения Дневная
курс __5__ семестр __9__
лекции __32____ часов,
лабораторные ___32___ часов
всего __64____ часов
Алматы, 2007
Программа дисциплины составлена старшим преподавателем
На основании ГОСО РК, типовых учебных планов направлений подготовки
__________________________________________________________________
Рассмотрена на заседании кафедры «Информатика»
«____» ________________ 2006 г. Протокол № ___
Зав. кафедрой _______________________
Одобрена Учебно-методическим советом
«____» ____________ 2006 г. Протокол № ___
Председатель _______________________
Сведения о преподавателе
старший преподаватель
Кафедра информатики каб. 505
E-mail: *****@***ru
Сведения о преподавателе
старший преподаватель
Кафедра информатики каб. 505
E-mail: *****@***ru
Время и место проведения учебной дисциплины
Время ____________________
№ аудитории: _____214________
ОБЩЕЕ ОПИСАНИЕ РАБОЧЕЙ ПРОГРАММЫ (СИЛЛАБУСА)
Цель преподавания дисциплины: научить студентов основам теории компиляции и программирования. Задачи изучения дисциплины: дать основные понятия теории формальных языков и грамматик; ознакомить с методами трансляции; обучить основам теории алгоритмов, теории верификации программ. Учебно-методическое обеспечение дисциплины:Список основной литературы
1. Доказательство правильности программ. М.: Мир, 1982.
2. Афанасьев языки и грамматики: Учебное пособие. – Ульяновск: УлГТУ, 1997.
3. Ульман Дж. Теория синтаксического анализа, перевода и компиляции, тт.1, 2. – М.:Мир, 1978.
4. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
5. Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Издательский дом «Вильямс», 2001.
6. Алгоритмы и структуры данных. – М.: Мир, 1989.
7. , Рудченко языки и грамматики. Элементы теории трансляции. – М.: Диалог-МГУ, 1999.
8. Математические методы анализа алгоритмов. – М.: Мир, 1987.
9. Наука программирования. – М.: Мир, 1984.
10. Д. Ван Тассел. Стиль, разработка, эффективность, отладка и испытание программ – М.: Мир, 1985.
11. Структурное программирование. – М.: Мир, 1975.
12. Дворянкин трансляции: Учебное пособие. – Волгоград: ВолгГТУ, 1999.
13. Дисциплина программирования. – М.: Мир, 1978.
14. Ершов в теоретическое программирование. – М.: Наука, 1977.
15. Лавров по теории программирования. – СПб.: изд-во НЕСТОР, 1999.
16. Лавров . Математические основы, средства, теория. – СПб.: БХВ-Петербург, 2001.
17. Логика и компьютер. Моделирование рассуждений и проверка правильности программ / , , и др. – М.: Наука, 1990.
18. Молчанов программное обеспечение: Учебник для вузов. – СПб.: Питер, 2003.
19. Рейуорд- Дж. Теория формальных языков. Вводный курс. – М.: Радио и связь, 1988.
20. Федоров построения трансляторов: Учебное пособие. – Обнинск: ИАТЭ, 1995.
21. Шарипбаев правильности программных и аппаратных средств компьютеров. — Алматы: НИЦ «Гылым», 1996.
Список дополнительной литературы
22. Конструирование компиляторов для цифровых вычислительных машин. – М.: Мир, 1975.
23. Введение в разработку и анализ алгоритмов. – М.: Мир, 1987.
24. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.
25. Карпов автоматов. – СПб.: Питер, 2003.
26. Искусство программирования для ЭВМ, т. 1, Основные алгоритмы. – М.: Мир, 1977.
27. Введение в математическую логику. – М.: Наука, 1976.
28. Вычисления и автоматы. – М.: Мир, 1978.
29. Ли Р. Математическая логика и автоматическое доказательство теорем. – М.: Наука, 1983.
30. Фомин основы разработки трансляторов: Учебное пособие. – Обнинск: ИАТЭ, 1995.
РАСПРЕДЕЛЕНИЕ ДИСЦИПЛИНЫ ПО ВИДАМ ЗАНЯТИЙ И РАСПРЕДЕЛЕНИЮ ЧАСОВ
таблица 2
№ п/п | Название темы | Учебные часы | |||
Лекции | СПЛЗ | СРС | СРСП | ||
1 | Основные принципы построения трансляторов | 2 | 2 | 2 | 2 |
2 | Формальные языки и грамматики | 1 | 1 | 1 | 1 |
3 | Лексические анализаторы | 2 | 2 | 2 | 2 |
4 | Синтаксические анализаторы | 3 | 3 | 3 | 3 |
5 | Демонстрационный язык программирования | 2 | 2 | 2 | 2 |
6 | Лексический анализатор демонстрационного языка программирования | 2 | 2 | 2 | 2 |
7 | Применение автоматов с магазинной памятью для нисходящего разбора слева направо | 1 | 1 | 1 | 1 |
8 | Использование динамически порождаемых автоматов для нисходящего разбора слева направо | 2 | 2 | 2 | 2 |
ВСЕГО: | 15 | 15 | 15 | 15 |
ПОЛНОЕ ОПИСАНИЕ УЧЕБНОГО ПРОЦЕССА ПО РАБОЧЕЙ ПРОГРАММЕ (СИЛЛАБУСУ)
1. Основные принципы построения трансляторов.
План лекции (1 ч.)
Трансляторы, компиляторы и интерпретаторы – общая схема работы. Современные компиляторы и интерпретаторы. Таблицы идентификаторов.
Задание на семинарское занятие (1 ч.): решение задач на построение таблиц идентификаторов.
Задания на СРС (1 ч.) и СРСП (1 ч.): решение задач и промежуточных тестов.
2. Формальные языки и грамматики.
План лекции (2 ч.)
Языки и цепочки символов. Способы задания языков. Грамматики и распознаватели. Цепочки вывода. Сентенциальная форма. Классификация языков и грамматик.
Задание на семинарское занятие (2 ч.): построение грамматик заданных языков; построение выводов цепочек языка; определение типа грамматики.
Задания на СРС (2 ч.) и СРСП (2 ч.): решение задач и промежуточных тестов.
3. Лексические анализаторы.
План лекции (2 ч.)
Лексические анализаторы (сканеры). Принципы построения сканеров. Регулярные языки и грамматики. Построение лексических анализаторов. Автоматизация построения лексических анализаторов (программа LEX).
Задание на семинарское занятие (2 ч.): решение систем уравнений с регулярными коэффициентами; построение регулярных грамматик; построение сканеров.
Задания на СРС (2 ч.) и СРСП (2 ч.): решение задач и промежуточных тестов.
4. Синтаксические анализаторы.
План лекции (2 ч.)
Основные принципы работы синтаксических анализаторов. Преобразование КС-грамматик. Приведенные грамматики. Синтаксические распознаватели с возвратом. Нисходящие распознаватели КС-языков без возвратов. LL(k)‑грамматики. Восходящие распознаватели КС-языков без возвратов. LR(k)‑грамматики. Автоматизация построения синтаксических анализаторов (программа YACC). Синтаксические распознаватели на основе грамматик предшествования.
Задание на семинарское занятие (3 ч.): построение распознавателей для заданных грамматик.
Задания на СРС (3 ч.) и СРСП (3 ч.): решение задач и промежуточных тестов.
Демонстрационный язык программированияПлан лекции (2 ч.)
Элементарные конструкции. Составные конструкции. Организация программы. Краткое описание семантики языка
Задание на семинарское занятие (2 ч.): Алгоритм Евклида (нахождение наибольшего общего делителя)
Одновременное нахождение наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК)
Суммирование n элементов из входного потока. Сортировка элементов вектора
Задания на СРС (4 ч.) и СРСП (4 ч.): решение задач и промежуточных тестов.
6 Лексический анализатор демонстрационного языка программирования
План лекции (2 ч.)
Транслитератор DPL. Непрямой лексический анализатор DPL. Прямой лексический анализатор DPL
Общая организация транслитератора. Диаграммы Вирта для отдельных автоматов непрямого лексического анализатора. Общая структура непрямого лексического анализатора
Задание на семинарское занятие (2 ч.):Программная реализация транслитератора. Программная реализация отдельных автоматов.
Задания на СРС (2 ч.) и СРСП (2 ч.): решение задач и промежуточных тестов.
7. Применение автоматов с магазинной памятью для нисходящего разбора слева направо
План лекции (2 ч.)
Необходимость использования автоматов с магазинной памятью. Организация автомата с магазинной памятью. Общая связь между грамматиками и автоматами с магазинной памятью. Связь между S-грамматикой и автоматом с магазинной памятью. Построение автомата с магазинной памятью по q-грамматике. Построение нисходящего автомата. LL(1) - грамматики. Программная реализация нисходящего автомата с магазинной памятью
Задание на семинарское занятие (1 ч.): Разработка программы по таблице переходов АМП.
Разработка программы с использованием метода рекурсивного спуска
Задания на СРС (1 ч.) и СРСП (1 ч.): решение задач и промежуточных тестов.
8. Использование динамически порождаемых автоматов для нисходящего разбора слева направо
План лекции (2 ч.)
Семантический разрыв между формальными грамматиками и автоматами с магазинной памятью. Модель динамически порождаемых конечных автоматов. Графический метаязык для описания динамически порождаемых конечных автоматов.
Использование диаграмм Вирта для представления динамически порождаемых конечных автоматов, распознающих КС(1) грамматику
.
Задание на семинарское занятие (2 ч.): контрольные вопросы по теме.
Задания на СРС (2 ч.) и СРСП (2 ч.): решение задач и промежуточных тестов.
ТЕМЫ ВОПРОСОВ ДЛЯ ПРОВЕДЕНИЯ КОНТРОЛЯ
Перечень тем вопросов для проведения первого рубежного контроля
Назовите основные способы определения формальных языков и их отличия.2. Дайте определение формальной грамматики.
3. Для чего нужны метаязыки?
4. Чем является формальный язык, порождаемый грамматикой?
5. Определите отношения вывода и назовите отличия, существующие между ними.
6. Для грамматики G3 приведите пример вывода терминальной цепочки, содержащей три знака умножения и два знака сложения.
7. Приведите пример цепочки для грамматики G3, содержащей пять операндов. Осуществите вывод этой цепочки из начального нетерминала.
8. Дайте определение распознавателя. Приведите его структуру.
9. Назовите известные Вам классы грамматик с ограничениями на правила. Дайте их определения.
10. Чем отличается язык, определяемый формальной грамматикой, от языка, определяемого распознавателем?
11. Назовите эквивалентные соотношения между определениями формальных языков с помощью распознавателей и грамматик, заданных иерархией Хомского.
12. Назовите отличия:
a. интерпретатора от компилятора;
b. компилятора от ассемблера;
c. перекодировщика от транслятора;
d. эмулятора от интерпретатора;
e. синтаксиса от семантики.
13. Приведите конкретные примеры использования методов трансляции в областях, не связанных с языками программирования.
14. Основные достоинства и недостатки компиляторов.
15. Основные достоинства и недостатки интерпретаторов.
16. Опишите основные различия в синтаксисе двух известных Вам языков программирования.
17. Опишите основные различия в семантике двух известных Вам языков программирования.
18. Назовите основные фазы процесса трансляции и их назначение.
19. Назовите специфические особенности однопроходной трансляции.
20. Назовите специфические особенности многопроходной трансляции.
21. Для чего нужен лексический анализатор?
22. Что порождает лексический анализатор?
23. Можно ли обойтись без сканера?
24. Назначение транслитератора.
25. Какая связь между сканером и конечным автоматом?
26. Существует ли связь между конечным автоматом и диаграммами Вирта?
27. Существует ли связь между конечным автоматом и праволинейными грамматиками?
28. Существует ли связь между конечным автоматом и грамматиками с левой рекурсией?
29. Как преобразовать грамматику с правой рекурсией в итеративную диаграмму Вирта?
30. Как преобразовать грамматику с левой рекурсией в итеративную диаграмму Вирта?
31. Назовите основные методы лексического анализа.
32. Приведите обобщенную структуру непрямого лексического анализатора.
33. Достоинства и недостатки непрямого лексического анализатора.
34. Можно ли повысит производительность непрямого лексического анализатора?
35. Приведите обобщенную структуру прямого лексического анализатора.
36. Достоинства и недостатки прямого лексического анализатора.
37. Перечислите конструкции конкретного языка программирования, которые целесообразно распознать на фазе лексического анализа.
Перечень тем вопросов для проведения второго рубежного контроля
1. Назначение синтаксического разбора.
2. Что является результатом синтаксического разбора?
3. Назовите основные критерии классификации синтаксического разбора.
4. Какие существуют методы разбора?
5. Связь методов разбора с выводом входной цепочки.
6. Особенности нисходящего разбора.
7. Особенности восходящего разбора.
8. Особенности комбинированного разбора.
9. Какие существуют последовательности разбора?
10. Связь между методами разбора и последовательностью разбора.
11. Особенности разбора с просмотром вперед.
12. Дополнительная классификация контекстно свободных грамматик.
13. Особенности разбора с возвратами.
14. Зачем, при синтаксическом разборе нужны автоматы с магазинной памятью?
15. Как организован автомат с магазинной памятью?
16. Основные операции автомата с магазинной памятью.
17. Каким образом ограничения, накладываемые на грамматику, определяют реализацию автомата?
18. Приведите примеры известных Вам ограниченных грамматик.
19. Каким образом можно построить АМП по s-грамматике?
20. Недостатки S-грамматики.
21. Разработка АМП по q-грамматике.
22. Приведите определения и краткие характеристики S-, q-, L-грамматик.
23. Методы программной реализации нисходящих автоматов с магазинной памятью.
24. Какие возможны варианты программной реализации нисходящего распознавателя при непосредственном использовании таблицы переходов АМП?
25. В чем специфика распознавателя, построенного с применением рекурсивного спуска?
26. Проблемы, существующие при наличии семантического разрыва при разработке транслятора.
27. Для сокращения семантического разрыва используется какая модель?
28. В чем заключается семантический разрыв между грамматиками и автоматами с магазинной памятью?
29. Определите модель динамически порождаемых конечных автоматов.
30. Взаимосвязь между ДПК-автоматами и диаграммами Вирта.
Перечень тем вопросов для проведения итогового контроля
1. Назовите основные способы определения формальных языков и их отличия.
2. Дайте определение формальной грамматики.
3. Для чего нужны метаязыки?
4. Чем является формальный язык, порождаемый грамматикой?
5. Определите отношения вывода и назовите отличия, существующие между ними.
6. Для грамматики G3 приведите пример вывода терминальной цепочки, содержащей три знака умножения и два знака сложения.
7. Приведите пример цепочки для грамматики G3, содержащей пять операндов. Осуществите вывод этой цепочки из начального нетерминала.
8. Дайте определение распознавателя. Приведите его структуру.
9. Назовите известные Вам классы грамматик с ограничениями на правила. Дайте их определения.
10. Чем отличается язык, определяемый формальной грамматикой, от языка, определяемого распознавателем?
11. Назовите эквивалентные соотношения между определениями формальных языков с помощью распознавателей и грамматик, заданных иерархией Хомского.
12. Назовите отличия:
a. интерпретатора от компилятора;
b. компилятора от ассемблера;
c. перекодировщика от транслятора;
d. эмулятора от интерпретатора;
e. синтаксиса от семантики.
13. Приведите конкретные примеры использования методов трансляции в областях, не связанных с языками программирования.
14. Основные достоинства и недостатки компиляторов.
15. Основные достоинства и недостатки интерпретаторов.
16. Опишите основные различия в синтаксисе двух известных Вам языков программирования.
17. Опишите основные различия в семантике двух известных Вам языков программирования.
18. Назовите основные фазы процесса трансляции и их назначение.
19. Назовите специфические особенности однопроходной трансляции.
20. Назовите специфические особенности многопроходной трансляции.
21. Для чего нужен лексический анализатор?
22. Что порождает лексический анализатор?
23. Можно ли обойтись без сканера?
24. Назначение транслитератора.
25. Какая связь между сканером и конечным автоматом?
26. Существует ли связь между конечным автоматом и диаграммами Вирта?
27. Существует ли связь между конечным автоматом и праволинейными грамматиками?
28. Существует ли связь между конечным автоматом и грамматиками с левой рекурсией?
29. Как преобразовать грамматику с правой рекурсией в итеративную диаграмму Вирта?
30. Как преобразовать грамматику с левой рекурсией в итеративную диаграмму Вирта?
31. Назовите основные методы лексического анализа.
32. Приведите обобщенную структуру непрямого лексического анализатора.
33. Достоинства и недостатки непрямого лексического анализатора.
34. Можно ли повысит производительность непрямого лексического анализатора?
35. Приведите обобщенную структуру прямого лексического анализатора.
36. Достоинства и недостатки прямого лексического анализатора.
37. Перечислите конструкции конкретного языка программирования, которые целесообразно распознать на фазе лексического анализа.
38. Назначение синтаксического разбора.
39. Что является результатом синтаксического разбора?
40. Назовите основные критерии классификации синтаксического разбора.
41. Какие существуют методы разбора?
42. Связь методов разбора с выводом входной цепочки.
43. Особенности нисходящего разбора.
44. Особенности восходящего разбора.
45. Особенности комбинированного разбора.
46. Какие существуют последовательности разбора?
47. Связь между методами разбора и последовательностью разбора.
48. Особенности разбора с просмотром вперед.
49. Дополнительная классификация контекстно свободных грамматик.
50. Особенности разбора с возвратами.
51. Зачем, при синтаксическом разборе нужны автоматы с магазинной памятью?
52. Как организован автомат с магазинной памятью?
53. Основные операции автомата с магазинной памятью.
54. Каким образом ограничения, накладываемые на грамматику, определяют реализацию автомата?
55. Приведите примеры известных Вам ограниченных грамматик.
56. Каким образом можно построить АМП по s-грамматике?
57. Недостатки S-грамматики.
58. Разработка АМП по q-грамматике.
59. Приведите определения и краткие характеристики S-, q-, L-грамматик.
60. Методы программной реализации нисходящих автоматов с магазинной памятью.
61. Какие возможны варианты программной реализации нисходящего распознавателя при непосредственном использовании таблицы переходов АМП?
62. В чем специфика распознавателя, построенного с применением рекурсивного спуска?
63. Проблемы, существующие при наличии семантического разрыва при разработке транслятора.
64. Для сокращения семантического разрыва используется какая модель?
65. В чем заключается семантический разрыв между грамматиками и автоматами с магазинной памятью?
66. Определите модель динамически порождаемых конечных автоматов.
67. Взаимосвязь между ДПК-автоматами и диаграммами Вирта.
