Синтаксический анализ автоматных языков

Задача этого раздела - дать общую схему построения программ синтаксического анализа А-языков и привести примеры их реализации. В дальнейшем мы рассмотрим большую группу полезных свойств А-грамматик и А-языков, которые, конечно же, должны использоваться Вами на практике. Автор счел необходимым привести данный раздел как можно раньше, предваряя этот материал, с тем, чтобы Вы могли совмещать изучение теории и ее использование в практической работе на ЭВМ. В данном курсе она будет сводиться к разработке и отладке программ синтаксического анализа с элементами семантики для предложенных Вам языков. Описание вариантов языков дано в Приложении.

Блок-схема алгоритма и программа, анализирующая принадлежность цепочки заданному А-языку, строиться тривиально по графу состояний А-грамматики. Каждой вершине графа, кроме заключительной и “ошибочной”, соответствует блок выбора очередного символа анализируемой цепочки. Каждому ребру, точнее пометке ребра, блок анализа символа с последующим переходом к тому или иному блоку выбора. Каждому пути по графу соответствует путь по блок-схеме и программе. Рассмотрим несколько приемов построения таких программ на примере анализа числа, граф А-грамматики которого представлен на рис. 1.5 (б). В качестве языка программирования используется подмножество языка C.

Пример 1.10. Фрагмент анализатора с GO TO.

Оператор безусловного перехода goto не рекомендуется использовать при программировании. В свое время он даже отсутствовал в ряде языков и я здесь вовсе не собираюсь призвать Вас повсеместно его применять. Ниже будут приведены примеры реализации структурных программ анализа. Тем не менее, использование goto яснее всего отражает связь программы анализа и А-грамматики или графа состояний. Для того чтобы подчеркнуть эту связь, имена меток в приведенной ниже программе получены транслитерацией имен нетерминалов с рис. 1.5 (б).

.........

char s, str[100]; /* анализируемая строка */

int i;

.........

int analiz(void)

{ i=0;

chis: s=str[i]; if (s==‘+’ || s==‘-’) goto chbz;

if (s>=‘0’ && s<=‘9’) goto chbz1;

if (s==‘.’) goto dchp;

goto Osh;

chbz: i++; s=str[i];

if (s>=‘0’ && s<=‘9’) goto chbz1;

if (s==‘.’) goto dchp;

goto Osh;

chbz1:i++; s=str[i];

if (s>=‘0’ && s<=‘9’) goto chbz1;

if (s==‘.’) goto dchp1;

goto Osh;

dchp: i++; s=str[i];

if (s>=‘0’ && s<=‘9’) goto dchp1;

goto Osh;

dchp1:i++; s=str[i];

if (s>=‘0’ && s<=‘9’) goto dchp1;

if (s==‘E’) goto por;

if (s==‘;’) goto F;

goto Osh;

por: i++; s=str[i];

if (s==‘+’ || s==‘-’) goto pbz;

if (s>=‘0’ && s<=‘9’) goto pbz1;

goto Osh;

pbz: i++; s=str[i];

if (s>=‘0’ && s<=‘9’) goto pbz1;

goto Osh;

pbz1: i++; s=str[i];

if (s>=‘0’ && s<=‘9’) goto pbz1;

if (s==‘;’) goto F;

Osh: printf(“\n Цепочка не принадлежит языку \n”);

return 0;

F: printf(“\n Цепочка принадлежит языку \n”);

return 1; }

.........

В рассмотренном примере, кроме использования goto есть и еще один существенный недостаток,- не идентифицируются ошибки. •

Пример 1.11. Фрагмент анализатора с перечислимым типом и переключателем.

.........

enum State {chis, chbz, chbz1, dchp, dchp1, por, pbz, pbz1, osh, F} sta;

char s, str[100]; int i;

.........

int analiz(void)

{

i=0; sta=chis;

while (sta!= F && sta!= osh)

{

s=str[i]; i++;

switch (sta)

{

case chis: {

if (s==‘+’ || s==‘-’) sta=chbz;

else if (s>=‘0’ && s<=‘9’) sta=chbz1;

else if (s==‘.’) sta=dchp;

else { printf(“\n Ошибка в начале числа \n”); sta=osh; }

break; }

case chbz: {

if ((s>=‘0’ && s<=‘9’) sta=chbz1;

else if (s==‘.’) sta=dchp;

else { printf(“\n Ошибка в целой части числа \n”); sta=osh; }

break; }

case chbz1: {

if ((s>=‘0’ && s<=‘9’) sta=chbz1;

else if (s==‘.’) sta=dchp1;

else { printf(“\n Ошибка в конце целой части числа \n”); sta=osh; }

break; }

case dchp: {

if ((s>=‘0’ && s<=‘9’) sta=dchp1;

else { printf(“\n Ошибка в дробной части числа \n”); sta=osh; }

break; }

case dchp1: {

if ((s>=‘0’ && s<=‘9’) sta=dchp1;

else if (s==‘E’) sta=por;

else if (s==‘;’) sta=F;

else { printf(“\n Ошибка в конце дробной части числа \n”); sta=osh; }

break; }

case por: {

if (s==‘+’ || s==‘-’) sta=pbz;

else if (s>=‘0’ && s<=‘9’) sta=pbz1;

else { printf(“\n Ошибка в значении порядка числа \n”); sta=osh; }

break; }

case pbz: {

if ((s>=‘0’ && s<=‘9’) sta=pbz1;

else { printf(“\n Ошибка в значении порядка числа \n”); sta=osh; }

break; }

case pbz1: {

if ((s>=‘0’ && s<=‘9’) sta=pbz1;

else if (s==‘;’) sta=F;

else { printf(“\n Ошибка в конце числа \n”); sta=osh; }

break; }

}

}

if (sta==F) printf(“\n Число без ошибок \n”);

return (sta==F);

}

.........

Сообщения об ошибках здесь несколько расплывчаты, но это уже дело вкуса. •

Отметим, что синтаксический анализ в рамках транслятора не является самоцелью. Кроме синтаксиса надо помнить о семантике. В процессе синтаксического анализа в трансляторе осуществляется перевод, а точнее синтаксический анализатор управляет этим переводом. Для осуществления перевода цепочки А-языка, с каждым ребром графа состояний, точнее каждой пометкой ребра, каждым блоком программы анализа необходимо, в общем случае, связать некоторые семантические действия, семантические подпрограммы. Для нашего примера семантикой символьного представления числа естественно считать его значение.

Пример 1.12. Синтаксический анализатор числа с получением его значения.

#include<stdio.h>

double rez; /* результат */

char st[80]; /* анализируемая строка */

/* Процедура анализа цифры */

int Dig(char d)

{

return (d>=‘0’ && d<=‘9’);

}

/* Процедура анализа числа */

int RealNumber(double *r)

{

double c, /* текущее значение числа */

z, /* знак числа */

p, /* знак порядка */

g; /* текущий множитель для формирования дробной части */

int cd; /* признак наличия целой или дробной части */

int i, j; char s;

c=0; z=1; p=10; j=0; g=0.1; cd=0; i=0; s=st[i];

if (s==‘-’) { z=-1; s=st[++i]; } /* знак “- “*/

else if (s==‘+’) s=st[++i];

while (Dig(s)) { c=c*10+(s-48); cd=1; s=st[++i]; } /* формируем целую часть */

if (s!= ‘.’) return 1; /* нет “.” */ s=st[++i];

while (Dig(s)) { c=c+((s-48)*g); g=g*0.1; cd=1; s=st[++i]; } /* дробная часть */

if (s==‘E’)

{ s=st[++i];

if (s==‘-’) p=0.1; /* отрицательный порядок */

else

{ if (Dig(s)) j=s-48; /* первая цифра порядка */

else if (s!= ‘+’) return 2; /* не то, что надо после “E” */

}

s=st[++i]; while (Dig(s)) { j=j*10+(s-48); s=st[++i] } /* значение порядка */

}

if (s!= ‘;’) return 3; /* отсутствует; */

if (!cd) return 4; /* отсутствуют цифры в целой и дробной части */

c=c*z; for(i=0;i<j;i++) c=c*p; /* окончательное формирование числа */

*r=c; return 0; /* нормальное завершение */

}

main()

{ printf(“\n Тест анализатора действительного числа. Для завершения \n”);

printf(“тестирования на предложение ‘ввести число’ введите пустую строку \n”);

for (;;)

{ printf(“\n введите число \n”);

gets(st);

if (st[0] == ‘\0’) break; /* Строка пуста - конец теста */

switch (RealNumber(&rez))

{

case 0:

{ printf(“\n Успешная трансляция. Результат = %30.15f \n”, rez); break; }

case 1:

{ printf(“\n Ошибка, ожидается точка (‘.’). \n”); break; }

case 2:

{ printf(“\n Ошибка в значении порядка \n”); break; }

case 3:

{ printf(“\n Ошибка, ожидается ‘;’ \n”); break; }

case 4:

{ printf(“\n Ошибка, в числе отсутствуют целая и дробная части \n”); break; }

}

} return 0;

} •

Дата добавления: 2015-06-27