Лексический анализатор как конечный автомат
Формальной основой ЛА являются конечные автоматы (КА). КА является формальным математическим аппаратом, широко используемым в компьютерной технике. В проектировании аппаратных средств КА используются при разработке управляющей схемы, реализующей заданный алгоритм. Точно так же, в любой программе достаточно сложная логика последовательности действий может быть реализована как напрямую в виде последовательности условных и циклических конструкций, так и в виде программного КА. Для начала дадим неформальное определение КА.
КОНЕЧНЫМ АВТОМАТОМ является система, которая в каждый момент времени может находится в одном из конечного множества заданных состояний. Каждый шаг (переключение) автомата состоит в том, что при нахождении в определенном состоянии при поступлении на вход одного из множества входных сигналов (воздействий) он переходит в однозначно определенное состояние и вырабатывает определенное выходное воздействие. Легче всего представить себе поведение КА в виде его диаграммы состояний-переходов.
Таким образом, если поведение какого-либо объекта можно описать набором предложений вида: находясь в состоянии A, при получении сигнала S объект переходит в состояние B и при этом выполняет действие D - то такая система будет представлять из себя конечный автомат. На диаграмме состояний-переходов каждому состоянию соответствует кружок, каждому переходу - дуга со стрелкой. Каждое состояние имеет свой “смысл”, заключенный в подписи. Каждый переход осуществляется только при выполнении определенного условия, которое обозначено подписью под дугой. Кроме того, при выполнении перехода производится действие, при помощи которого автомат обнаруживает свое поведение извне.
У конечного автомата есть еще несколько условий работоспособности:
- автомат имеет некоторое начальное состояние, из которого он начинает работу;
- автомат имеет конечное число состояний;
в каждом состоянии не может быть одновременно справедливыми несколько условий перехода, то есть автомат должен быть ДЕТЕРМИНИРОВАННЫМ.
Автомат не может перейти одновременно в несколько состояний и не может иметь таких условий перехода.
О том, что конечный автомат может использоваться при анализе последовательностей различных символов в строке, несложно убедиться на простом примере. Пусть требуется написать программу, которая исключает из строки комментарии вида “ /* ... */ ”
Прежде всего, необходимо определить состояния конечного автомата. Таковыми являются состояния программы, возможные при просмотре очередного символа строки:
- состояние 0 - идет обычный текст;
- состояние 1 - обнаружен символ “/”;
- состояние 2 - обнаружено начало комментария “/*”;
- состояние 3 - в комментарии обнаружен символ “*”.
Программа, представляющая собой КА, будет выглядеть следующим образом:
void f(char in[],char out[])
{int i, s, j;
for(i=0,s=0,j=0; in[i]!=0; i++)
switch(s)
{
case 0: if (in[i])!=’/’ out[j++] = in[i];
else s=1;
break;
case 1: if (in[i]!=’*’)
{out[j++]=in[i-1]; out[j++]=in[i]; s=0;}
else s=2;
break;
case 2: if (in[i]==’*’) s=3;
break;
case 3: if (in[i]==’/’) s=0;
break;
}
}
Подробнее рассмотрим характерные особенности этой программы:
- программа представляет собой цикл, в каждом шаге которой анализируется очередной символ из входной строки. Заметим, что только текущий. Программа принципиально не анализирует ни предыдущих, ни последующих символов. Текущий символ играет, таким образом. Роль входного сигнала, по которому автомат переходит из одного состояния в другое.
- программа имеет переменную s, которая и представляет собой текущее состояние КА. В теле основного цикла программы выполняется переключение (switсh) по всем возможным значениям этой переменной - состояниям КА.
- в каждом состоянии реализуется логика его перехода в другие состояния на основе анализа текущего символа - входного сигнала и вырабатывается соответствующее действие. Например, в состоянии 1, когда программа уже обнаружила символ “/” - возможное начало комментария, она проверяет, не является ли текущий символ “*”.Если это так, автомат переводится в состояние 2 - нахождение внутри комментария, если нет, то в выходную строку переписывается предыдущий “/” и текущий символы, а автомат возвращается в состояние 0.
