В этом разделе рассматривается наиболее важная часть интерпретатора Little С. Перед тем как приступить к подробному чтению текста программы интерпретатора, нужно понять, как вообще работает интерпретатор. Понять программу интерпретатора в некотором смысле легче, чем программу синтаксического анализатора выражений, потому что работа по интерпретации программы на С может быть выражена следующим простым алгоритмом:
while (есть_лексемы_во_входном_потоке) {
читать следующую лексему;
выполнить соответствующее действие;
}
Этот алгоритм может показаться невероятно простым по сравнению с синтаксическим анализатором выражений, но это именно то, что делает интерпретатор. Нужно только иметь в виду следующее: шаг "выполнить соответствующее действие" может содержать чтение дополнительных лексем из входного потока. Для лучшего понимания этого алгоритма мысленно выполним интерпретацию следующего фрагмента программы:
int a;
a = 10;
if(a < 100) printf("%d", a);
Согласно алгоритму, прочтем первую лексему int. Эта лексема указывает на то, что следующим действием должно быть чтение следующей лексемы для того, чтобы узнать, как называется переменная (a), которую нужно объявить и для которой нужно выделить область памяти. Следующая лексема (точка с запятой) заканчивает строку. Соответствующее действие — проигнорировать ее. Далее, начинаем следующую итерацию алгоритма и считываем следующую лексему, это а из второй строки. Строка не начинается с зарезервированного слова, следовательно, это выражение языка С. Поэтому соответствующим действием является применение синтаксического анализатора выражений для вычисления значения выражения. Этот процесс "съедает" все лексемы во второй строке. Наконец, читаем лексему if. Она указывает на то, что начинается оператор if. Соответствующее действие — выполнить его. Аналогичный процесс выполняется многократно, пока не будет считана последняя лексема программы. Это относится к любой программе на С. Пользуясь этим алгоритмом, приступим к созданию интерпретатора.
Перед тем как интерпретатор начнет выполнять программу, должны быть выполнены некоторые рутинные процедуры. Характерной чертой языков, предназначенных больше для интерпретации, чем для компиляции, является то, что выполнение программы начинается в начале текста программы и заканчивается в его конце. Так выполняются программы, написанные на старых версиях языка BASIC. Это, однако, не относится к языку С (как и к любому другому структурированному языку) по трем основным причинам.
Во-первых, все программы на С начинают выполняться с функции main(). Вовсе не обязательно, чтобы эта функция была первой в программе. Поэтому интерпретатор, чтобы начать выполнение с нее, должен еще до начала выполнения программы узнать, где она находится. Следовательно, должен быть реализован некоторый метод, позволяющий начать выполнение программы с нужной точки. (Глобальные переменные также могут предшествовать функции main(), поэтому, даже если она является первой функцией программы, все равно и в этом случае она не начинается с первой строки.)
Во-вторых, все глобатьные переменные должны быть известны перед началом выполнения main(). Операторы объявления глобальных переменных никогда не выполняются интерпретатором, потому что они находятся вне всех функций. (В языке С весь выполняющийся текст программы находится внутри функций, поэтому при выполнении программы интерпретатор Little С никогда не выходит за пределы функций.)
И наконец, в-третьих, для повышения скорости выполнения необходимо (правда, не всегда) знать, где в программе расположена каждая функция; это позволит вызывать ее как можно быстрее. Если это условие не будет выполнено, то при каждом вызове функции понадобится длительный последовательный поиск этой функции в тексте программы.
Эти проблемы решаются с помощью предварительного прохода интерпретатора. Программа предварительного прохода (иногда ее называют препроцессором, правда это название очень неудачное из-за того, что совпадает с названием препроцессора компилятора С, хотя практически ничего общего с ним не имеет) применяется во всех коммерческих компиляторах независимо от интерпретируемого языка. Программа предварительного прохода читает исходный текст программы перед ее выполнением и делает все, что нужно сделать до выполнения. В интерпретаторе Little С она выполняет две важные задачи: во-первых, находит и запоминает положение всех пользовательских функций, включая main(), и во-вторых, находит все глобальные переменные и определяет область их видимости. В интерпретаторе Little С предварительный проход выполняет функция prescan():
/* Найти адреса всех функций в программе
и запомнить глобальные переменные. */
void prescan(void)
{
char *p, *tp;
char temp[32];
int datatype;
int brace = 0; /* Если brace = 0, то текущая
позиция указателя программы находится
в не какой-либо функции. */
p = prog;
func_index = 0;
do {
while(brace) { /* обход кода функции */
get_token();
if(*token == '{') brace++;
if(*token == '}') brace--;
}
tp = prog; /* запоминание текущей позиции */
get_token();
/* тип глобальной переменной или возвращаемого значения функции */
if(tok==CHAR || tok==INT) {
datatype = tok; /* запоминание типа данных */
get_token();
if(token_type == IDENTIFIER) {
strcpy(temp, token);
get_token();
if(*token != '(') { /* это должна быть глобальная переменная */
prog = tp; /* возврат в начало объявления */
decl_global();
}
else if(*token == '(') { /* это должна быть функция */
func_table[func_index].loc = prog;
func_table[func_index].ret_type = datatype;
strcpy(func_table[func_index].func_name, temp);
func_index++;
while(*prog != ')') prog++;
prog++;
/* сейчас prog указывает на открывающуюся
фигурную скобку функции */
}
else putback();
}
}
else if(*token == '{') brace++;
} while(tok != FINISHED);
prog = p;
}
Функция prescan() работает следующим образом. Каждый раз, когда встречается открывающаяся фигурная скобка, переменная brace увеличивается на 1, а когда закрывающаяся — уменьшается на 1. Следовательно, если brace больше нуля, то текущая лексема находится внутри функции[1]. Поэтому объявление переменной считается глобальным, если оно встретилось, когда brace равно нулю. Аналогично, если при brace, равном нулю, встретилось имя функции, значит, оно принадлежит определению функции (в Little С нет прототипов функций).
Функция decl_global() запоминает глобальные переменные в таблице global_vars:
/* Массив этих структур содержит информацию
о глобальных переменных.
*/
struct var_type {
char var_name[ID_LEN];
int v_type;
int value;
} global_vars[NUM_GLOBAL_VARS];
int gvar_index; /* индекс в таблице глобальных переменных */
/* Объявление глобальной переменной. */
void decl_global(void)
{
int vartype;
get_token(); /* определение типа */
vartype = tok; /* запоминание типа переменной */
do { /* обработка списка */
global_vars[gvar_index].v_type = vartype;
global_vars[gvar_index].value = 0; /* инициализация нулем */
get_token(); /* определение имени */
strcpy(global_vars[gvar_index].var_name, token);
get_token();
gvar_index++;
} while(*token == ',');
if(*token != ';') sntx_err(SEMI_EXPECTED);
}
Переменная целого типа gvar_index содержит индекс первого свободного элемента массива global_vars.
Адрес каждой функции, определенной пользователем, помещается в массив func_table:
struct func_type {
char func_name[ID_LEN];
int ret_type;
char *loc; /* адрес точки входа в файл */
} func_table[NUM_FUNC];
int func_index; /* индекс в таблице функций */
Переменная func_index содержит индекс первой свободной позиции в таблице func_table.
Главная функция интерпретатора Little С загружает исходный текст программы, инициализирует глобальные переменные, готовит интерпретатор к вызову main() и вызывает функцию call(), которая начинает выполнение программы. Работа call() будет рассмотрена далее в этой главе.
int main(int argc, char *argv[])
{
if(argc != 2) {
printf("Применение: littlec <имя_файла>\n");
exit(1);
}
/* выделение памяти для программы */
if((p_buf = (char *) malloc(PROG_SIZE))==NULL) {
printf("Выделить память не удалось");
exit(1);
}
/* загрузка программы для выполнения */
if(!load_program(p_buf, argv[1])) exit(1);
if(setjmp(e_buf)) exit(1); /* инициализация буфера long jump */
gvar_index = 0; /* инициализация индекса глобальных переменных */
/* установка указателя программы на начало буфера программы */
prog = p_buf;
prescan(); /* определение адресов всех функций
и глобальных переменных программы */
lvartos = 0; /* инициализация индекса стека локальных переменных */
functos = 0; /* инициализация индекса стека вызова (CALL) */
/* первой вызывается main() */
prog = find_func("main"); /* поиск точки входа программы */
if(!prog) { /* функция main() неправильна или отсутствует */
printf("main() не найдена.\n");
exit(1);
}
prog--; /* возврат к открывающейся скобке ( */
strcpy(token, "main");
call(); /* начало интерпритации main() */
return 0;
}
Функция interp_block() является сердцем интерпретатора. В этой функции принимается решение о том, какое действие выполнить при прочтении очередной лексемы из входного потока. Функция интерпретирует один блок программы, после чего возвращает управление. Если блок состоит из единственного оператора, этот оператор интерпретируется и функция возвращает управление вызвавшей программе. По умолчанию interp_block() интерпретирует один оператор, после чего возвращает управление вызвавшей программе. Однако, если встречается открывающаяся фигурная скобка, то флажок block устанавливается в 1 и функция продолжает интерпретацию операторов, пока не встретит закрывающуюся фигурную скобку. Текст функции interp_block() приведен ниже:
/* Интерпритация одного оператора или блока. Когда
interp_block() возвращает управление после первого
вызова, в main() встретилась последняя
закрывающаяся фигурная скобка или оператор return.
*/
void interp_block(void)
{
int value;
char block = 0;
do {
token_type = get_token();
/* При интерпритации одного операторавозврат
после первой точки с запятой.
*/
/* определение типа лексемы */
if(token_type == IDENTIFIER) {
/* Это не зарегестрированное слово,
обрабатывается выражение. */
putback(); /* возврат лексемыво входной поток
для дальнейшей обработки функцией eval_exp() */
eval_exp(&value); /* обработка выражения */
if(*token!=';') sntx_err(SEMI_EXPECTED);
}
else if(token_type==BLOCK) {
/* если это граничитель блока */
if(*token == '{') /* блок */
block = 1; /* интерпритация блока, а не оператора */
else return; /* это }, возврат */
}
else /* зарезервированное слово */
switch(tok) {
case CHAR:
case INT: /* объявление локальной переменной */
putback();
decl_local();
break;
case RETURN: /* возврат из вызова функции */
func_ret();
return;
case IF: /* обработка оператора if */
exec_if();
break;
case ELSE: /* обработка оператора else */
find_eob(); /* поиск конца блока else
и продолжение выполнения */
break;
case WHILE: /* обработка цикла while */
exec_while();
break;
case DO: /* обработка цикла do-while */
exec_do();
break;
case FOR: /* обработка цикла for */
exec_for();
break;
case END:
exit(0);
}
} while (tok != FINISHED && block);
}
Если не считать вызовов функции exit() или подобных ей, то интерпретация программы, написанной на языке С, кончается в одном из следующих случаев: встретилась последняя закрывающаяся фигурная скобка функции main(), или встретился оператор return из main(). Из-за того, что при встрече последней закрывающейся фигурной скобки main() программу нужно завершить, interp_block() выполняет только один оператор или блок, а не всю программу, хоть она и состоит из блоков. Таким образом, interp_block() вызывается каждый раз, когда встречается новый блок. Это относится не только к блокам функций, но и к блокам операторов (например, if). Следовательно, в процессе выполнения программы интерпретатор Little С вызывает interp_block() рекурсивно.
Функция interp_block() работает следующим образом. Сначала из входного потока считывается очередная лексема программы. Если это точка с запятой, то выполняется единственный оператор и функция возвращает управление. В противном случае, выполняется проверка, является ли следующая лексема идентификатором; если да, то оператор является выражением и вызывается синтаксический анализатор выражений. Синтаксический анализатор должен прочесть все выражение, включая первую лексему, поэтому перед его вызовом функция putback() возвращает последнюю прочитанную лексему во входной поток. После возврата управления из eval_exp() token содержит последнюю лексему, прочитанную синтаксическим анализатором выражений. Если синтаксических ошибок нет, то это должна быть точка с запятой. Если token не содержит точку с запятой, то выводится сообщение об ошибке.
Если очередная лексема программы является открывающейся фигурной скобкой, то переменная block устанавливается равной 1, а если закрывающейся, то interp_block() возвращает управление вызвавшей программе.
Если лексема является зарезервированным словом, то выполняется оператор switch, который вызывает соответствующую процедуру обработки оператора. Нумерация зарезервированных слов в функции get_token() нужна для того, чтобы можно было применить switch, а не if, которому пришлось бы сравнивать строки, что значительно медленнее.
Функции, выполняющие операторы с зарезервированным словом, будут рассмотрены в дальнейших разделах.
Ниже приведен листинг файла с текстом программы интерпретатора. Он называется LITTLEC.C.
/* Интерпритатор языка Little C. */
#include <stdio.h>
#include <setjmp.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#define NUM_FUNC 100
#define NUM_GLOBAL_VARS 100
#define NUM_LOCAL_VARS 200
#define NUM_BLOCK 100
#define ID_LEN 31
#define FUNC_CALLS 31
#define NUM_PARAMS 31
#define PROG_SIZE 10000
#define LOOP_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};
char *prog; /* текущая позиция в исходном тексте программы */
char *p_buf; /* указывает на начало буфера программы */
jmp_buf e_buf; /* содержит информацию для longjmp() */
/* Массив этих структур содержит информацию
о глобальных переменных.
*/
struct var_type {
char var_name[ID_LEN];
int v_type;
int value;
} global_vars[NUM_GLOBAL_VARS];
struct var_type local_var_stack[NUM_LOCAL_VARS];
struct func_type {
char func_name[ID_LEN];
int ret_type;
char *loc; /* адрес точки входа в файл */
} func_table[NUM_FUNC];
int call_stack[NUM_FUNC];
struct commands { /* таблица зарезервированных слов */
char command[20];
char tok;
} table[] = { /* В эту таблицу */
"if", IF, /* команды должны быть введены на нижнем регистре. */
"else", ELSE,
"for", FOR,
"do", DO,
"while", WHILE,
"char", CHAR,
"int", INT,
"return", RETURN,
"end", END,
"", END /* конец таблицы */
};
char token[80];
char token_type, tok;
int functos; /* индекс вершины стека вызова функции */
int func_index; /* индекс в таблице функций */
int gvar_index; /* индекс в таблице глобальных переменных */
int lvartos; /* индекс в стеке локальных переменных */
int ret_value; /* возвращаемое значение функции */
void print(void), prescan(void);
void decl_global(void), call(void), putback(void);
void decl_local(void), local_push(struct var_type i);
void eval_exp(int *value), sntx_err(int error);
void exec_if(void), find_eob(void), exec_for(void);
void get_params(void), get_args(void);
void exec_while(void), func_push(int i), exec_do(void);
void assign_var(char *var_name, int value);
int load_program(char *p, char *fname), find_var(char *s);
void interp_block(void), func_ret(void);
int func_pop(void), is_var(char *s), get_token(void);
char *find_func(char *name);
int main(int argc, char *argv[])
{
if(argc != 2) {
printf("Применение: littlec <имя_файла>\n");
exit(1);
}
/* выделение памяти для программы */
if((p_buf = (char *) malloc(PROG_SIZE))==NULL) {
printf("Выделить память не удалось");
exit(1);
}
/* загрузка программы для выполнения */
if(!load_program(p_buf, argv[1])) exit(1);
if(setjmp(e_buf)) exit(1); /* инициализация буфера long jump */
gvar_index = 0; /* инициализация индекса глобальных переменных */
/* установка указателя программы на начало буфера программы */
prog = p_buf;
prescan(); /* определение адресов всех функций
и глобальных переменных программы */
lvartos = 0; /* инициализация индекса стека локальных переменных */
functos = 0; /* инициализация индекса стека вызова (CALL) */
/* первой вызывается main() */
prog = find_func("main"); /* поиск точки входа программы */
if(!prog) { /* функция main() неправильна или отсутствует */
printf("main() не найдена.\n");
exit(1);
}
prog--; /* возврат к открывающейся скобке ( */
strcpy(token, "main");
call(); /* начало интерпритации main() */
return 0;
}
/* Интерпритация одного оператора или блока. Когда
interp_block() возвращает управление после первого
вызова, в main() встретилась последняя
закрывающаяся фигурная скобка или оператор return.
*/
void interp_block(void)
{
int value;
char block = 0;
do {
token_type = get_token();
/* При интерпритации одного операторавозврат
после первой точки с запятой.
*/
/* определение типа лексемы */
if(token_type == IDENTIFIER) {
/* Это не зарегестрированное слово,
обрабатывается выражение. */
putback(); /* возврат лексемыво входной поток
для дальнейшей обработки функцией eval_exp() */
eval_exp(&value); /* обработка выражения */
if(*token!=';') sntx_err(SEMI_EXPECTED);
}
else if(token_type==BLOCK) {
/* если это граничитель блока */
if(*token == '{') /* блок */
block = 1; /* интерпритация блока, а не оператора */
else return; /* это }, возврат */
}
else /* зарезервированное слово */
switch(tok) {
case CHAR:
case INT: /* объявление локальной переменной */
putback();
decl_local();
break;
case RETURN: /* возврат из вызова функции */
func_ret();
return;
case IF: /* обработка оператора if */
exec_if();
break;
case ELSE: /* обработка оператора else */
find_eob(); /* поиск конца блока else
и продолжение выполнения */
break;
case WHILE: /* обработка цикла while */
exec_while();
break;
case DO: /* обработка цикла do-while */
exec_do();
break;
case FOR: /* обработка цикла for */
exec_for();
break;
case END:
exit(0);
}
} while (tok != FINISHED && block);
}
/* Загрузка программы. */
int load_program(char *p, char *fname)
{
FILE *fp;
int i=0;
if((fp=fopen(fname, "rb"))==NULL) return 0;
i = 0;
do {
*p = getc(fp);
p++; i++;
} while(!feof(fp) && i<PROG_SIZE);
if(*(p-2) == 0x1a) *(p-2) = '\0'; /* программа кончается
нулевым символом */
else *(p-1) = '\0';
fclose(fp);
return 1;
}
/* Найти адреса всех функций в программе
и запомнить глобальные переменные. */
void prescan(void)
{
char *p, *tp;
char temp[32];
int datatype;
int brace = 0; /* Если brace = 0, то текущая
позиция указателя программы находится
в не какой-либо функции. */
p = prog;
func_index = 0;
do {
while(brace) { /* обход кода функции */
get_token();
if(*token == '{') brace++;
if(*token == '}') brace--;
}
tp = prog; /* запоминание текущей позиции */
get_token();
/* тип глобальной переменной или возвращаемого значения функции */
if(tok==CHAR || tok==INT) {
datatype = tok; /* запоминание типа данных */
get_token();
if(token_type == IDENTIFIER) {
strcpy(temp, token);
get_token();
if(*token != '(') { /* это должна быть глобальная переменная */
prog = tp; /* возврат в начало объявления */
decl_global();
}
else if(*token == '(') { /* это должна быть функция */
func_table[func_index].loc = prog;
func_table[func_index].ret_type = datatype;
strcpy(func_table[func_index].func_name, temp);
func_index++;
while(*prog != ')') prog++;
prog++;
/* сейчас prog указывает на открывающуюся
фигурную скобку функции */
}
else putback();
}
}
else if(*token == '{') brace++;
} while(tok != FINISHED);
prog = p;
}
/* Возврат адреса точки входа данной функции.
Возврат NULL, если не надена.
*/
char *find_func(char *name)
{
register int i;
for(i=0; i < func_index; i++)
if(!strcmp(name, func_table[i].func_name))
return func_table[i].loc;
return NULL;
}
/* Объявление глобальной переменной. */
void decl_global(void)
{
int vartype;
get_token(); /* определение типа */
vartype = tok; /* запоминание типа переменной */
do { /* обработка списка */
global_vars[gvar_index].v_type = vartype;
global_vars[gvar_index].value = 0; /* инициализация нулем */
get_token(); /* определение имени */
strcpy(global_vars[gvar_index].var_name, token);
get_token();
gvar_index++;
} while(*token == ',');
if(*token != ';') sntx_err(SEMI_EXPECTED);
}
/* Объявление локальной переменной. */
void decl_local(void)
{
struct var_type i;
get_token(); /* определение типа */
i.v_type = tok;
i.value = 0; /* инициализация нулем */
do { /* обработка списка */
get_token(); /* определение типа пременной */
strcpy(i.var_name, token);
local_push(i);
get_token();
} while(*token == ',');
if(*token != ';') sntx_err(SEMI_EXPECTED);
}
/* Вызов функции. */
void call(void)
{
char *loc, *temp;
int lvartemp;
loc = find_func(token); /* найти точку входа функции */
if(loc == NULL)
sntx_err(FUNC_UNDEF); /* функция не определена */
else {
lvartemp = lvartos; /* запоминание индекса стека
локальных переменных */
get_args(); /* получение аргумента функции */
temp = prog; /* запоминание адреса возврата */
func_push(lvartemp); /* запоминание индекса стека
локальных переменных */
prog = loc; /* переустановка prog в начало функции */
get_params(); /* загрузка параметров функции
значениями аргументов */
interp_block(); /* интерпретация функции */
prog = temp; /* восстановление prog */
lvartos = func_pop(); /* восстановление стека
локальных переменных */
}
}
/* Заталкивание аргументов функций в стек
локальных переменных. */
void get_args(void)
{
int value, count, temp[NUM_PARAMS];
struct var_type i;
count = 0;
get_token();
if(*token != '(') sntx_err(PAREN_EXPECTED);
/* обработка списка значений */
do {
eval_exp(&value);
temp[count] = value; /* временное запоминание */
get_token();
count++;
}while(*token == ',');
count--;
/* затолкнуть в local_var_stack в обратном порядке */
for(; count>=0; count--) {
i.value = temp[count];
i.v_type = ARG;
local_push(i);
}
}
/* Получение параметров функции. */
void get_params(void)
{
struct var_type *p;
int i;
i = lvartos-1;
do { /* обработка списка параметров */
get_token();
p = &local_var_stack[i];
if(*token != ')' ) {
if(tok != INT && tok != CHAR)
sntx_err(TYPE_EXPECTED);
p->v_type = token_type;
get_token();
/* связывание имени пераметров с аргументом,
уже находящимся в стеке локальных переменных */
strcpy(p->var_name, token);
get_token();
i--;
}
else break;
} while(*token == ',');
if(*token != ')') sntx_err(PAREN_EXPECTED);
}
/* Возврат из функции. */
void func_ret(void)
{
int value;
value = 0;
/* получение возвращаемого значения, если оно есть */
eval_exp(&value);
ret_value = value;
}
/* Затолкнуть локальную переменную. */
void local_push(struct var_type i)
{
if(lvartos > NUM_LOCAL_VARS)
sntx_err(TOO_MANY_LVARS);
local_var_stack[lvartos] = i;
lvartos++;
}
/* Выталкивание индекса в стеке локальных переменных. */
int func_pop(void)
{
functos--;
if(functos < 0) sntx_err(RET_NOCALL);
return call_stack[functos];
}
/* Запись индекса в стек локальных переменных. */
void func_push(int i)
{
if(functos>NUM_FUNC)
sntx_err(NEST_FUNC);
call_stack[functos] = i;
functos++;
}
/* Присваивание переменной значения. */
void assign_var(char *var_name, int value)
{
register int i;
/* проверка наличия локальной переменной */
for(i=lvartos-1; i >= call_stack[functos-1]; i--) {
if(!strcmp(local_var_stack[i].var_name, var_name)) {
local_var_stack[i].value = value;
return;
}
}
if(i < call_stack[functos-1])
/* если переменная нелокальная,
ищем ее в таблице глобальных переменных */
for(i=0; i < NUM_GLOBAL_VARS; i++)
if(!strcmp(global_vars[i].var_name, var_name)) {
global_vars[i].value = value;
return;
}
sntx_err(NOT_VAR); /* переменная не найдена */
}
/* Получение значения переменной. */
int find_var(char *s)
{
register int i;
/* проверка наличия переменной */
for(i=lvartos-1; i >= call_stack[functos-1]; i--)
if(!strcmp(local_var_stack[i].var_name, token))
return local_var_stack[i].value;
/* в противном случае проверим,
может быть это глобальная переменная */
for(i=0; i < NUM_GLOBAL_VARS; i++)
if(!strcmp(global_vars[i].var_name, s))
return global_vars[i].value;
sntx_err(NOT_VAR); /* переменная не найдена */
return -1;
}
/* Если индентификатор является переменной, то
возвращается 1, иначе 0.
*/
int is_var(char *s)
{
register int i;
/* это локальная переменная ? */
for(i=lvartos-1; i >= call_stack[functos-1]; i--)
if(!strcmp(local_var_stack[i].var_name, token))
return 1;
/* если нет - поиск среди глобальных переменных */
for(i=0; i < NUM_GLOBAL_VARS; i++)
if(!strcmp(global_vars[i].var_name, s))
return 1;
return 0;
}
/* Выполнение оператора if. */
void exec_if(void)
{
int cond;
eval_exp(&cond); /* вычисление if-выражения */
if(cond) { /* истина - интерпретация if-предложения */
interp_block();
}
else { /* в противном случае пропуск if-предложения
и выполнение else-предложения, если оно есть */
find_eob(); /* поиск конца блока */
get_token();
if(tok != ELSE) {
putback(); /* восстановление лексемы,
если else-предложение отсутсвует */
return;
}
interp_block();
}
}
/* Выполнение цикла while. */
void exec_while(void)
{
int cond;
char *temp;
putback();
temp = prog; /* запоминание адреса начала цикла while */
get_token();
eval_exp(&cond); /* вычисление управляющего выражения */
if(cond) interp_block(); /* если оно истинно, то выполнить
интерпритацию */
else { /* в противном случае цикл пропускается */
find_eob();
return;
}
prog = temp; /* возврат к началу цикла */
}
/* Выполнение цикла do. */
void exec_do(void)
{
int cond;
char *temp;
putback();
temp = prog; /* запоминание адреса начала цикла */
get_token(); /* найти начало цикла */
interp_block(); /* интерпритация цикла */
get_token();
if(tok != WHILE) sntx_err(WHILE_EXPECTED);
eval_exp(&cond); /* проверка условия цикла */
if(cond) prog = temp; /* если условие истинно,
то цикл выполняется, в противном случае происходит
выход из цикла */
}
/* Поиск конца блока. */
void find_eob(void)
{
int brace;
get_token();
brace = 1;
do {
get_token();
if(*token == '{') brace++;
else if(*token == '}') brace--;
} while(brace);
}
/* Выполнение цикла for. */
void exec_for(void)
{
int cond;
char *temp, *temp2;
int brace ;
get_token();
eval_exp(&cond); /* инициализирующее выражение */
if(*token != ';') sntx_err(SEMI_EXPECTED);
prog++; /* пропуск ; */
temp = prog;
for(;;) {
eval_exp(&cond); /* проверка условия */
if(*token != ';') sntx_err(SEMI_EXPECTED);
prog++; /* пропуск ; */
temp2 = prog;
/* поиск начала тела цикла */
brace = 1;
while(brace) {
get_token();
if(*token == '(') brace++;
if(*token == ')') brace--;
}
if(cond) interp_block(); /* если условие выполнено,
то выполнить интерпритацию */
else { /* в противном случае обойти цикл */
find_eob();
return;
}
prog = temp2;
eval_exp(&cond); /* вполнение инкремента */
prog = temp; /* возврат в начало цикла */
}
}
Когда интерпретатор встречает зарезервированные слова int или char, он вызывает функцию decl_local(), которая размещает локальные переменные. Как отмечалось ранее, при выполнении программы интерпретатор не может встретить объявление глобальной переменной, потому что выполняется только код программы, записанный внутри функций. Следовательно, если встретилось объявление переменной, то это локальная переменная (или параметр — этот случай будет рассмотрен в следующем разделе). В структурированных языках локальные переменные хранятся в стеке. Если программа компилируется, то обычно используется системный стек. Однако при интерпретации стек с локальными переменными должен быть создан самим интерпретатором. В интерпретаторе Little С стек для локальных переменных хранится в массиве local_var_stack. Каждый раз, когда встречается локальная переменная, ее имя, тип и значение (первоначально равное нулю) заносятся в стек при помощи функции local_push(). Глобальная переменная lvartos является указателем стека. (Соответствующей функции извлечения из стека нет. Вместо этого стек локальных переменных переустанавливается каждый раз при возврате управления из функции local_push(). Зачем это сделано, будет видно из дальнейшего изложения.) Функции decl_local() и lоcal_push() приведены ниже:
/* Объявление локальной переменной. */
void decl_local(void)
{
struct var_type i;
get_token(); /* определение типа */
i.v_type = tok;
i.value = 0; /* инициализация нулем */
do { /* обработка списка */
get_token(); /* определение типа пременной */
strcpy(i.var_name, token);
local_push(i);
get_token();
} while(*token == ',');
if(*token != ';') sntx_err(SEMI_EXPECTED);
}
/* Затолкнуть локальную переменную. */
void local_push(struct var_type i)
{
if(lvartos > NUM_LOCAL_VARS)
sntx_err(TOO_MANY_LVARS);
local_var_stack[lvartos] = i;
lvartos++;
}
Функция decl_local() сначала считывает тип объявленной переменной (или переменных) и инициализирует переменные нулями. Затем в цикле считывается список идентификаторов, разделенных запятыми. При каждой итерации цикла информация об очередной переменной заносится в стек локальных переменных. В конце функции decl_local() проверяется, является ли последняя лексема точкой с запятой.
Выполнение функций, определенных пользователем, — это, наверное, самая трудная часть в реализации интерпретатора С. Интерпретатор должен начать чтение исходного текста программы с нового места, а затем вернуться в вызывающую процедуру после выхода из функции. Кроме того, он должен выполнить следующие три задачи: передать аргументы, разместить в памяти параметры и вернуть значение функции.
Все вызовы функций (кроме main()) осуществляются в синтаксическом анализаторе выражений из функции atom() с помощью вызова функции call(). Именно функция call() выполняет все необходимые при вызове функций действия. Текст функции call() вместе с ее вспомогательными функциями приведен ниже. Рассмотрим эту функцию подробнее:
/* Вызов функции. */
void call(void)
{
char *loc, *temp;
int lvartemp;
loc = find_func(token); /* найти точку входа функции */
if(loc == NULL)
sntx_err(FUNC_UNDEF); /* функция не определена */
else {
lvartemp = lvartos; /* запоминание индекса стека
локальных переменных */
get_args(); /* получение аргумента функции */
temp = prog; /* запоминание адреса возврата */
func_push(lvartemp); /* запоминание индекса стека
локальных переменных */
prog = loc; /* переустановка prog в начало функции */
get_params(); /* загрузка параметров функции
значениями аргументов */
interp_block(); /* интерпретация функции */
prog = temp; /* восстановление prog */
lvartos = func_pop(); /* восстановление стека
локальных переменных */
}
}
/* Заталкивание аргументов функций в стек
локальных переменных. */
void get_args(void)
{
int value, count, temp[NUM_PARAMS];
struct var_type i;
count = 0;
get_token();
if(*token != '(') sntx_err(PAREN_EXPECTED);
/* обработка списка значений */
do {
eval_exp(&value);
temp[count] = value; /* временное запоминание */
get_token();
count++;
}while(*token == ',');
count--;
/* затолкнуть в local_var_stack в обратном порядке */
for(; count>=0; count--) {
i.value = temp[count];
i.v_type = ARG;
local_push(i);
}
}
/* Получение параметров функции. */
void get_params(void)
{
struct var_type *p;
int i;
i = lvartos-1;
do { /* обработка списка параметров */
get_token();
p = &local_var_stack[i];
if(*token != ')' ) {
if(tok != INT && tok != CHAR)
sntx_err(TYPE_EXPECTED);
p->v_type = token_type;
get_token();
/* связывание имени пераметров с аргументом,
уже находящимся в стеке локальных переменных */
strcpy(p->var_name, token);
get_token();
i--;
}
else break;
} while(*token == ',');
if(*token != ')') sntx_err(PAREN_EXPECTED);
}
В первую очередь с помощью вызова функции find_func() функция call() находит адрес точки входа вызываемой функции в исходном тексте программы. Затем эта функция сохраняет текущее значение lvartos индекса стека локальных переменных в переменной lvartemp. Потом она вызывает функцию get_args(), которая обрабатывает все аргументы функции. Функция get_args() считывает список выражений, разделенных запятыми, и заносит их в стек локальных переменных в обратном порядке. (Обратный порядок занесения переменных применяется потому, что так их легче сопоставлять с соответствующими параметрами.) Значения переменных, записанные в стек, не имеют имен (стек — это всего лишь массив). Имена параметров даются им функцией get_params(), которая будет рассмотрена далее.
После обработки аргументов функции текущее значение указателя prog сохраняется в temp. Эта переменная указывает на точку возврата функции. После этого значение lvartemp заносится в стек вызова функций. Доступ к этому стеку осуществляется с помощью функций func_push() и func_pop(). В данный стек при каждом вызове функции записывается значение lvartos. Значение lvartos представляет собой начальную точку в стеке локальных переменных для переменных (и параметров) вызванной функции. Значение на вершине стека вызова функций используется для предотвращения доступа функции к переменным, которые в ней не объявлены.
Следующие две строки функции call() устанавливают указатель программы на начало функции и затем, вызывая функцию get_params(), устанавливают соответствие между формальными параметрами и значениями аргументов функции, которые уже находятся в стеке локальных переменных. Фактическое выполнение функции осуществляется вызовом interp_block(). После возврата управления из interp_block() указатель программы prog переустанавливается; он будет указывать на точку возврата, а индекс стека локальных переменных получит значение, которое он имел до вызова функции. На этом последнем шаге из стека фактически удаляются все локальные переменные функции.
Если вызванная функция содержит оператор return, то interp_block() перед возвратом в call() вызывает func_ret(), которая вычисляет возвращаемое значение; код этой функции приведен ниже:
/* Возврат из функции. */
void func_ret(void)
{
int value;
value = 0;
/* получение возвращаемого значения, если оно есть */
eval_exp(&value);
ret_value = value;
}
Глобальная целочисленная переменная ret_value содержит возвращаемое функцией значение. На первый взгляд может показаться странным то, что локальной переменной value сначала присваивается возвращаемое значение функции, а затем это значение присваивается переменной ret_value. Причина здесь в том, что функции могут быть рекурсивными и функция eval_exp() для вычисления возвращаемого значения может вызвать ту же функцию.
Возвратимся ненадолго к синтаксическому анализатору выражений. Когда встречается оператор присваивания, то сначала вычисляется значение выражения в правой части, а затем это значение присваивается переменной в левой части путем вызова assign_var(). Однако язык С структурирован и поддерживает глобальные и локальные переменные. Как же тогда в следующей программе
int count;
int main()
{
int count, i;
count = 10;
i = f();
return 0;
}
int f()
{
int count;
count = 99;
return count;
}
функция assign_var() знает, какой именно переменной count нужно присвоить значение? Ответ на это простой: во-первых, локальные переменные имеют приоритет над одноименными глобальными, а, во-вторых, локальные переменные недоступны за пределами своих функций. Проанализируем, как применяются эти правила для разрешения коллизий в приведенных выше примерах операторов присваивания. Для этого рассмотрим функцию assign_var():
/* Присваивание переменной значения. */
void assign_var(char *var_name, int value)
{
register int i;
/* проверка наличия локальной переменной */
for(i=lvartos-1; i >= call_stack[functos-1]; i--) {
if(!strcmp(local_var_stack[i].var_name, var_name)) {
local_var_stack[i].value = value;
return;
}
}
if(i < call_stack[functos-1])
/* если переменная нелокальная,
ищем ее в таблице глобальных переменных */
for(i=0; i < NUM_GLOBAL_VARS; i++)
if(!strcmp(global_vars[i].var_name, var_name)) {
global_vars[i].value = value;
return;
}
sntx_err(NOT_VAR); /* переменная не найдена */
}
Как указывалось в предыдущем разделе, при каждом вызове функции индекс стека локальных переменных (lvartos) записывается в стек вызова функции. Это значит, что любая локальная переменная (или параметр), определенные в функции, будут записаны в стек выше точки, на которую указывает lvartos. Следовательно, функция assign_var() просматривает local_var_stack, начиная с текущего значения на верхушке стека, причем просмотр прекращается, когда индекс достигает того значения, которое было занесено при последнем вызове функции. Благодаря этому просматриваются только те переменные, которые являются локальными для данной функции. (Это также помогает вызывать рекурсивные функции, потому что текущее значение lvartos сохраняется при каждом вызове функции.) Таким образом, если в main() присутствует строка "count = 100;", то assign_var() находит локальную переменную count внутри main(). В f() функция assign_var() находит переменную count, определенную в f(), а не в main().
Если имя переменной не совпадает ни с одним из имен локальных переменных, то просматривается список глобальных переменных.
Итак, базовая структура интерпретатора Little С создана. Теперь к ней можно добавить некоторые управляющие операторы. Каждый раз, когда функция interp_block() встречает оператор с зарезервированным словом, она вызывает соответствующую функцию, обрабатывающую этот оператор. Один из самых легких операторов — if. Он обрабатывается функцией exec_if():
/* Выполнение оператора if. */
void exec_if(void)
{
int cond;
eval_exp(&cond); /* вычисление if-выражения */
if(cond) { /* истина - интерпретация if-предложения */
interp_block();
}
else { /* в противном случае пропуск if-предложения
и выполнение else-предложения, если оно есть */
find_eob(); /* поиск конца блока */
get_token();
if(tok != ELSE) {
putback(); /* восстановление лексемы,
если else-предложение отсутсвует */
return;
}
interp_block();
}
}
Рассмотрим эту функцию подробнее. В первую очередь она вызывает eval_exp() для вычисления значения условного выражения. Если условие (cond) выполнено (т.е. выражение имеет ненулевое значение), то функция вызывает рекурсивно interp_block(), выполняя тем самым блок if. Если cond ложно, вызывается функция find_eob(), которая передвигает указатель программы на оператор, следующий после блока if. Если там присутствует else-предложение, то оно обрабатывается функцией exec_if() и выполняется блок else. В противном случае выполняется следующий оператор программы.
Если блок else присутствует и выполняется блок if, то после его выполнения нужно каким-то образом обойти блок else. Эта задача выполняется в функции interp_block() путем вызова функции find_eob(), которая обходит блок после else. Запомните, что в синтаксически правильной программе else обрабатывается функцией interp_block() только в одном случае — после выполнения блока if. Если выполняется блок else, то оператор else обрабатывается функцией exec_if().
Интерпретировать цикл while, как и if, довольно легко. Ниже приведен текст функции exec_while(), которая интерпретирует while:
/* Выполнение цикла while. */
void exec_while(void)
{
int cond;
char *temp;
putback();
temp = prog; /* запоминание адреса начала цикла while */
get_token();
eval_exp(&cond); /* вычисление управляющего выражения */
if(cond) interp_block(); /* если оно истинно, то выполнить
интерпритацию */
else { /* в противном случае цикл пропускается */
find_eob();
return;
}
prog = temp; /* возврат к началу цикла */
}
Функция exec_while() работает следующим образом. Сначала лексема while возвращается во входной поток, а ее адрес сохраняется в переменной temp. Этот адрес будет использован интерпретатором, чтобы возвратиться к началу цикла (т.е. начать следующую итерацию с начала цикла while). Далее лексема while считывается заново для того, чтобы удалить ее из входного потока. После этого вызывается функция eval_exp(), которая вычисляет значение условного выражения цикла while. Если условие выполнено (т.е. условное выражение принимает значение ИСТИНА), то рекурсивно вызывается функция interp_block(), которая интерпретирует блок while. После возврата управления из interp_block() программный указатель prog устанавливается на начало цикла while и управление передается функции interp_block(), в которой весь процесс повторяется. Если условное выражение оператора while принимает значение ЛОЖЬ, то происходит поиск конца блока while, а затем выход из функции exec_while().
Обработка цикла do-while во многом похожа на обработку цикла while. Когда функция interp_block() встречает оператор do, она вызывает функцию exec_do(), исходный текст которой приведен ниже:
/* Выполнение цикла do. */
void exec_do(void)
{
int cond;
char *temp;
putback();
temp = prog; /* запоминание адреса начала цикла */
get_token(); /* найти начало цикла */
interp_block(); /* интерпритация цикла */
get_token();
if(tok != WHILE) sntx_err(WHILE_EXPECTED);
eval_exp(&cond); /* проверка условия цикла */
if(cond) prog = temp; /* если условие истинно,
то цикл выполняется, в противном случае происходит
выход из цикла */
}
Главное отличие цикла do-while от цикла while состоит в том, что блок do-while выполняется всегда как минимум один раз, потому что его условное выражение находится после тела цикла. Поэтому exec_do сначала запоминает адрес начала цикла в переменной temp, а затем рекурсивно вызывает interp_block(), которая интерпретирует блок, ассоциированный с циклом. После возврата управления из interp_block() идет поиск соответствующего слова while и вычисляется значение условного выражения. Если условие выполнено, то prog устанавливается так, что его значение указывает на начало цикла, в противном случае выполнение продолжается со следующего оператора.
Интерпретация цикла for — задача значительно более трудная, чем интерпретация других операторов. Частично это объясняется тем, что структура цикла for в языке С была задумана в предположении компиляции программы. Главная трудность заключается в том, что условное выражение for должно проверяться в начале цикла, а часть приращения должна быть выполнена в его конце. Таким образом, эти две части цикла for в тексте исходной программы находятся рядом, а их интерпретация разделена выполнением блока цикла. Однако, после некоторой дополнительной работы, цикл for все же может быть интерпретирован.
Когда interp_block() встречает оператор for, вызывается функция exec_for(), текст которой приведен ниже:
/* Выполнение цикла for. */
void exec_for(void)
{
int cond;
char *temp, *temp2;
int brace ;
get_token();
eval_exp(&cond); /* инициализирующее выражение */
if(*token != ';') sntx_err(SEMI_EXPECTED);
prog++; /* пропуск ; */
temp = prog;
for(;;) {
eval_exp(&cond); /* проверка условия */
if(*token != ';') sntx_err(SEMI_EXPECTED);
prog++; /* пропуск ; */
temp2 = prog;
/* поиск начала тела цикла */
brace = 1;
while(brace) {
get_token();
if(*token == '(') brace++;
if(*token == ')') brace--;
}
if(cond) interp_block(); /* если условие выполнено,
то выполнить интерпритацию */
else { /* в противном случае обойти цикл */
find_eob();
return;
}
prog = temp2;
eval_exp(&cond); /* вполнение инкремента */
prog = temp; /* возврат в начало цикла */
}
}
Сначала функция обрабатывает инициализирующее выражение цикла for. Часть инициализации for выполняется только один раз; эта часть не подвергается циклической обработке. Затем указатель программы устанавливается так, чтобы он указывал на символ, следующий сразу после той точки с запятой, которой заканчивается часть инициализации. Наконец, после этого значение указателя присваивается переменной temp. А затем организовывается цикл, в котором проверяется условная часть цикла for и переменной temp2 присваивается адрес начала части приращения. Далее производится поиск начала тела цикла и его (тела) интерпретация, если условное выражение принимает значение ИСТИНА. (В противном случае производится поиск конца тела цикла и выполнение продолжается с оператора, следующего после цикла for.) После рекурсивного вызова interp_block() выполняется часть приращения, после чего весь процесс повторяется.
[1]На самом деле, конечно, данный алгоритм работает правильно только при условии, что учитываются только значащие фигурные скобки, а фигурные скобки внутри строк, например, не учитываются. (Фигурные скобки внутри строк "съедаются" программой считывания лексем.)