-
Название работы: «Лексика языков программирования. Конечные автоматы без памяти для обнаружения слов в тексте программы».
-
Цели работы: изучение конечных автоматов (КА) без памяти, способов определения КА в трансляторах – графового и табличного, методов построения недетерминированного КА по системе регулярных выражений, методов эквивалентных преобразований недетерминированных КА в оптимальные полностью определенные КА – лексические акцепторы.
-
Основные теоретические сведения:
-
Конечные автоматы без памяти
Конечный автомат без памяти есть совокупность
K = {A, C, С0, G, F},
где
A – алфавит входных символов;
C – конечное множество состояний;
С0 – начальное состояние;
G – функция переходов, которая по текущему состоянию автомата и входному символу формирует его состояние в следующий момент времени;
F – конечное множество состояний останова (финальных состояний).
Применительно к программной реализации в трансляторах конечным автоматом без памяти называется математическая модель устройства, которое:
-
имеет определенный набор рабочих состояний C, среди которых выделено особое начальное (стартовое) состояние С0 и некоторый набор состояний останова (финальных состояний)F;
-
имеет один вход и не имеет ни одного выхода;
-
в любой момент времени на входе имеет либо в точности один символ входного алфавита A, либо пустую цепочку ε;
-
функционирует в дискретном времени t0, t1, t2, ...;
-
при запуске, т. е. в момент времени t0, всегда оказывается в начальном состоянии С0, на входе в этот момент находится самый первый символ входной цепочки;
-
в любой момент времени ti по текущему состоянию и символу, находящемуся на входе, в соответствии с функцией G определяет номер рабочего или финального состояния, в котором автомат окажется в момент времени ti+1;
-
если по каким-либо причинам номер следующего состояния не может быть определен, то автомат останавливается по ошибке (для остановов по ошибке подразумевается существование особого финального состояния, не принадлежащего множеству F);
-
при любом переходе в рабочее состояние или состояние останова по ошибке текущий входной символ заменяется следующим символом из входной цепочки;
-
при переходе в финальное состояние обнаружения правильного слова входной символ автомата не изменяется (такой переход выполняется по пустой цепочке ε; действия со входным символом при переходе по пустой цепочке состоят в чтении символа со входа + обнаружении того, что символ не принадлежит текущему слову + возврате этого символа на вход автомата);
-
каждому финальному состоянию, не являющемуся состоянием останова по ошибке, поставлена в соответствие группа правильных слов, возможно, не единственная; останов автомата в таком состоянии понимается как обнаружение им правильного слова этой группы (или слова, принадлежащего нескольким группам).
Пусть требуется решить задачу распознавания двоичных чисел, разделенных последовательностями пробелов. Простая система регулярных определений может описать слова этих двух групп:
BinaryNumber : [01] +
Space : [ ] +
Существует как минимум три способа определения конечного автомата без памяти, способного распознавать такие слова.
-
Конечный автомат без памяти может быть задан только функцией переходов, если соблюдаются определенные соглашения о способе нумерации состояний (начальным является состояние номер 0):
{текущее состояние; входной символ; следующее состояние}
Пример такого определения автомата:{0,ε,-1} {0,\d32,1} {0,0,2} {0,1,2} {1,\d32,1} {1, ε,-2} {2,0,2} {2,1,2} {2,ε,-3}Алфавит входных символов может быть извлечен из функции переходов, это символы
0,
1, пробел (символ с десятичным кодом
\d32). Любые другие символы, которые могут появиться на входе автомата, здесь обозначены пустой цепочкой
ε, их обработка состоит в переходе автомата в финальные состояния
.Состояния
0, 1 и
2 являются рабочими, поскольку для них определены переходы в другие состояния по входным символам. Состояния
-1,
-2 и
-3 – финальные, поскольку из них не существует ни одного перехода. Состояние
-1 соответствует обнаружению конца цепочки символов, содержащей только правильные слова, т.е. двоичные числа и последовательности пробелов. Останов автомата в состоянии
-2 означает обнаружение последовательности пробелов, а в состоянии
-3 – обнаружение двоичного числа.
При программной реализации конечные автоматы без памяти обычно представляются либо графами состояний и переходов, либо управляющими таблицами.
-
Графом состояний и переходов (ГСП) конечного автомата без памяти (далее просто конечного автомата - КА) называется помеченный ориентированный граф, вершины которого сопоставлены состояниям, а дуги – переходам.
Разметка вершин обычно производится целыми числами, обозначающими номера состояний. Имеется особая начальная вершина (имеющая обычно номер 0), в которую не входит ни одна дуга. Дуги графа могут быть помечены обозначением пустой цепочки ε, одиночным символом, перечнем или диапазоном символов.
Существуют особые финальные вершины, из которых не может выходить ни одна дуга. Имеется одна или несколько рабочих вершин, в которые могут входить дуги и из которых могут выходить дуги.
Пример списка состояний
и переходов конечного автомата,распознающего двоичные числа и последовательности пробелов в представлении, формируемом ВебТрансБилдером:
0:
|
|
EOF-> -1 [\d32] -> 1 [01]-> 2
|
1:
|
|
[other]-> -2 [\d32] -> 1
|
2:
|
|
[other]-> -3 [01]-> 2
|
Разметка
дуг графа производится с помощью указания одного из символов входного алфавита того языка, для распознавания слов которого построен данный автомат либо обозначения пустой цепочки символов ε, которому здесь соответствует [
other]. Это обозначение надо понимать так: любой символ, не принадлежащий разметке какой-либо дуги, выходящей из данного состояния. Поэтому в разных состояниях [
other] обозначают разные множества символов. Для состояния
1 это не пробел, а для состояния
2 – любой символ кроме двоичных цифр. Если дуга помечена символом входного алфавита, то при переходе по этой дуге автомат заменяет данный входной символ следующим символом из входной цепочки. При переходе по дуге, помеченной обозначением пустой цепочки ε, символ на входе автомата не изменяется.
-
Еще одним способом определения конечного автомата без памяти является табличный способ. Автомат задается прямоугольной таблицей, строки которой обычно соответствуют состояниям, а столбцы – входным символам. Номера состояний и входные символы показаны в заголовках строк и столбцов, однако следует помнить, что заголовки строк и столбцов не являются элементами таблицы. В клетках таблицы указываются номера состояний перехода (из состояния, в строке которого находится клетка по символу, указанному в заголовке столбца). Пример управляющей таблицы (УТ) автомата, предназначенного для акцепта двоичных чисел, формируемой пакетом ВебТрансБилдер показан в табл. 2.1.
Таблица 2.1
|
|
|
|
|
0
|
1
|
2
|
[ ► ]
|
-1
|
-2
|
-3
|
[ \d32 ]
|
1
|
1
|
-3
|
[ 01 ]
|
2
|
-2
|
2
|