1.
Введение
Научное направление "Информатика" ориентировано в основном на разработку и реализацию моделей, которые могут быть представлены в памяти компьютера. Методы построения подобных моделей, составляют базу информационных технологий. Широкое использование моделей, основанных на конечных автоматах и формальных грамматиках, в теоретических исследованиях и при разработке систем, применяемых на практике, позволяет рассматривать дисциплину "Формальные языки, грамматики и автоматы" как одну из основных дисциплин направления "Информатика".
Главным назначением дисциплины "Формальные языки,
грамматики и автоматы" является изучение основ теории, методов и приемов
практического использования аппарата формальных грамматик и конечных автоматов.
Особенностью материала, изложенного в курсе лекций,
является то, что один и тот же аппарат, а именно аппарат формальных грамматик,
используется для описания и построения как программных, так и аппаратных
средств. На нем базируются как методы программной реализации преобразователей,
так и методы аппаратной реализации автоматов и логических схем устройств.
Дисциплина "Формальные языки,
грамматики и автоматы" обеспечивает подготовку для изучения таких
дисциплин, как "Построение компиляторов", "Элементы и узлы
ЭВМ", "Автоматизация проектирования ЭВМ" и "Имитационное
моделирование".
2.
Для кого
предназначен курс лекций
Курс лекций ориентирован, в первую очередь, на студентов,
обучающихся по направлению «Информатика и вычислительная техника». Кроме того,
он может быть полезен студентам других направлений и специальностей, связанных
с разработкой программных и аппаратных средств, а также программистам,
работающим в области разработки трансляторов, и инженерам, разрабатывающим
логические схемы устройств.
3.
Что нужно знать
для рабы с курсом лекций
Приступая к изучению этой дисциплины, студенты должны
знать содержание курсов "Основы алгоритмизации и программирования",
"Структуры данных" и «Дискретная математика». Поскольку примеры в курсе лекций написаны на
языке Java, желательно уметь программировать на этом языке или хотя бы знать особенности построения и
основные конструкции языка.
4.
Как работать с
курсом лекций
Для получения полного представления о дисциплине
желательно читать лекции последовательно, однако, в зависимости от интересов
возможно и частичное изучение материала.
Глава 1 позволит вам познакомиться с основными понятиями
дисциплины, такими как «язык», «формальная грамматика», «вывод» и научиться
строить простейшие формальные грамматики.
Чтобы научиться строить распознаватели, осуществляющие
синтаксический контроль входного текста, следует ознакомиться с содержанием
глав 1 и 3.
Если вас интересуют вопросы трансляции, вам необходимо
прочитать главы 1, 3, 4.
Для тех, кто уже умеет строить преобразователи, но хочет
научиться вводить в описание языка семантику и строить простейшие атрибутные
преобразователи, предназначена глава 5.
Программистов, работающих в области построения
трансляторов, наверняка заинтересуют главы 6 и 7, в которых описан вариант
реализации простейшего транслятора на
языке Java/
Специалистам, занимающимся разработкой логических
схем устройств, будет интересна глава 8,
а специалистам по аппаратной реализации
автоматов главы 2 и 9.
5.
Благодарности
Считаю приятным долгом выразить признательность за помощь в оформлении пособия студентам и аспирантам СПбГЭТУ (ЛЭТИ): Татьяне Карасевой, Светлане Новиковой, Алексею Лапшину, Тарасу Щепину, Денису Степанову, Сергею Савицкому, Дмитрию Москвину, Алексею Дайтеру, Кириллу Широкову. Особенно хочу поблагодарить мою жену Татьяну и дочь Настю, без помощи которых эта работа, наверное никогда не была бы завершена.
Буду весьма признателен читателям за указание на возможные ошибки и неточности, а также прочие недостатки, которые удастся обнаружить в тексте лекций. Со мной можно связаться по электронной почте по адресу: vsfomichev@www.eltech.ru.
05.10.2006
Владимир Степанович Фомичев