WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Министерство образования Российской Федерации Санкт-Петербургский государственный электротехнический университет “ЛЭТИ” РАБОЧАЯ ПРОГРАММА дисциплины Языки, грамматики и автоматы Для подготовки бакалавров по направлению 552800 - “Информатика и вычислительная техника” Санкт-Петербург 2002 2 Санкт-Петербургский государственный электротехнический университет “ЛЭТИ” “УТВЕРЖДАЮ” Проректор по учебной работе проф. _ Ушаков В.Н.

“_”_2002 г.

РАБОЧАЯ ПРОГРАММА дисциплины Языки, грамматики и автоматы Для подготовки бакалавров по направлению 552800 - “Информатика и вычислительная техника” Факультет компьютерных технологий и информатики Кафедра Вычислительной техники Курс 3 Семестр 5 Лекции 80 ч. Экзамен семестр 5 Курсовое проектирование 16 ч.

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

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

Всего часов 185 ч.

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

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

1)Дискретная математика 2)Программирование 3)Организация ЭВМ и систем Рабочая программа одобрена методической комиссией факультета компьютерных технологий и информатики “”_2002г.

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

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

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

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

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

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

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

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

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

Эквивалентные и неоднозначные грамматики. Типы грамматик и языков. Автоматные грамматики. Контекстно-свободные грамматики. Неукорачивающие грамматики.

Исключение цепных и леворекурсивных правил.

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

Тема 4. Магазинные распознаватели Определение магазинного автомата. Работа магазинного автомата.

Детерминированные и недетерминированные автоматы. Расширенные автоматы.Тема Нисходящие распознаватели Работа детерминированного распознавателя. Разделенные грамматики. Функции ПЕРВ и СЛЕД. Определение слаборазделенных и 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 2 Определение и типы грамматик и 3 3 6 9 языков 3 Конечные распознаватели 4 4 3 7 4 Магазинные распознаватели 3 3 3 6 5 Нисходящие распознаватели 4 4 3 7 6 Восходящие распознаватели 5 5 3 8 7 Способы описания перевода 4 4 2 6 8 Конечные преобразователи 4 4 3 7 9 Магазинные преобразователи 5 5 3 8 10 Атрибутные грамматики 4 4 5 9 11 Атрибутные преобразователи 5 5 3 8 12 Программная реализация 7 7 6 13 преобразователей 13 Переключательные функции 6 6 3 9 14 Минимизация переключательных 8 8 4 12 функций 15 Полнота функциональных 6 6 2 8 базисов 16 Аппаратная реализация 8 8 4 12 преобразователей 17 Заключение 2 2 2 Курсовое проектирование 16 36 52 ИТОГО: 80 16 96 89 185 ЛИТЕРАТУРА Основная К-во экз. в Кп Л библ.

№ Название, библиографическое описание Гриф (р) (на каф.) 1 Ф.Льюис, Д.Розенкранц, Р.Стирнз. Теоретические основы 5 5 построения компиляторов. М.: Мир, 1979. - 665 с.

2 А.Ахо, Р.Сати, Д. Ульман. Компиляторы: принципы, технологии и инструменты. Пер. с англ. – М.: Издательский 5 уч.

дом «Вильямс», 2001. – 768 с.

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

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

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

6 Магазинный распознаватель и преобразователь.

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

Дополнительная К-во экз.

в библ.

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

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

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

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

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

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

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

Автор:

д.т.н., профессор Фомичев В.С.

Рецензент к.т.н., доцент кафедры МОЭВМ Самойленко В.П.

Зав. кафедрой вычислительной техники д.т.н., профессор Пузанков Д.В.

Декан факультета компьютерных технологий и информатики д.т.н., профессор Герасимов И.В.

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

Зав. кафедрой вычислительной техники д.т.н., профессор Пузанков Д.В.

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

Председатель методической комиссии факультета компьютерных технологий и информатики к.т.н., доцент Чугунов Л.А.

Руководитель методического отдела к.т.н., доцент Марасина Л.А.











© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.