Синтаксический анализатор выражений

Содержание

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

Для построения синтаксического анализатора выражений языка С можно применить несколько различных методов. Во многих коммерческих компиляторах используются синтаксические анализаторы, управляемые таблицей; такие синтаксические анализаторы создаются специальными генераторами программ синтаксического анализа. Синтаксические анализаторы, управляемые таблицей, в общем случае обладают большим быстродействием, чем другие синтаксические анализаторы, однако процесс их создания очень трудоемкий. В рассматриваемом здесь интерпретаторе Little С используется рекурсивный нисходящий синтаксический анализатор[1], который представляет собой реализацию в языке С производящих правил, приведенных в предыдущем разделе.

Рекурсивный нисходящий синтаксический анализатор представляет собой набор взаимно рекурсивных функций, обрабатывающих выражение. Если синтаксический анализатор работает в компиляторе, то он генерирует объектный код, соответствующий исходному тексту программы. В интерпретаторе целью синтаксического анализатора является вычисление значения заданного выражения. В этом разделе рассматривается разработка синтаксического анализатора выражений языка Little С.



На заметкуОсновы теории синтаксического анализа выражений рассмотрены в главе 24. Синтаксический анализатор, разрабатываемый в этой главе, строится на основе простого расширения этой теории.

Синтаксический разбор исходного текста программы


Специальная функция, читающая исходный текст программы и возвращающая очередную логическую единицу, является фундаментальной частью каждого интерпретатора и компилятора. Исторически сложившееся название такой логической единицы — лексема. Во всех языках программирования (в том числе и в языке С) программа рассматривается как последовательность лексем. Другими словами, лексема — это неделимая единица программы. Например, оператор равенства == является лексемой. Эти два знака равенства нельзя разделить, не изменив кардинальным образом их значение. Аналогично, if — также лексема. Ни «i«, ни «f» сами по себе не имеют в программе на С никакого значения.

В языке С каждая лексема принадлежит одной из следующих категорий:

зарезервированные слова     идентификаторы     константы
строки                      операторы          знаки пунктуации

Зарезервированные слова — это лексемы, составляющие язык С; к ним относится, например, while. Идентификаторы — это имена переменных, функций и типов, определенных пользователем (в Little С не реализованы). Знаки пунктуации — это некоторые символы, такие как точка с запятой, запятая, различные скобки и т.п. В зависимости от контекста, некоторые из этих символов, могут быть операторами. Приведем пример разбиения на лексемы при разборе оператора слева направо. Оператор

for(x=0; x<10; x=x+1) printf("алло %d", x);

состоит из следующих лексем:

Лексема       Категория
for           зарезервированное слово
(             знак пунктуации
x             идентификатор
=             оператор
0             константа
;             знак пунктуации
x             идентификатор
<             оператор
10            константа
;             знак пунктуации
x             идентификатор
=             оператор
x             идентификатор
+             оператор
1             константа
)             знак пунктуации
printf        идентификатор
(             знак пунктуации
"алло %d"     строка
,             знак пунктуации
x             идентификатор
)             знак пунктуации
;             знак пунктуации

Однако для упрощения интерпретатора Little С в нем определяются следующие категории лексем:

Тип лексемы                          Включает
delimiter (разделитель)              знаки пунктуации и операторы
keyword (зарезервированное слово)    зарезервированные слова
string (строка)                      строки, заключенные в двойные кавычки
identifier (идентификатор)           имена переменных и функций
number (число)                       числовая константа
block (блок)                         { или }

Функция get_token() выделяет лексемы из исходного текста программы Little С и возвращает их в качестве своего значения:

/* Считывание лексемы из входного потока. */
int get_token(void)
{

  register char *temp;

  token_type = 0; tok = 0;

  temp = token;
  *temp = '\0';

  /* пропуск пробелов, символов табуляции и пустой строки */
  while(iswhite(*prog) && *prog) ++prog;

  if(*prog == '\r') {
    ++prog;
    ++prog;
    /* пропуск пробелов */
    while(iswhite(*prog) && *prog) ++prog;
  }

  if(*prog == '\0') { /* конец файла */
    *token = '\0';
    tok = FINISHED;
    return (token_type = DELIMITER);
  }

  if(strchr("{}", *prog)) { /* ограничение блока */
    *temp = *prog;
    temp++;
    *temp = '\0';
    prog++;
    return (token_type = BLOCK);
  }

  /* поиск комментариев */
  if(*prog == '/')
    if(*(prog+1) == '*') { /* это комментарий */
      prog += 2;
      do { /* найти конец комментария */
        while(*prog != '*') prog++;
        prog++;
      } while (*prog != '/');
      prog++;
    }

  if(strchr("!<>=", *prog)) { /* возможно, это
                                       оператор сравнения */
    switch(*prog) {
      case '=': if(*(prog+1) == '=') {
          prog++; prog++;
          *temp = EQ;
          temp++; *temp = EQ; temp++;
          *temp = '\0';
       }
       break;
      case '!': if(*(prog+1) == '=') {
          prog++; prog++;
          *temp = NE;
          temp++; *temp = NE; temp++;
          *temp = '\0';
       }
       break;
      case '<': if(*(prog+1) == '=') {
          prog++; prog++;
          *temp = LE; temp++; *temp = LE;
       }
       else {
          prog++;
          *temp = LT;
       }
       temp++;
       *temp = '\0';
       break;
      case '>': if(*(prog+1) == '=') {
          prog++; prog++;
          *temp = GE; temp++; *temp = GE;
       }
       else {
         prog++;
         *temp = GT;
       }
       temp++;
       *temp = '\0';
       break;
    }
    if(*token) 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') sntx_err(SYNTAX);
    prog++; *temp = '\0';
    return (token_type = STRING);
  }

  if(isdigit(*prog)) { /* число */
    while(!isdelim(*prog)) *temp++ = *prog++;
    *temp = '\0';
    return (token_type = NUMBER);
  }

  if(isalpha(*prog)) { /* переменная или оператор */
    while(!isdelim(*prog)) *temp++ = *prog++;
    token_type = TEMP;
  }

  *temp = '\0';

  /* эта строка является оператором или переменной? */
  if(token_type==TEMP) {
    tok = look_up(token); /* преобразовать во внутренее представление */
    if(tok) token_type = KEYWORD; /* это зарезервированное слово */
    else token_type = IDENTIFIER;
  }
  return token_type;
}

В функции get_token() используются следующие глобальные данные и перечислимые типы:

extern char *prog;  /* текущее положение в исходном тексте программы */
extern char *p_buf;  /* указатель на начало буфера программы */

extern char token[80]; /* строковое представление лексемы */
extern char token_type; /* содержит тип лексемы */
extern char tok; /* внутреннее представление лексемы */

enum tok_types {DELIMITER, IDENTIFIER, NUMBER, KEYWORD,
                TEMP, STRING, BLOCK};

enum tokens {ARG, CHAR, INT, IF, ELSE, FOR, DO, WHILE,
             SWITCH, RETURN, EOL, FINISHED, END};

enum double_ops {LT=1, LE, GT, GE, EQ, NE};

/* Эти константы используются для вызова функции sntx_err()
   в случае синтаксической ошибки. При необходимости список
   констант можно расширить.
   ВНИМАНИЕ: константа SYNTAX используется тогда, когда
   интерпритатор не может квалифицировать ошибку.
*/
enum error_msg
     {SYNTAX, UNBAL_PARENS, NO_EXP, EQUALS_EXPECTED,
      NOT_VAR, PARAM_ERR, SEMI_EXPECTED,
      UNBAL_BRACES, FUNC_UNDEF, TYPE_EXPECTED,
      NEST_FUNC, RET_NOCALL, PAREN_EXPECTED,
      WHILE_EXPECTED, QUOTE_EXPECTED, NOT_TEMP,
      TOO_MANY_LVARS, DIV_BY_ZERO};

Указатель prog указывает на текущую позицию в исходном тексте интерпретируемой программы. Указатель p_buf интерпретатором не изменяется; он всегда указывает на начало интерпретируемой программы. Функция get_token() начинает работу с удаления пробелов и символов перевода строки. Так как никакая лексема языка С (кроме строковой константы) не содержит пробелов, их нужно пропустить. Функция get_token() пропускает также комментарии (в Little С допускаются только комментарии вида /*...*/). После этого строка, представляющая каждую лексему, помещается в token и ее тип (определенный в перечислении tok_types) записывается в token_type. Если лексема представляет собой зарезервированное слово, то его внутреннее представление присваивается tok с помощью функции look_up() (приведена в полном листинге синтаксического анализатора). Необходимость внутреннего представления зарезервированных слов будет обоснована позже. Функция get_token() преобразует двухсимвольные операторы сравнения в соответствующие значения перечислимого типа. Технически в этом нет крайней необходимости, однако это упрощает реализацию интерпретатора. И, наконец, если синтаксический анализатор находит синтаксическую ошибку, то он вызывает функцию sntx_err() со значением перечислимого типа, соответствующим типу найденной ошибки. Функция sntx_err() вызывается также другими процедурами интерпретатора каждый раз, когда встречается ошибка. Листинг функции sntx_err() имеет такой вид:

/* Вывод сообщения об ошибке. */
void sntx_err(int error)
{
  char *p, *temp;
  int linecount = 0;
  register int i;

  static char *e[]= {
    "синтаксическая ошибка",
    "несбалансированные скобки",
    "выражение отсутствует",
    "ожидается знак равенства",
    "не переменная",
    "ошибка в параметре",
    "ожидается точка с запятой",
    "несбалансированные фигурные скобки",
    "функция не определена",
    "ожидается спецификатор типа",
    "слишком много вложенных вызовов функций",
    "оператор return вне функции",
    "ожидаются скобки",
    "ожидается while",
    "ожидается закрывающаяся кавычка",
    "не строка",
    "слишком много локальных переменных",
    "деление на нуль"
  };
  printf("\n%s", e[error]);
  p = p_buf;
  while(p != prog) {  /* поиск номера строки с ошибкой */
    p++;
    if(*p == '\r') {
      linecount++;
    }
  }
  printf(" in line %d\n", linecount);

  temp = p;
  for(i=0; i < 20 && p > p_buf && *p != '\n'; i++, p--);
  for(i=0; i < 30 && p <= temp; i++, p++) printf("%c", *p);

  longjmp(e_buf, 1); /* возврат в безопасную точку */
}

Обратите внимание, sntx_err() выводит на экран номер строки, в которой обнаружена ошибка (или номер следующей строки) и саму строку. Заканчивается sntx_err() вызовом longjmp(). Синтаксическая ошибка часто встречается внутри глубоко вложенных или рекурсивных процедур, поэтому лучшим способом реакции на ошибку является переход в какое-либо безопасное место. Как альтернативный подход, можно было бы установить глобальный флажок ошибки и просмотреть его значение во всех точках каждой процедуры, однако это существенно усложнило бы программу интерпретатора.

Рекурсивный нисходящий синтаксический анализатор Little C


Ниже приведен полный текст рекурсивного нисходящего синтаксического анализатора Little С вместе со всеми его функциями, глобальными данными и типами данных. Текст программы синтаксического анализатора находится в одном файле под именем PARSER.C. (Из-за большого объема всей программы интерпритатора Little С она содержится в трех отдельных файлах.)

/* Рекурсивный нисходящий синтаксический анализатор
   целочисленных выражений, содержащих переменные
   и вызовы функций.
*/
#include <setjmp.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define NUM_FUNC        100
#define NUM_GLOBAL_VARS 100
#define NUM_LOCAL_VARS  200
#define ID_LEN          31
#define FUNC_CALLS      31
#define PROG_SIZE       10000
#define FOR_NEST        31

enum tok_types {DELIMITER, IDENTIFIER, NUMBER, KEYWORD,
                TEMP, STRING, BLOCK};

enum tokens {ARG, CHAR, INT, IF, ELSE, FOR, DO, WHILE,
             SWITCH, RETURN, EOL, FINISHED, END};

enum double_ops {LT=1, LE, GT, GE, EQ, NE};

/* Эти константы используются для вызова функции sntx_err()
   в случае синтаксической ошибки. При необходимости список
   констант можно расширить.
   ВНИМАНИЕ: константа SYNTAX используется тогда, когда
   интерпритатор не может квалифицировать ошибку.
*/
enum error_msg
     {SYNTAX, UNBAL_PARENS, NO_EXP, EQUALS_EXPECTED,
      NOT_VAR, PARAM_ERR, SEMI_EXPECTED,
      UNBAL_BRACES, FUNC_UNDEF, TYPE_EXPECTED,
      NEST_FUNC, RET_NOCALL, PAREN_EXPECTED,
      WHILE_EXPECTED, QUOTE_EXPECTED, NOT_TEMP,
      TOO_MANY_LVARS, DIV_BY_ZERO};

extern char *prog;  /* текущее положение в исходном тексте программы */
extern char *p_buf;  /* указатель на начало буфера программы */
extern jmp_buf e_buf; /* содержит данные для longjmp() */

/* Массив этой структуры содержит информацию
   о глобальный переменных.
*/
extern struct var_type {
  char var_name[32];
  int v_type;
  int value;
}  global_vars[NUM_GLOBAL_VARS];

/* Это стек вызова функции. */
extern struct func_type {
  char func_name[32];
  int ret_type; 
  char *loc;  /* адрес входа функции в файле */
} func_stack[NUM_FUNC];

/* Таблица зарезервированных слов */
extern struct commands {
  char command[20];
  char tok;
} table[];

/* Здесь функции "стандартной библиотеки"
   объявлены таким образом, что их можно
   поместить во внутренюю таблицу функции.
*/
int call_getche(void), call_putch(void);
int call_puts(void), print(void), getnum(void);

struct intern_func_type {
  char *f_name; /* имя функции */
  int (*p)();   /* указатель на функцию */
} intern_func[] = {
  "getche", call_getche,
  "putch", call_putch,
  "puts", call_puts,
  "print", print,
  "getnum", getnum,
  "", 0  /* этот список заканчивается нулем */
};

extern char token[80]; /* строковое представление лексемы */
extern char token_type; /* содержит тип лексемы */
extern char tok; /* внутреннее представление лексемы */

extern int ret_value; /* возвращаемое значение функции */

void eval_exp0(int *value);
void eval_exp(int *value);
void eval_exp1(int *value);
void eval_exp2(int *value);
void eval_exp3(int *value);
void eval_exp4(int *value);
void eval_exp5(int *value);
void atom(int *value);
void sntx_err(int error), putback(void);
void assign_var(char *var_name, int value);
int isdelim(char c), look_up(char *s), iswhite(char c);
int find_var(char *s), get_token(void);
int internal_func(char *s);
int is_var(char *s);
char *find_func(char *name);
void call(void);

/* Точка входа в синтаксический анализатор выражений. */
void eval_exp(int *value)
{
  get_token();
  if(!*token) {
    sntx_err(NO_EXP);
    return;
  }
  if(*token == ';') {
    *value = 0; /* пустое выражение */
    return;
  }
  eval_exp0(value);
  putback(); /* возврат последней лексемы во входной поток */
}

/* Обработка выражения в присваивании */
void eval_exp0(int *value)
{
  char temp[ID_LEN];  /* содержит имя переменной,
                         которой присваивается значение */
  register int temp_tok;

  if(token_type == IDENTIFIER) {
    if(is_var(token)) {  /* если эта переменная,
       посмотреть, присваивается ли ей значение */
      strcpy(temp, token);
      temp_tok = token_type;
      get_token();
      if(*token == '=') {  /* это присваивание */
        get_token();
        eval_exp0(value);  /* вычислить присваемое значение */
        assign_var(temp, *value);  /* присвоить значение */
        return;
      }
      else {  /* не присваивание */
        putback();  /* востановление лексемы */
        strcpy(token, temp);
        token_type = temp_tok;
      }
    }
  }
  eval_exp1(value);
}

/* Обработка операций сравнения. */
void eval_exp1(int *value)
{
  int partial_value;
  register char op;
  char relops[7] = {
    LT, LE, GT, GE, EQ, NE, 0
  };

  eval_exp2(value);
  op = *token;
  if(strchr(relops, op)) {
    get_token();
    eval_exp2(&partial_value);
    switch(op) {  /* вычисление результата операции сравнения */
      case LT:
        *value = *value < partial_value;
        break;
      case LE:
        *value = *value <= partial_value;
        break;
      case GT:
        *value = *value > partial_value;
        break;
      case GE:
        *value = *value >= partial_value;
        break;
      case EQ:
        *value = *value == partial_value;
        break;
      case NE:
        *value = *value != partial_value;
        break;
    }
  }
}

/*  Суммирование или вычисление двух термов. */
void eval_exp2(int *value)
{
  register char  op;
  int partial_value;

  eval_exp3(value);
  while((op = *token) == '+' || op == '-') {
    get_token();
    eval_exp3(&partial_value);
    switch(op) { /* суммирование или вычитание */
      case '-':
        *value = *value - partial_value;
        break;
      case '+':
        *value = *value + partial_value;
        break;
    }
  }
}

/* Умножение или деление двух множителей. */
void eval_exp3(int *value)
{
  register char  op;
  int partial_value, t;

  eval_exp4(value);
  while((op = *token) == '*' || op == '/' || op == '%') {
    get_token();
    eval_exp4(&partial_value);
    switch(op) { /* умножение, деление или деление целых */
      case '*':
        *value = *value * partial_value;
        break;
      case '/':
        if(partial_value == 0) sntx_err(DIV_BY_ZERO);       
        *value = (*value) / partial_value;
        break;
      case '%':
        t = (*value) / partial_value;
        *value = *value-(t * partial_value);
        break;
    }
  }
}

/* Унарный + или -. */
void eval_exp4(int *value)
{
  register char  op;

  op = '\0';
  if(*token == '+' || *token == '-') {
    op = *token;
    get_token();
  }
  eval_exp5(value);
  if(op)
    if(op == '-') *value = -(*value);
}

/* Обработка выражения в скобках. */
void eval_exp5(int *value)
{
  if((*token == '(')) {
    get_token();
    eval_exp0(value);   /* вычисление подвыражения */
    if(*token != ')') sntx_err(PAREN_EXPECTED);
    get_token();
  }
  else
    atom(value);
}

/* Получение значения числа, переменной или функции. */
void atom(int *value)
{
  int i;

  switch(token_type) {
  case IDENTIFIER:
    i = internal_func(token);
    if(i!= -1) {  /* вызов функции из "стандартной билиотеки" */
      *value = (*intern_func[i].p)();
    }
    else
    if(find_func(token)) { /* вызов функции,
                              определенной пользователем */
      call();
      *value = ret_value;
    }
    else *value = find_var(token); /* получение значения переменной */
    get_token();
    return;
  case NUMBER: /* числовая константа */
    *value = atoi(token);
    get_token();
    return;
  case DELIMITER: /* это символьная константа? */
    if(*token == '\'') {
      *value = *prog;
      prog++;
      if(*prog!='\'') sntx_err(QUOTE_EXPECTED);
      prog++;
      get_token();
      return ;
    }
    if(*token==')') return; /* обработка пустого выражения */
    else sntx_err(SYNTAX); /* синтаксическая ошибка */
  default:
    sntx_err(SYNTAX); /* синтаксическая ошибка */
  }
}

/* Вывод сообщения об ошибке. */
void sntx_err(int error)
{
  char *p, *temp;
  int linecount = 0;
  register int i;

  static char *e[]= {
    "синтаксическая ошибка",
    "несбалансированные скобки",
    "выражение отсутствует",
    "ожидается знак равенства",
    "не переменная",
    "ошибка в параметре",
    "ожидается точка с запятой",
    "несбалансированные фигурные скобки",
    "функция не определена",
    "ожидается спецификатор типа",
    "слишком много вложенных вызовов функций",
    "оператор return вне функции",
    "ожидаются скобки",
    "ожидается while",
    "ожидается закрывающаяся кавычка",
    "не строка",
    "слишком много локальных переменных",
    "деление на нуль"
  };
  printf("\n%s", e[error]);
  p = p_buf;
  while(p != prog) {  /* поиск номера строки с ошибкой */
    p++;
    if(*p == '\r') {
      linecount++;
    }
  }
  printf(" in line %d\n", linecount);

  temp = p;
  for(i=0; i < 20 && p > p_buf && *p != '\n'; i++, p--);
  for(i=0; i < 30 && p <= temp; i++, p++) printf("%c", *p);

  longjmp(e_buf, 1); /* возврат в безопасную точку */
}

/* Считывание лексемы из входного потока. */
int get_token(void)
{

  register char *temp;

  token_type = 0; tok = 0;

  temp = token;
  *temp = '\0';

  /* пропуск пробелов, символов табуляции и пустой строки */
  while(iswhite(*prog) && *prog) ++prog;

  if(*prog == '\r') {
    ++prog;
    ++prog;
    /* пропуск пробелов */
    while(iswhite(*prog) && *prog) ++prog;
  }

  if(*prog == '\0') { /* конец файла */
    *token = '\0';
    tok = FINISHED;
    return (token_type = DELIMITER);
  }

  if(strchr("{}", *prog)) { /* ограничение блока */
    *temp = *prog;
    temp++;
    *temp = '\0';
    prog++;
    return (token_type = BLOCK);
  }

  /* поиск комментариев */
  if(*prog == '/')
    if(*(prog+1) == '*') { /* это комментарий */
      prog += 2;
      do { /* найти конец комментария */
        while(*prog != '*') prog++;
        prog++;
      } while (*prog != '/');
      prog++;
    }

  if(strchr("!<>=", *prog)) { /* возможно, это
                                       оператор сравнения */
    switch(*prog) {
      case '=': if(*(prog+1) == '=') {
          prog++; prog++;
          *temp = EQ;
          temp++; *temp = EQ; temp++;
          *temp = '\0';
       }
       break;
      case '!': if(*(prog+1) == '=') {
          prog++; prog++;
          *temp = NE;
          temp++; *temp = NE; temp++;
          *temp = '\0';
       }
       break;
      case '<': if(*(prog+1) == '=') {
          prog++; prog++;
          *temp = LE; temp++; *temp = LE;
       }
       else {
          prog++;
          *temp = LT;
       }
       temp++;
       *temp = '\0';
       break;
      case '>': if(*(prog+1) == '=') {
          prog++; prog++;
          *temp = GE; temp++; *temp = GE;
       }
       else {
         prog++;
         *temp = GT;
       }
       temp++;
       *temp = '\0';
       break;
    }
    if(*token) 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') sntx_err(SYNTAX);
    prog++; *temp = '\0';
    return (token_type = STRING);
  }

  if(isdigit(*prog)) { /* число */
    while(!isdelim(*prog)) *temp++ = *prog++;
    *temp = '\0';
    return (token_type = NUMBER);
  }

  if(isalpha(*prog)) { /* переменная или оператор */
    while(!isdelim(*prog)) *temp++ = *prog++;
    token_type = TEMP;
  }

  *temp = '\0';

  /* эта строка является оператором или переменной? */
  if(token_type==TEMP) {
    tok = look_up(token); /* преобразовать во внутренее представление */
    if(tok) token_type = KEYWORD; /* это зарезервированное слово */
    else token_type = IDENTIFIER;
  }
  return token_type;
}

/* Возврат лексемы во входной поток. */
void putback(void)
{
  char *t;

  t = token;
  for(; *t; t++) prog--;
}

/* Поиск внутреннего представления лексемы
   в таблице лексем.
*/
int look_up(char *s)
{
  register int i;
  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; /* незнакомый оператор */
}

/* Возвращает идекс функции во внутренней
   библиотеке, или -1, если не найдена.
*/
int internal_func(char *s)
{
  int i;

  for(i=0; intern_func[i].f_name[0]; i++) {
    if(!strcmp(intern_func[i].f_name, s))  return i;
  }
  return -1;
}

/* Возвращает true (ИСТИНА), если с - разделитель. */
int isdelim(char c)
{
  if(strchr(" !;,+-<>'/*%^=()", c) || c == 9 ||
     c == '\r' || c == 0) return 1;
  return 0;
}

/* Возвращает 1, если с - пробел или табуляция. */
int iswhite(char c)
{
  if(c == ' ' || c == '\t') return 1;
  else return 0;
}

Функции, начинающиеся с eval_exp, и функция atom() реализуют порождающие правила для выражений в Little С. Для их проверки (и в качестве упражнения) рекомендуется мысленно выполнить действия синтаксического анализатора для какого-либо простого выражения.

Функция atom() находит значение целой константы или переменной, функции или символьной константы. В тексте программы могут присутствовать функции двух видов: определенные пользователем и библиотечные. Если встретилась пользовательская функция, ее текст обрабатывается интерпретатором до получения возвращаемого значения и выхода из функции. (Вызов функции рассматривается в следующем разделе.) Если встретилась библиотечная функция, то сначала ищется ее адрес с помощью функции internal_func(), а затем устанавливается доступ к ней с помощью ее интерфейсной функции. Библиотечные функции и адреса их интерфейсных функций содержатся в массиве intern_func, приведенном ниже:

/* Здесь функции "стандартной библиотеки"
   объявлены таким образом, что их можно
   поместить во внутренюю таблицу функции.
*/
int call_getche(void), call_putch(void);
int call_puts(void), print(void), getnum(void);

struct intern_func_type {
  char *f_name; /* имя функции */
  int (*p)();   /* указатель на функцию */
} intern_func[] = {
  "getche", call_getche,
  "putch", call_putch,
  "puts", call_puts,
  "print", print,
  "getnum", getnum,
  "", 0  /* этот список заканчивается нулем */
};

Таким образом, в интерпретаторе Little С предусмотрено только несколько функций стандартной библиотеки, однако расширить их список очень легко. (Тексты интерфейсных функций содержатся в отдельном файле, рассматриваемом далее в разделе "Библиотечные функции Little С".)

Необходимо сделать еще одно замечание о процедурах в файле синтаксического анализатора. Для правильного анализа программы на С в некоторых случаях требуется так называемый просмотр на одну лексему вперед. Например, в операторе

alpha = count();

интерпретатор сможет определить, что count является функцией, а не переменной, только если просмотрит на одну лексему вперед, то есть прочтет следующую скобку. Однако, если оператор выглядит как

alpha = count * 10;

то следующую после count лексему (в данном случае *) нужно вернуть обратно во входной поток; она будет использована позднее. Поэтому в файл синтаксического анализатора выражений включена функция putback(), которая возвращает последнюю прочитанную лексему обратно во входной поток.

В файле синтаксического анализатора выражений могут встретиться функции, в данный момент непонятные для читателя, однако в процессе изучения Little С их назначение и принцип работы станут яснее.

----------
[1]Так называется программа, выполняющая синтаксический анализ методом рекурсивного спуска.