Содержание | <<< | >>>

Простая программа синтаксического анализа выражений

В оставшейся части данной главы приведены два синтаксических анализатора. Первый из них разбирает и вычисляет только константные выражения, т.е. выражения, в которых нет переменных. Второй анализатор способен работать с 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. Несмотря на то, что этот процесс может поначалу показаться сложным, самостоятельная проработка других примеров поможет вам разобраться в работе анализатора.

Данный анализатор подошел бы для настольного калькулятора, что было продемонстрировано предыдущей программой, или для небольшой базы данных. Однако перед тем как использовать его для разбора языка программирования или в сложном калькуляторе, в него необходимо добавить средства работы с переменными. Это является предметом следующего раздела.


Содержание | <<< | >>>