В оставшейся части данной главы приведены два синтаксических анализатора. Первый из них разбирает и вычисляет только константные выражения, т.е. выражения, в которых нет переменных. Второй анализатор способен работать с 26 переменными, от А до Z.
Ниже приводится полная версия простого рекурсивного нисходящего синтаксического анализатора, вычисляющего выражения, в которых при вычислении операнды представляются в формате с плавающей запятой.
/* Это модуль содержит простой синтаксический анализатор,
который не распознает переменные.
*/
#include <stdlib.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>
#define DELIMITER 1
#define VARIABLE 2
#define NUMBER 3
extern char *prog; /* содержит анализируемое выражение */
char token[80];
char tok_type;
void eval_exp(double *answer), eval_exp2(double *answer);
void eval_exp3(double *answer), eval_exp4(double *answer);
void eval_exp5(double *answer), eval_exp6(double *answer);
void atom(double *answer);
void get_token(void), putback(void);
void serror(int error);
int isdelim(char c);
/* Точка входа анализатора. */
void eval_exp(double *answer)
{
get_token();
if(!*token) {
serror(2);
return;
}
eval_exp2(answer);
if(*token) serror(0); /* последней лексемой должен быть нуль */
}
/* Сложение или вычитание двух слагаемых. */
void eval_exp2(double *answer)
{
register char op;
double temp;
eval_exp3(answer);
while((op = *token) == '+' || op == '-') {
get_token();
eval_exp3(&temp);
switch(op) {
case '-':
*answer = *answer - temp;
break;
case '+':
*answer = *answer + temp;
break;
}
}
}
/* Умножение или деление двух множителей. */
void eval_exp3(double *answer)
{
register char op;
double temp;
eval_exp4(answer);
while((op = *token) == '*' || op == '/' || op == '%') {
get_token();
eval_exp4(&temp);
switch(op) {
case '*':
*answer = *answer * temp;
break;
case '/':
if(temp == 0.0) {
serror(3); /* деление на нуль */
*answer = 0.0;
} else *answer = *answer / temp;
break;
case '%':
*answer = (int) *answer % (int) temp;
break;
}
}
}
/* Возведение в степень */
void eval_exp4(double *answer)
{
double temp, ex;
register int t;
eval_exp5(answer);
if(*token == '^') {
get_token();
eval_exp4(&temp);
ex = *answer;
if(temp==0.0) {
*answer = 1.0;
return;
}
for(t=temp-1; t>0; --t) *answer = (*answer) * (double)ex;
}
}
/* Умножение унарных операторов + и -. */
void eval_exp5(double *answer)
{
register char op;
op = 0;
if((tok_type == DELIMITER) && *token=='+' || *token == '-') {
op = *token;
get_token();
}
eval_exp6(answer);
if(op == '-') *answer = -(*answer);
}
/* Вычисление выражения в скобках. */
void eval_exp6(double *answer)
{
if((*token == '(')) {
get_token();
eval_exp2(answer);
if(*token != ')')
serror(1);
get_token();
}
else
atom(answer);
}
/* Получение значения в скобках. */
void atom(double *answer)
{
if(tok_type == NUMBER) {
*answer = atof(token);
get_token();
return;
}
serror(0); /* иначе синтаксическая ошибка в выражении */
}
/* Выражение лексемы во входной поток. */
void putback(void)
{
char *t;
t = token;
for(; *t; t++) prog--;
}
/* Отображение сообщения об ошибке. */
void serror(int error)
{
static char *e[]= {
"Синтаксическая ошибка",
"Несбалансированные скобки",
"Нет выражения",
"Деление на нуль"
};
printf("%s\n", e[error]);
}
/* Возврат очередной лексемы. */
void get_token(void)
{
register char *temp;
tok_type = 0;
temp = token;
*temp = '\0';
if(!*prog) return; /* конец выражения */
while(isspace(*prog)) ++prog; /* пропустить пробелы,
символы табуляции и пустой строки */
if(strchr("+-*/%^=()", *prog)){
tok_type = DELIMITER;
/* перейтик следующему символу */
*temp++ = *prog++;
}
else if(isalpha(*prog)) {
while(!isdelim(*prog)) *temp++ = *prog++;
tok_type = VARIABLE;
}
else if(isdigit(*prog)) {
while(!isdelim(*prog)) *temp++ = *prog++;
tok_type = NUMBER;
}
*temp = '\0';
}
/* Возвращение значения ИСТИНА, если с является разделителем. */
int isdelim(char c)
{
if(strchr(" +-/*%^=()", c) || c==9 || c=='\r' || c==0)
return 1;
return 0;
}
В приведенном здесь виде анализатор поддерживает следующие операторы: +, -, *, /, %. Кроме того, он умеет возводить в целочисленную степень (^) и вычислять унарный минус. А еще анализатор умеет корректно распознавать скобки. Обратите внимание, что он состоит из шести уровней, а также функции atom, которая возвращает значение числа. Как уже обсуждалось ранее, в глобальной переменной token возвращается очередная лексема из строки, содержащей выражение, а в tok_type — тип лексемы. Переменная-указатель prog указывает на строку, содержащую выражение.
Следующая простая функция main() демонстрирует использование этого анализатора:
/* Демонстрационная программа для анализатора. */
#include <stdlib.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>
char *prog;
void eval_exp(double *answer);
int main(void)
{
double answer;
char *p;
p = (char *) malloc(100);
if(!p) {
printf("Ошибка при выделении памяти.\n");
exit(1);
}
/* Обработка выражений до ввода пустой строки. */
do {
prog = p;
printf("Введите выражение: ");
gets(prog);
if(!*prog) break;
eval_exp(&answer);
printf("Результат: %.2f\n", answer);
} while(*p);
return 0;
}
Чтобы понять, как же в действительности анализатор вычисляет выражение, давайте проработаем следующий пример. (Допустим, что prog указывает на начало выражения.)
10 - 3 * 2
При вызове функции eval_exp() — входной точки анализатора — из входной строки выбирается лексема. Если она является пустой строкой, то функция печатает сообщение "Нет выражения" и завершается. Однако в данном случае лексемой является число 10. Поскольку это не пустая строка, вызывается функция eval_exp2(). В результате, функция eval_exp2() вызывает eval_exp3(), a eval_exp3() вызывает eval_exp4(), а та в свою очередь вызывает eval_exp5(). Затем функция eval_exp5() проверяет, не является ли лексема унарным плюсом или минусом. В данном случае это не так, поэтому вызывается функция eval_exp6(). В этот момент eval_exp6() может рекурсивно вызвать либо eval_exp2() (в случае выражения, заключенного в скобки), либо atom(), чтобы определить значение числа. Поскольку лексема не является открывающей скобкой, выполняется функция atom() и переменной *answer присваивается значение 10. Затем происходит выборка следующей лексемы и возврат из цепочки вызовов функций. Лексемой становится оператор -, а управление возвращается функции eval_exp2().
То, что происходит дальше, очень важно. Поскольку текущей лексемой является символ -, он сохраняется в переменной ор. Затем анализатор выбирает следующую лексему и спуск по цепочке начинается снова. Как и раньше, вызывается функция atom(). Полученное значение 3 возвращается в переменной *answer, и считывается лексема *. Это вызывает возврат по цепочке до eval_exp3(), где считывается последняя лексема 2. В этот момент происходит первая арифметическая операция — умножение 3 на 2. Полученный результат возвращается функции eval_exp2(), где происходит вычитание. В результате вычитания в ответе получается 4. Несмотря на то, что этот процесс может поначалу показаться сложным, самостоятельная проработка других примеров поможет вам разобраться в работе анализатора.
Данный анализатор подошел бы для настольного калькулятора, что было продемонстрировано предыдущей программой, или для небольшой базы данных. Однако перед тем как использовать его для разбора языка программирования или в сложном калькуляторе, в него необходимо добавить средства работы с переменными. Это является предметом следующего раздела.