A ® a <D1 >B<D1; D2 > | bC <D3 > , здесь A, D, C Î VN; a, b Î VT;
<Di> означает вызов семантической процедуры Di, i = 1, 2, 3.
Имея такое правило грамматики, легко написать процедуру для метода рекурсивного спуска, которая будет выполнять синтаксический анализ и некоторые дополнительные действия:
void A() {
if (c=='a') {c = fgetc(fp); D1(); B(); D1(); D2();}
else if (c == 'b') {c = fgetc(fp); C(); D3();}
else ERROR();
}
Написать грамматику, которая позволит распознавать цепочки языка
L = {a Î (0,1)+^ | a содержит равное количество 0 и 1}.
Этого можно добиться, пытаясь чисто синтаксическими средствами описать цепочки, обладающие этим свойством. Но гораздо проще с помощью синтаксических правил описать произвольные цепочки из 0 и 1, а потом вставить действия для отбора цепочек с равным количеством 0 и 1:
S ® <k0 = 0; k1 = 0;> A^
A ® 0<k0 = k0+1>A | 1<k1 = k1+1>A |
0<k0 = k0+1; check()> | 1<k1 = k1+1; check()>, где
void check()
{if (k0 != k1) { printf("ERROR !!!"); exit(1);}
else { printf("SUCCESS !!!");exit(0);}
}
Теперь по этой грамматике легко построить анализатор, распознающий цепочки с нужными свойствами.
Контекстные условия, выполнение которых нам надо контролировать в программах на М-языке, таковы:
- любое имя, используемое в программе, должно быть описано и только один раз;
- в операторе присваивания типы переменной и выражения должны совпадать;
- в условном операторе и в операторе цикла в качестве условия возможно только логическое выражение;
- операнды операции отношения должны быть целочисленными;
- тип выражения и совместимость типов операндов в выражении определяются по обычным правилам (как в Паскале).
Проверку контекстных условий совместим с синтаксическим анализом. Для этого в синтаксические правила вставим вызовы процедур, осуществляющих необходимый контроль, а затем перенесем их в процедуры рекурсивного спуска.
Для контроля согласованности типов в выражениях и типов выражений в операторах, необходимо знать типы переменных, входящих в эти выражения. Кроме того, нужно проверять, нет ли повторных описаний идентификаторов. Эта информация становится известной в тот момент, когда синтаксический анализатор обрабатывает описания. Следовательно, в синтаксические правила для описаний нужно вставить действия, с помощью которых будем запоминать типы переменных и контролировать единственность их описания.
Лексический анализатор запомнил в таблице идентификаторов TID все идентификаторы-лексемы, которые были им обнаружены в тексте исходной программы. Информацию о типе переменных и о наличии их описания естественно заносить в ту же таблицу.
Пусть каждая строка в TID имеет вид
struct record {
char *name; /* идентификатор */
int declare; /* описан ? 1-"да", 0-"нет" */
char *type; /* тип переменной */
...
};
Тогда таблица идентификаторов TID - это массив структур
#define MAXSIZE_TID 1000
struct record TID [MAXSIZE_TID];
причем i-я строка соответствует идентификатору-лексеме вида (4, i).
Лексический анализатор заполнил поле name; значения полей declare и type будем заполнять на этапе семантического анализа.
Для этого нам потребуется следующая функция:
void decid (int i, char *t) - в i-той строке таблицы TID контролирует и заполняет поле declare и, если лексема (4,i) впервые встретилась в разделе описаний, заполняет поле type:
void decid (int i, char *t)
{if (TID [i].declare) ERROR(); /*повторное описание */
else {TID [i].declare = 1; /* описан ! */
strcpy (TID [i].type, t);} /* тип t ! */
}
Раздел описаний имеет вид
D ® I {,I}: [int | bool],
то есть имени типа (int или bool) предшествует список идентификаторов. Эти идентификаторы (вернее, номера соответствующих им строк таблицы TID) надо запоминать (например, в стеке), а когда будет проанализировано имя типа, заполнить поля declare и type в этих строках.
Для этого будем использовать функции работы со стеком целых чисел:
void ipush (int i); /* значение i - в стек */
int ipop (void); /* из стека - целое */
Будем считать, что (-1) - "дно" стека; тогда функция
void dec (char *t)
{int i;
while ((i = ipop()) != -1)
decid(i,t);
}
считывает из стека номера строк TID и заносит в них информацию о наличии описания и о типе t.
С учетом этих функций правило вывода с действиями для обработки описаний будет таким:
