Рабочая программа дисциплины Языки, грамматики и автоматы Для подготовки бакалавров по направлению 552800 icon

Рабочая программа дисциплины Языки, грамматики и автоматы Для подготовки бакалавров по направлению 552800


Смотрите также:
Рабочая программа дисциплины Метрология программного обеспечения Для подготовки бакалавров по...
Рабочая программа дисциплины моделирование для подготовки бакалавров по направлению 552800...
Рабочая программа дисциплины Технология разработки программного обеспечения Для подготовки...
Рабочая программа дисциплины “Узлы и устройства эвм” Для подготовки бакалавров по направлению...
Рабочая программа дисциплины микропроцессорные системы для подготовки бакалавров по направлению...
Рабочая программа дисциплины сетевые технологии для подготовки магистров по направлению 552800...
Рабочая программа дисциплины микропроцессорные технологии для подготовки магистров по...
Рабочая программа учебной дисциплины Для направления 030900...
Образовательный стандарт по направлению бакалавриата 552800 «Информатика и вычислительная...
Рабочая программа дисциплины базы знаний и экспертные системы для подготовки бакалавров по...
Методические указания по оформлению курсовых проектов (работ)...
Рабочая программа дисциплины Для студентов, обучающихся по направлению 080200. 62 «Менеджмент»...



Загрузка...
скачать


Министерство образования Российской Федерации


Санкт-Петербургский государственный электротехнический

университет “ЛЭТИ”


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


дисциплины




Языки, грамматики и автоматы




Для подготовки бакалавров по направлению 552800 - “Информатика и вычислительная техника”







Санкт-Петербург


2002

Санкт-Петербургский государственный электротехнический


университет “ЛЭТИ”


“УТВЕРЖДАЮ”



Проректор по учебной работе


проф. ___________ Ушаков В.Н.


“_____”_______________2002 г.


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


дисциплины



Языки, грамматики и автоматы

Для подготовки бакалавров по направлению 552800 - “Информатика и вычислительная техника”



Факультет компьютерных технологий и информатики

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


Курс 3

Семестр 5


Лекции

80 ч.




Экзамен

семестр













5

Курсовое проектирование

16 ч.













Аудиторные занятия

96 ч.







Самостоятельные занятия

89ч.




Всего часов

185 ч.









2002

Рабочая программа обсуждена на заседании кафедры Вычислительной техники “____”_______________2002 г., протокол №______.


Рабочая программа согласована с рабочими программами изученных ранее дисциплин:

1)Дискретная математика

2)Программирование

3)Организация ЭВМ и систем


Рабочая программа одобрена методической комиссией факультета компьютерных технологий и информатики

“____”_____________2002г.

^ Цели и задачи дисциплины


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

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


^ Требования к уровню освоения дисциплины


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


  1. Знать основные определения, принципы построения, работы формальных грамматик и автоматов, а также области их применения.

  2. Уметь строить простые грамматики и автоматы и осуществлять их реализацию.

  3. Иметь представление об общей теории формальных языков и грамматик, методах построения компиляторов и цифровых блоков компьютеров.



Содержание рабочей программы



Тема 1. Введение

Предмет дисциплины, ее объем, содержание, роль в подготовке специалистов по направлению "Информатика". Связь с другими дисциплинами. Краткий обзор литературы.


Тема 2. ^ Определение и типы грамматик и языков.

Определение грамматики и языка. Вывод. Язык, порождаемый грамматикой. Пустой язык. Эквивалентные и неоднозначные грамматики. Типы грамматик и языков. Автоматные грамматики. Контекстно-свободные грамматики. Неукорачивающие грамматики. Исключение цепных и леворекурсивных правил.


Тема 3. ^ Конечные распознаватели

Определение конечного автомата. Работа автомата. Построение автомата по заданной грамматике. Недетерминированные автоматы. Преобразование недетерминированных автоматов в детерминированные. Построение автомата для заданного конечного языка.


Тема 4. ^ Магазинные распознаватели


Определение магазинного автомата. Работа магазинного автомата. Детерминированные и недетерминированные автоматы. Расширенные автоматы.Тема 5 Нисходящие распознаватели

Работа детерминированного распознавателя. Разделенные грамматики. Функции ПЕРВ и СЛЕД. Определение слаборазделенных и LL(1) грамматик. Построение распознавателей для LL(1) грамматик.


Тема 6 ^ Восходящие распознаватели

Работа детерминированного распознавателя. -грамматики. Грамматические символы и грамматические вхождения. Таблицы, описывающие работу восходящего распознавателя. Функции ВПЕРВ и ВПОД. Построение распознавателя для -грамматик. Построение распознавателей для -грамматик. Построение распознавателей для грамматик и с аннулирующими правилами.

Тема 7 ^ Способы описания перевода

Определение перевода. Синтаксически управляемые схемы перевода. Простые схемы перевода. Транслирующие грамматики. Построение транслирующей грамматики по заданной простой схеме.


Тема 8 ^ Конечные преобразователи

Определение и работа конечного преобразователя. Построение преобразователя по заданной транслирующей грамматике. Примеры построения преобразователей. Эквивалентные и совместимые состояния. Лексический анализатор.


Тема 9 ^ Магазинные преобразователи

Определение и работа нисходящего преобразователя. Построение

нисходящих преобразователей. Определение и работа восходящего преобразователя. Постфиксные транслирующие грамматики. Построение восходящих преобразователей.


Тема 10 Атрибутные грамматики

Семантика конструкций языков программирования. Определение атрибутной грамматики. Вывод с помощью правил грамматики. Отложенные вычисления. Левосторонняя атрибутная грамматика. Грамматика простого присваивания.

Тема 11 Атрибутные преобразователи

Представление атбирутов в стеке преобразователя. Правила установки указателей. Представление правил атрибутной грамматики в стеке. Построение команд преобразователя для записи в стек. Порядок построения атрибутного преобразователя. Описание работы преобразователя.

Тема 12 Программная реализация преобразователей

Реализация магазина и представление магазинных символов. Представление таблиц переходов операторов условного перехода. Алгоритмы работы преобразователей.


Тема 13. Переключательные функции.

Булева алгебра. Алгебра переключательных функций. Аналитические записи переключательных функций. Геометрическое и графическое представление функций.


Тема 14. Минимизация переключательных функций.

Задача минимизации. Построение множества минималей. Неизбыточные покрытия, экстремали. Построение минимальных покрытий. Визуальные методы минимизации.

Тема 15. Полнота функциональных базисов.

Переключательные функции двух переменных. Замкнутые классы функций. Теорема о функциональной полноте. Реализация функций в различных базисах.


Тема 16. Аппаратная реализация преобразователей.

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


Тема 17. Заключение

Цели и содержание курсового проекта (работы)


Целью курсовой работы является закрепление материала, излагаемого на лекциях, и демонстрация возможности программной реализации формальных моделей. Этапы выполнения курсовой работы:

1) Описание задания.

2) Построение формального описания атрибутного преобразователя.

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

4) Построение алгоритма работы преобразователя.

5) Разработка программы, моделирующей работу преобразователя.

6) Отладка и тестирование программы.


^ Распределение учебных часов по темам и видам занятий




темы

Название разделов и тем

Объем учебных часов


Семестр

Лекции

Лабор.

занятия

Практ.

занятия

Аудит.

занятия

Самост.

работа

Всего

1

Введение

2







2




2

5

2

Определение и типы грамматик и языков

3







3

6

9

5

3

Конечные распознаватели

4







4

3

7

5

4

Магазинные распознаватели

3







3

3

6

5

5

Нисходящие распознаватели

4







4

3

7

5

6

Восходящие распознаватели

5







5

3

8

5

7

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

4







4

2

6

5

8

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

4







4

3

7

5

9

Магазинные преобразователи

5







5

3

8

5

10

Атрибутные грамматики

4







4

5

9

5

11

Атрибутные преобразователи

5







5

3

8

5

12

Программная реализация преобразователей

7







7

6

13

5

13

Переключательные функции

6







6

3

9

5

14

Минимизация переключательных функций

8







8

4

12

5

15

Полнота функциональных базисов

6







6

2

8

5

16

Аппаратная реализация преобразователей

8







8

4

12

5

17

Заключение

2







2




2

5

Курсовое проектирование










16

36

52

5

ИТОГО:

80




16

96

89

185

5



ЛИТЕРАТУРА


Основная

Название, библиографическое описание

Л
Кп

(р)
К-во экз. в библ. (на каф.)
Гриф
1
Ф.Льюис, Д.Розенкранц, Р.Стирнз. Теоретические основы построения компиляторов. М.: Мир, 1979. - 665 с.
5
5
0
2
А.Ахо, Р.Сати, Д. Ульман. Компиляторы: принципы, технологии и инструменты. Пер. с англ. – М.: Издательский дом «Вильямс», 2001. – 768 с.
5
5
26

уч.
3
Миллер Р. Теория переключательных схем. М.: Мир, 1970.
5
5
Т.1-6

Т.2-7
4
Фомичев В.С. Арифметические и логические основы вычислительной техники: Конспект лекций./ЛЭТИ. Л., 1973-1975. Вып.1. 1973; Вып.2. 1974; Вып.3. 1975; Вып.4. 1975.
5
5
В.1-280

В.2-0

В.3-301

В.4-263
5
Построение и анализ грамматик. Методические указания к лабораторным работам по дисциплине "Системное программирование" /СПб., ЛЭТИ, 1991. - 32 с.
5
15

(ч/з)
6
Магазинный распознаватель и преобразователь. Методические указания к лабораторным работам по дисциплине "Системное программирование" / СПб., ЭТУ, 1992. - 32 с.
5
100



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



Название, библиографическое описание
К-во экз. в библ. (на каф.)
1

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

т.1-31

т.2-20
2

T.Пратт., Зельковец М. Языки программирования: разработка и реализация. СПб.: Питер, 2001. – 674 с.

11
3

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

0
4

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

0
5

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

71
6

Фридман А., Менон П. Теория и проектирование переключательных схем. М.: Мир, 1978.

0
7

Кук Д., Бейз Г. Компьютерная математика. М.: Наука, 1990.

19
8

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988.

77




Автор:




д.т.н., профессор

Фомичев В.С.








Рецензент




к.т.н., доцент кафедры МОЭВМ

Самойленко В.П.







Зав. кафедрой

вычислительной техники




д.т.н., профессор

Пузанков Д.В.








Декан факультета

компьютерных технологий и информатики




д.т.н., профессор

Герасимов И.В.













^ Программа согласована:










Зав. кафедрой

вычислительной техники




д.т.н., профессор

Пузанков Д.В.














Зав. отделом учебной литературы

Киселева Т.В.







Председатель методической комиссии

факультета компьютерных технологий

и информатики




к.т.н., доцент

Чугунов Л.А.





Руководитель методического отдела




к.т.н., доцент

Марасина Л.А.












Скачать 152,15 Kb.
оставить комментарий
Дата29.09.2011
Размер152,15 Kb.
ТипРабочая программа, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх