Синтаксический анализатор выражений
Полный простой синтаксический анализатор рекурсивного спуска для целых числовых выражений включает в себя ряд функций. Вы должны взять тексты этих функций и сохранить их в своем файле (когда тексты анализатора и интерпретатора объединятся получится довольно большой файл, поэтому рекомендуется откомпилировать файлы отдельно). Смысл использования глобальных переменных будет кратко описан, в процессе обсуждения интерпретатора.
Исходный текст простейшего синтаксического анализатора рекурсивного спуска для целочисленных выражений приведен ниже.
/* Синтаксический анализатор рекурсивного спуска
для целочисленных выражений, который содержит
ряд включаемых переменных
*/
#include "setjmp.h"
#include "math.h"
#include "ctype.h"
#include "stdlib.h"
#define DELIMITER 1
#define VARIABLE 2
#define NUMBER 3
#define COMMAND 4
#define STRING 5
#define QUOTE 6
#define EOL 9
#define FINISHED 10
extern char *prog; /* буфер анализируемого выражения */
extern jmp_buf e_buf; /* буфер среды функции longjmp() */
extern int variables[26]; /* переменные */
extern struct commands
char command[20];
char tok;
table[];
extern char token[80]; /* внешнее представление лексемы */
extern char token_type; /* тип лексемы */
extern char tok; /* внутреннее представление лексемы */
void get_exp(),level2(),level3(),level4(),level5();
void level6(),primitive(),arith(),unary();
void serror(), putback();
/* Точка входа в анализатор. */
void get_exp(result)
int *result;
get_token();
if(!*token)
serror(2);
return;
level2(result);
putback(); /* возвращает последнюю считаную
лексему обратно во входной поток */
/* Сложение или вычитание двух термов */
void level2(result)
int *result;
register char op;
int hold;
level3(result);
while((op=*token) == '+' || op == '-')
get_token();
level3(&hold);
arith(op,result,&hold);
/* Вычисление произведения или частного двух фвкторов */
void level3(result)
int *result;
register char op;
int hold;
level4(result);
while((op = *token) == '+' || op == '/' || op == '%')
get_token();
level4(&hold);
arith(op,result,&hold);
/* Обработка степени числа (целочисленной) */
void level4(result)
int *result;
int hold;
level5(result);
if(*token== '^')
get_token();
level4(&hold);
arith('^', result, &hold);
/* Унарный + или - */
void level5(result)
int *result;
register char op;
op = 0;
if((token_type==DELIMITER) && *token=='+' || *token=='-')
op = *token;
get_token();
level6(result);
if(op)
unary(op, result);
/* Обработка выражения в круглых скобках */
void level6(result)
int *result;
if((*token == '(') && (token_type == DELIMITER))
get_token();
level2(result);
if(*token != ')')
serror(1);
get_token();
else
primitive(result);
/* Определение значения переменной по ее имени */
void primitive(result)
int *result;
switch(token_type)
case VARIABLE:
*result = find_var(token);
get_token();
return;
case NUMBER:
*result = atoi(token);
get_token();
return;
default:
serror(0);
/* Выполнение специфицированной арифметики */
void arith(o, r, h)
char o;
int *r, *h;
register int t, ex;
switch(o)
case '-':
*r = *r-*h;
break;
case '+':
*r = *r+*h;
break;
case '*':
*r = *r * *h;
break;
case '/':
*r = (*r)/(*h);
break;
case '%':
t = (*r)/(*h);
*r = *r-(t*(*h));
break;
case '^':
ex =*r;
if(*h==0)
*r = 1;
break;
for(t=*h-1; t>0; --t) *r = (*r) * ex;
break;
/* Изменение знака */
void unary(o, r)
char o;
int *r;
if(o=='-') *r = -(*r);
/* Поиск значения переменной */
int find_var(s)
char *s;
if(!isalpha(*s))
serror(4); /* не переменная */
return 0;
return variables[toupper(*token)-'^'];
/* выдать сообщение об ошибке */
void serror(error)
int error;
static char *e[]=
"Синтаксическая ошибка",
"Непарные круглые скобки",
"Это не выражениеt",
"Предполагается символ равенства",
"Не переменная",
"Таблица меток переполнена",
"Дублирование меток",
"Неопределенная метка",
"Необходим оператор THEN",
"Необходим оператор TO",
" Уровень вложенности цикла FOR слишком велик",
"NEXT не соответствует FOR",
"Уровень вложенности GOSUB слишком велик",
"RETURN не соответствует GOSUB"
;
printf("&4%s\n",e[error]);
longjmp(e_buf, 1); /* возврат в точку сохранения */
/* Чтение лексемы. */
get_token()
register char *temp;
token_type=0; tok=0;
temp=token;
if(*prog=='\0') /* Конец файла */
*token=0;
tok = FINISHED;
return(token_type=DELIMITER);
while(iswhite(*prog)) ++prog; /* пропуск пробелов */
if(*prog=='\r') /* коней строки программы */
++prog; ++prog;
tok = EOL; *token='\r';
token[1]='\n'; token[2]=0;
return (token_type = DELIMITER);
if(strchr("+-^/%=;(),><", *prog)) /* разделитель */
*temp=*prog;
prog++; /* переход на следующую позицию */
temp++;
*temp=0;
return (token_type=DELIMITER);
if(*prog=='"') /* строка кавычек */
prog++;
while(*prog != '"' && *prog!='\r') *temp++=*prog++;
if(*prog=='\r') serror(1);
prog++;*temp=0;
return(token_type=QUOTE);
if(isdigit(*prog)) /* число */
while(!isdelim(*prog)) *temp++=*prog++;
*temp = '\0';
return(token_type = NUMBER);
if(isalpha(*prog)) /* переменная или команда */
while(!isdelim(*prog)) *temp++=*prog++;
token_type=STRING;
*temp = '\0';
/* просматривается, если строка - переменная или команда */
if (token_type==STRING)
tok=look_up(token); /* Преобразование во внутренний формат */
if (!tok) token_type = VARIABLE;
else token_type = COMMAND; /* это команда */
return token_type;
/* Возврат лексемы во входной поток */
void putback()
char *t;
t = token;
for(; *t; t++) prog--;
/* Поиск соответствия внутреннего формата для
текущей лексемы в таблице лексем.
*/
look_up(s)
char *s;
register int i,j;
char *p;
/* преобразование к нижнему регистру */
p = s;
while(*p) *p = tolower(*p); p++;
/* просматривается, если лексема обнаружена в
таблице */
for(i=0; *table[i].command; i++)
if(!strcmp(table[i].command, s)) return table[i].tok; return 0; /* нераспознанная команда */
/* Возвращает "истину", если "c" разделитель */
isdelim(c)
char c;
if(strchr(" ;,+-<>/*%^=()",c) || c==9 || c=='\r' || c==0)
return 1;
return 0;
/* Возвращает 1, если "с" пробел или табуляция */
iswhite(c)
char c;
if(c==' ' || c=='\t') return 1;
else return 0;
Анализатор поддерживает следующие операторы: "+", "-", "*", "/", "%", целочисленный показатель степени (^) и унарный минус. Все эти операции могут использоваться в сочетании с круглыми скобками. Вы, вероятно, заметили, что в программе имеются функции шести уровней, которые работают точно также как функция primitive(), вращающая значение числа. Помимо этих функций, реализующих арифметические операции, в состав программы включены функции arith() и unary(), а также get_token().
При вычислении выражения prog указывает на начало строки, содержащей выражение, и вызывает get_exp() с адресом переменной, в которую вы хотите поместить результат.
Обратите особое внимание на функцию serror(), которая используется для выдачи сообщений об ошибках. При обнаружении синтаксической ошибки serror() вызывается с номером этой ошибки в качестве аргумента. Ошибка с кодом 0, которой соответствует сообщение "синтаксическая ошибка", выдается в том случае, когда тип ошибки нельзя определить более конкретно. В других случаях ошибка уточняется. Заметьте, что serror() заканчивается вызовом функции longjmp().
Функция logjmp() выполняет нелокальный переход, возвращаясь в точку, определенную с помощью функции setjmp(). Функция setjmp() включена в исходный текст интерпретатора. Первый аргумент функции logjmp() является буфером среды, инициированной с помощью setjmp(). Второй аргумент - это значение, которое определяется при передаче управления из setjmp() обратно в точку ее вызова. Как это делается вы, увидите позже.
Использование ljgjmp() упрощает обработку ошибок, так как программы-анализаторы не должны аварийно завершаться при обнаружении ошибки. Если ваш компилятор Си не поддерживает функции setjmp() и logjmp(), то каждая функция при обнаружении ошибок должна выполнять возврат в точку возникновения ошибки самостоятельно.
