1.4. Представление а - грамматики в виде графа состояний.
Недетерминированные и детерминированные А - грамматики
Наглядным способом представления А-грамматики является граф состояний (переходов). Вершины этого графа соответствуют нетерминалам и из вершины A в вершину B проводится дуга, помеченная терминалом a, если в грамматике существует правило
A aB.
Добавим еще одну дополнительную заключительную вершину F и проведем дуги
если в грамматике присутствует заключительное правило A b, а само это правило будем записывать A bF, получив тем самым модифицированную А-грамматику.
Заметим, что каждому выводу в А-грамматике будет соответствовать путь по графу состояний из начальной вершины S в вершину F. Граф А-грамматики действительного числа из примера 1.9 представлен на рисунке 1.5 (a).
А-грамматика числа, рассмотренная в примере 1.9, является недетерминированной, то есть в ней существует такой нетерминал A и терминал a, для которых существует несколько нетерминалов B, таких что выполняются правила A aB. Например, модифицированная А-грамматика числа, что отчетливо видно на рис. 5.1 (а), содержит правила чбз . дчп и чбз .F или дчп 0 дчп и дчп 0F. Это нежелательно с точки зрения построения программ синтаксического анализа.
А-грамматика называется детерминированной, если для любого A (A F) и любого a существует не более одного B , для которого выполняется правило A aB.
А-грамматика называется вполне детерминированной, если для любого A (A F) и любого a существует единственное B , для которого выполняется правило A aB.
В разделе 3 будет показано, что любую недетерминированную А-грамматику можно свести к детерминированной. Пока же, для того чтобы перейти к реализации программ синтаксического анализа А-языков, что является основной частью лабораторных работ на ЭВМ в данной части курса, отметим, что на практике всегда используется специальный символ - ограничитель цепочки. Это либо нулевой байт, либо символ конца файла и т.п.
Если, например, считать, что число из примера 1.9 завершается символом “;”, то детерминированная А-грамматика числа строится элементарно. Граф состояний для этого случая представлен на рис. 1.5 (б). Нетерминалы чбз1 , дчп1 , пбз1 добавлены здесь для того, чтобы исключить возможность формирования числа без целой и дробной части и без числа порядка после символа ”E”. Вполне детерминированная форма должна включать, кроме того “ошибочный” нетерминал < Ош > и правила типа чбз + Ош или дчп . Ош и т.п. То есть для тех A (A F) и a , для которых в модифицированной детерминированной А-грамматике нет правил A aB, необходимо для формирования вполне детерминированной формы добавить правила A aE, где E <Ош> - “ошибочная” вершина.
1.5. Синтаксический анализ автоматных языков
Задача этого раздела - дать общую схему построения программ синтаксического анализа А-языков и привести примеры их реализации. В дальнейшем мы рассмотрим большую группу полезных свойств А-грамматик и А-языков, которые, конечно же, должны использоваться Вами на практике. Автор счел необходимым привести данный раздел как можно раньше, предваряя этот материал, с тем, чтобы Вы могли совмещать изучение теории и ее использование в практической работе на ЭВМ. В данном курсе она будет сводиться к разработке и отладке программ синтаксического анализа с элементами семантики для предложенных Вам языков. Описание вариантов языков дано в Приложении.
Блок-схема алгоритма и программа, анализирующая принадлежность цепочки заданному А-языку, строиться тривиально по графу состояний А-грамматики. Каждой вершине графа, кроме заключительной и “ошибочной”, соответствует блок выбора очередного символа анализируемой цепочки. Каждому ребру, точнее пометке ребра, блок анализа символа с последующим переходом к тому или иному блоку выбора. Каждому пути по графу соответствует путь по блок-схеме и программе. Рассмотрим несколько приемов построения таких программ на примере анализа числа, граф А-грамматики которого представлен на рис. 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;
}
Упражнения.
1.1. Дайте определение грамматике. Перечислите классы грамматик по Хомскому и дайте их определения. Как определить, содержит ли язык, порождаемый грамматикой, бесконечное число цепочек?
1.2. Что общего в А- и КС- грамматиках? Какие грамматики являются частным случаем других грамматик?
1.3. Постройте КС- и А- грамматики для цепочек вида x n y m z k, где n,k 0 и m 0. Покажите деревья вывода цепочк xxxyyz, xxzzz и xyz по полученной КС-грамматике.
1.4. Приведите граф состояний для A-грамматики из упр. 1.3. Введите признак конца цепочки, например символ “;”, и преобразуйте граф к детерминированной форме. Напишите программу синтаксического анализа цепочек x n y m z k, в качестве семантики подсчитайте количество x, y и z.
1.5. Постройте КС-грамматику, A-грамматику и граф состояний для цепочек состоящих из одного или нескольких, идущих без разделения блоков. Каждый блок начинается с единственной буквы и содержит в качестве продолжения от одной до трех цифр.
1.6. Постройте КС-грамматику для цепочек, инвариантных относительно симметричного поворота, т.е. цепочек, которые слева и справа читаются одинаково. Терминалами считайте буквы русского алфавита. Покажите деревья вывода для цепочек а, бб, казак, шалаш, анна. Подчеркните тот факт, что других цепочек, типа дом, он по вашей грамматике получить нельзя.
1.7. Постройте КС-грамматику, детерминированную А-грамматику и граф состояний для языка индексов ФОРТРАНа. При построении грамматики терминалами считать { a b c ...y z 0 1 2...8 9 ( ) + - }. Индексы ФОРТРАНа - это ограниченное арифметическое выражение, заключенное в круглые скобки. Ниже перечислены все возможные варианты этих индексов: (И) (К) (К*И) (И+К) (И-К) (К*И+К) (К*И-К), где И - идентификатор, а К - целая константа без знака.
1.8. Напишите процедуру анализа идентификатора с предупреждением в случае, когда количество символов в нем больше шести; процедуру анализа целой константы без знака с преобразованием символьного представления в число и предупреждением о переполнении (максимальное значение - 65535). Используя эти процедуры, напишите по А-грамматике программу анализа индексов ФОРТРАНа из упражнения 1.7.
1.9. Постройте КС - грамматики для цепочек ( n 0, m 0 )
(а) x n y n z m,
(б) x m y n z n,
(в) x n y m z n.
1.10. Постройте КС - грамматики для следующих цепочек в бинарном алфавите ({0,1}, n, m 0 ):
(a) 0 n 1 m 0 m 1 n;
(б) aR, где - любая цепочка из нулей и единиц, а R - обращение (симметричный поворот) цепочки ;
(в) 0 n 1 2n+3;
(г) всех цепочек, содержащих равное количество нулей и единиц;
(д) всех цепочек, содержащих равное количество нулей и единиц и такие, у которых количество нулей в каждой левой подцепочке не меньше чем единиц;
(е) 1n0m1p, где n+p>m>0.
1.11. Опишите языки, порождаемые следующими грамматиками с начальным нетерминалом S:
(a) S 10S0 S aA
A bA A a
(б) S SS S 1A0
A 1A0 A
(в) S 1A S B0
A 1A A C
B B0 B C
C 1C0 C
(г) S aSS S a
(д) S bADc D Gl
A aGs G
1.12. Какие из приведенных ниже цепочек можно вывести в данной грамматике? В каждом случае постройте левый вывод, правый вывод и дерево вывода.
S aAcB S BdS
B aScA B cAB
A BaB A aBc
A a B b
(a) aacb
(б) aaacbdaacb
(в) aabcbd
(г) acabaaaacbcacb
(д) aaaaacbcacccab
1.13. (а) Найдите КС-грамматику для логических выражений, составленных из логических переменных, констант, скобок и знаков операций отрицания (), дизъюнкции () и конъюнкции (). Приоритеты обычные: выполняется перед , а - перед .
(б) Добавьте к указанному языку первичные логические выражения, каждое из которых представляет собой арифметическое выражение, за которым следует знак отношения ( ) и еще одно арифметическое выражение, и постройте соответствующую грамматику.
1.14. Постройте КС-грамматику оператора FORMAT языка ФОРТРАН, ограничиваясь форматами A, X, I, F. Примеры правильных цепочек:
10 FORMAT(I5)
100 FORMAT (X10,A5,3A4,I6,4(I3,X2,5(F8.3,X4,3A2,I6),X2,2(3A3,I4)),I7)