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
 Владимир Степанович Фомичев

 

                                       

                                           Содержание