Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 37 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

39
Множество цепочек, допускаемых конечным автоматом, составляет опре-
деляемый им язык.
Для более удобной работы с диаграммами состояний введем несколько со-
глашений:
если из одного состояния в другое выходит несколько дуг, помеченных
разными символами, то будем изображать одну дугу, помеченную всеми
этими символами;
непомеченная дуга будет соответствовать переходу при любом символе,
кроме тех, которыми помечены другие дуги, выходящие из этого состоя-
ния.
введем состояние ошибки (ER); переход в это состояние будет означать,
что исходная цепочка языку не принадлежит.
По диаграмме состояний легко написать анализатор для регулярной грам-
матики. Например, для грамматики G = ({a,b, ⊥}, {S,A,B,C}, P, S), где:
P: S → C⊥
С → Ab | Ba
A → a | Ca
B → b | Cb
анализатор будет таким:
#include <stdio.h>
int scan_G(){
enum state {H, A, B, C, S, ER}; // множество состояний
state CS; // CS - текущее состояние
FILE fp; // указатель на файл, в котором находится анализируемая цепочка
int c;
CS=H;
fp = fopen ("data","r");
c = fgetc (fp);
do {switch (CS) {
case H: if (c == 'a') {c = fgetc(fp); CS = A;}
else if (c == 'b') {c = fgetc(fp); CS = B;}
else CS = ER;
break;
case A: if (c == 'b') {c = fgetc(fp); CS = C;}
else CS = ER;
break;
case B: if (c == 'a') {c = fgetc(fp); CS = C;}
else CS = ER;
break;
case C: if (c =='a') {c = fgetc(fp); CS = A;}
else if (c == 'b') {c = fgetc(fp); CS = B;}
else if (c == '⊥') CS = S;
else CS = ER;
break;
}
} while (CS != S && CS != ER);
if (CS == ER) return -1; else return 0;
}

Страницы