Для иллюстрации применения теории автоматов в этом направлении приведем граф переходов схемы управления обычных электронных часов [1]. Все функции часов реализуются конечным автоматом, который управляется кнопками на корпусе часов. Пусть для простоты автомат выполняет две функции: отображение даты и времени и их установку. Часы с двумя управляющими кнопками А и В приведены на рис. 3 а, граф переходов автомата – на рис. 3 б.
а
б
Рис. 3: а – электронные часы;
б – граф переходов управляющего автомата
Начальное состояние для данного автомата – состояние «Отображение времени». При нажатии кнопки А автомат переходит в состояние «Установка минут». Если сейчас нажать кнопку В, то к минутам прибавится единица, а состояние останется прежним. Нажатие кнопки А переводит автомат в состояние «Установка часов» и т. д.
Трансляция языков программирования. Другим традиционным применением теории автоматов является построение трансляторов для языков программирования – одна из самых важных областей системного программирования.
Известно, что транслятор (компилятор или интерпретатор) состоит из следующих основных частей: лексического анализатора, синтаксического анализатора, генератора кода (в интерпретаторе вместо генератора кода используется эмулятор) и анализатора ошибок (рис. 4) [10-12].
Рис. 4. Общая структурная схема транслятора
Лексический анализатор преобразует цепочку входных символов в цепочку лексем (элементарные конструкции языка, например, идентификатор, действительное число, комментарий). Синтаксический анализатор осуществляет распознавание цепочки лексем, семантический анализ и построение промежуточного представления. Генератор кода на основе промежуточного представления и системы команд конкретного компьютера вырабатывает объектный код. Анализатор ошибок, обрабатывая сообщения блоков транслятора об ошибках, выдает предупреждения пользователю, иногда пытаясь исправить ошибку самостоятельно.
Важнейшими частями лексического и синтаксического анализаторов являются распознаватели – алгоритмы, определяющие некоторое множество. Распознаватели реализуются автоматами. Рассмотрим структуру лексического анализатора (рис. 5).
Рис. 5. Лексический анализатор
Он включает в себя блок управления, n распознавателей – конечных автоматов и обработчик ошибок. Каждый конечный автомат распознает отдельную лексему. Автоматы соединены последовательно, поэтому в случае неудачи распознавания одним автоматом символ передается следующему.
Loading ...