Курс Основы построения трансляторов


Лексический анализатор как конечный автомат - часть 2


Автомат не может перейти одновременно в несколько состояний и не может иметь таких условий перехода.

О том, что конечный автомат может использоваться при анализе последовательностей различных символов в строке, несложно убедиться на простом примере. Пусть требуется написать программу, которая исключает из строки комментарии вида “ /* ... */ ”

Прежде всего, необходимо определить состояния конечного автомата. Таковыми являются состояния программы, возможные при просмотре очередного символа строки:

- состояние 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.

   




Начало  Назад  Вперед



Книжный магазин