Page 37 - 4761

Кінцевий автомат має наступні умови працездатності :
- має деякий початковий стан з якого починається робота;
- має скінчену кількість станів.
Для кожного стану не може бути одночасно справедливими кілька умов переходу.
Тобто автомат повинен бути детермінованим (кінцевий автомат не може перейти
одночасно в кілька станів і не може мати кілька таких умов переходу)
Приклад 3.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] =='*')
else s=3; break;
case 3: if(in[i] =='/')
else s=0; break;}
}
Наведена програма реалізовується на основі циклу, кожен крок якого аналізує
черговий символ із вхідного рядка. Аналізується тільки черговий символ без врахування
попередніх і наступних .Фактично черговий символ відіграє роль вхідного сигналу за
яким кінцевий автомат переходить з одного стану в інший . Змінна s представляє собою
поточний стан кінець автомату на основі мультиумовного оператора switch відбувається
переключеня (зміна) за всіма можливими значеннями (станами) кінцевого автомату. В
кожному з кінцевих станів (при аналізі поточного символу) реалізується логіка переходу
на основі на налізу вхідного сигналу згідно чого виконується відповідна дія. Наприклад
,якщо кінцевий автомат знаходиться в стані 1 (виявлено символ « / » ) – можливий
початок коментаря ,то перевірка поточного символа відбувається на наявність символа
«*». Якщо це так, то автомат переходить в стан 2 (вхід в середину коментаря). Якщо ні,то
у всіх рядок переписується попередній « / » і поточний символ ,а кінцевий автомат
скидається в нульовий стан.

Діаграма станів і переходів при лексичному аналізі
Найбільш зручно (для розуміння суті роботи кінцевого автомату) представляти
переходи з одного стану в інший у вигляді діаграми станів переходів. Кожному стану
автомату відповідає кожна дія (поведінка), яку потрібно виконувати, тобто якщо автомат
розпізнає константу як послідовність цифр, то в ньому необхідно передбачити стан, який
можна назвати як «очікування наступної цифри». Переключення автомату з одного стану

35