Семантический анализатор для М-языка
Контекстные условия, выполнение которых нам надо контролировать в программах на М-языке, таковы:
2) Любое имя, используемое в программе, должно быть описано и только один раз.
3) В операторе присваивания типы переменной и выражения должны совпадать.
4) В условном операторе и в операторе цикла в качестве условия возможно только логическое выражение.
5) Операнды операции отношения должны быть целочисленными.
6) Тип выражения и совместимость типов операндов в выражении определяются по обычным правилам (как в Паскале).
Проверку контекстных условий совместим с синтаксическим анализом. Для этого в синтаксические правила вставим вызовы процедур, осуществляющих необходимый контроль, а затем перенесем их в процедуры рекурсивного спуска.
Обработка описаний
Для контроля согласованности типов в выражениях и типов выражений в операторах, необходимо знать типы переменных, входящих в эти выражения. Кроме того, нужно проверять, нет ли повторных описаний идентификаторов. Эта информация становится известной в тот момент, когда синтаксический анализатор обрабатывает описания. Следовательно, в синтаксические правила для описаний нужно вставить действия, с помощью которых будем запоминать типы переменных и контролировать единственность их описания.
Лексический анализатор запомнил в таблице идентификаторов 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.
С учетом этих функций правило вывода с действиями для обработки описаний будет таким:
D ® < ipush (-1) > I < ipush (curr_lex.value) >
{, I < ipush (curr_lex.value) >}:
[ int < dec ("int") > | bool < dec ("bool") > ]
Контроль контекстных условий в выражении
Пусть есть функция
char *gettype (char *op, char *t1, char *t2),
которая проверяет допустимость сочетания операндов типа t1 (первый операнд) и типа t2 (второй операнд) в операции op; если типы совместимы, то выдает тип результата этой операции; иначе - строку "no".
Типы операндов и обозначение операции будем хранить в стеке; для этого нам нужны функции для работы со стеком строк:
void spush (char *s); /* значение s - в стек */
char *spop (void); /* из стека - строку */
Если в выражении встречается лексема-целое_число или логические константы true или false, то соответствующий тип сразу заносим в стек с помощью spush("int") или spush("bool").
|
|
Если операнд - лексема-переменная, то необходимо проверить, описана ли она; если описана, то ее тип надо занести в стек. Эти действия можно выполнить с помощью функции checkid:
void checkid (void)
{int i;
i = curr_lex.value;
if (TID [i].declare) /* описан? */
spush (TID [i].type); /* тип - в стек */
else ERROR(); /* описание отсутствует */
}
Тогда для контроля контекстных условий каждой тройки - "операнд-операция-операнд" будем использовать функцию checkop:
void checkop (void)
{char *op;
char *t1;char *t2;
char *res;
t2 = spop(); /* из стека - тип второго операнда */
op = spop(); /* из стека - обозначение операции */
t1 = spop(); /* из стека - тип первого операнда */
res = gettype (op,t1,t2); /* допустимо ? */
if (strcmp (res, "no")) spush (res); /* да! */
else ERROR(); /* нет! */
}
Для контроля за типом операнда одноместной операции not будем использовать функцию checknot:
void checknot (void)
{ if (strcmp (spop (), "bool")) ERROR();
else spush ("bool");}
Теперь главный вопрос: когда вызывать эти функции?
В грамматике модельного языка задано старшинство операций: наивысший приоритет имеет операция отрицания, затем в порядке убывания приоритета - группа операций умножения (*, /, and), группа операций сложения (+,-,or), операции отношения.
E ® E1 | E1 [ = | < | > ] E1
|
|
E1 ® T {[ + | - | or ] T}
T ® F {[ * | / | and ] F}
F ® I | N | [ true | false ] | not F | (E)
Именно это свойство грамматики позволит провести синтаксически-управляемый контроль контекстных условий.
Замечание: сравните грамматики, описывающие выражения, состоящие из символов +, *, (, ), i:
G1: E ® E+E | E*E | (E) | i G4: E ® T | E+T
G2: E ® E+T | E*T | T T ® F | T*F
T ® i | (E) F ® i | (E)
G3: E ® T+E | T*E | T G5: E ® T | T+E
T ® i |(E) T ® F | F*T
F ® i | (E)
оцените, насколько они удобны для трансляции выражений.
Правила вывода выражений модельного языка с действиями для контроля контекстных условий:
E ® E1 | E1 [ = | < | > ] < spush ( TD [curr_lex.value] ) > E1 <checkop() >
E1 ® T { [ + | - | or ] < spush ( TD [curr_lex.value] ) > T < checkop() >}
T ® F { [ * | / | and ] < spush ( TD [curr_lex.value] ) > F < checkop() >}
F ® I < checkid() > | N < spush ("int") > | [ true | false ] < spush ("bool") > |
not F < checknot() > | (E)
Замечание: TD - это таблица ограничителей, к которым относятся и знаки операций; будем считать, что это массив
#define MAXSIZE_TD 50
char * TD[MAXSIZE_TD];
именно из этой таблицы по номеру лексемы в классе выбираем обозначение операции в виде строки.
Дата добавления: 2018-10-27; просмотров: 225; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!