Введение

Научное направление "Информатика" ориентировано в основном на разработку и реализацию моделей, которые могут быть представлены в памяти компьютера. Методы построения подобных моделей, составляют базу информационных технологий. Широкое использование моделей, основанных на конечных автоматах и формальных грамматиках, в теоретических исследованиях и при разработке систем, применяемых на практике, позволяет рассматривать дисциплину "Формальные языки, грамматики и автоматы" как одну из основных дисциплин направления "Информатика".

Главным назначением дисциплины "Формальные языки, грамматики и автоматы" является изучение основ теории, методов и приемов практического использования  аппарата формальных грамматик и конечных автоматов.

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

Дисциплина "Формальные языки, грамматики и автоматы" обеспечивает подготовку для изучения таких дисциплин, как "Построение компиляторов", "Элементы и узлы ЭВМ", "Автоматизация проектирования ЭВМ" и "Имитационное моделирование".

Для кого предназначен курс лекций

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

Что нужно знать для работы с курсом лекций

Приступая к изучению этой дисциплины, студенты должны знать содержание курсов "Основы алгоритмизации и программирования", "Структуры данных" и «Дискретная математика». Поскольку примеры в курсе лекций написаны на языке Java, желательно уметь программировать на этом языке или хотя бы знать особенности построения и основные конструкции языка.

Как работать с курсом лекций

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

• Глава 1 позволит вам познакомиться с основными понятиями дисциплины, такими как «язык», «формальная грамматика», «вывод» и научиться строить простейшие формальные грамматики.
• Чтобы научиться строить распознаватели, осуществляющие синтаксический контроль входного текста, следует ознакомиться с содержанием глав 1 и 3.
• Если вас интересуют вопросы трансляции, вам необходимо прочитать главы 1, 3, 4.
• Для тех, кто уже умеет строить преобразователи, но хочет научиться вводить в описание языка семантику и строить простейшие атрибутные преобразователи, предназначена глава 5.
• Программистов, работающих в области построения трансляторов, наверняка заинтересуют главы 6 и 7, в которых описан вариант реализации простейшего транслятора на языке Java.
• Специалистам, занимающимся разработкой логических схем устройств, будет интересна глава 8, а специалистам по аппаратной реализации автоматов главы 2 и 9.

Благодарности

Считаю приятным долгом выразить признательность за помощь в оформлении пособия студентам и аспирантам СПбГЭТУ (ЛЭТИ): Татьяне  Карасевой, Светлане Новиковой, Алексею Лапшину,  Тарасу Щепину, Денису Степанову, Сергею Савицкому, Дмитрию Москвину, Алексею Дайтеру, Кириллу Широкову. Особенно хочу поблагодарить мою жену Татьяну и дочь Настю, без помощи которых эта работа, наверное никогда не была бы завершена.

Буду весьма признателен читателям за указание на возможные ошибки и неточности, а также прочие недостатки, которые удастся обнаружить в тексте лекций. Со мной можно связаться по электронной почте по адресу: vsfomichev@yandex.ru

05.10.2006
Владимир Степанович Фомичев

Содержание