|
|
|
| |
Главная  Программирование С++ Интерпретатор Mini С++
Интерпретатор — это средство выполнения программы на С++. Перед тем как перейти непосредственно к коду, было бы полезно уяснить, как вообще работает интерпретатор. Понять код интерпретатора во многих отношениях легче, чем код анализатора выражений, потому что суть процесса интерпретации можно описать с помощью следующего алгоритма: while(есть_лексемы) {
получи следующую лексему;
выполни назначенное действие;
}
Этот алгоритм может показаться невероятно простым по сравнению с алгоритмом анализатора выражений, но он в точности описывает то, что делают все интерпретаторы! Правда, следует помнить, что шаг "выполни назначенное действие" может включать чтение дополнительных лексем из входного потока и выполнение нового назначенного действия. Таким образом, шаг "выполни назначенное действие" может быть рекурсивным.
Для того чтобы понять, как работает алгоритм, давайте вручную проинтерпретируем приведенный далее фрагмент кода.
int а;
а = 10 * num;
if(а < 100) { cout « а:
>
Следуя алгоритму, прочитаем первую лексему int. Назначенное действие для этой лексемы — извлечь следующую лексему для того, чтобы выяснить имя объявляемой переменной (в данном случае, а) и затем запомнить его. Следующая лексема — точка с запятой, завершающая строку. Назначенное действие — игнорировать ее. Теперь получим следующую лексему — а. Поскольку в начале оператора нет ключевого слова, значит, это начало выражения. Назначенное действие — вычислить выражение, используя синтаксический анализатор выражений. Этот процесс поглощает все лексемы данного оператора. Далее читаем лексему if. Она сигнализирует о начале условного оператора, поэтому назначенное действие — обработать оператор if, что означает вычислить условное выражение. Если результат выражения равен true, выполняется блок кода, входящий в состав оператора if. В противном случае он пропускается.
Только что описанный процесс характерен для любой программы на языке С++. Интерпретация прекращается, когда прочитана последняя лексема или обнаружена синтаксическая ошибка. Давайте рассмотрим интерпретатор, учитывая базовый алгоритм. В листинге 9.2 приведен полный код интерпретатора из файла minicpp.cpp. В следующих разделах он будет обсуждаться подробно.
Листинг 9.2. Интерпретатор Mini С++
#include <iostream> #include <fstream> #include <new> #include <stack> #include <vector> #include <cstring> #include <cstdlib> #include <cctype> #include "mccommon.h"
using namespace std;
char *prog; // текущая точка выполнения в исходном коде char *p_buf; // указывает на начало буфера программы
// Эта структура инкапсулирует информацию, // связанную с переменными, struct var_type {
char var_name [MAX_ID_LEN+1 ]; // имя
token_ireps v_type; // тип данных
int value; // значение
>;
// Этот вектор содержит информацию о глобальных переменных. vector<var_type> global_vars;
// Этот вектор содержит информацию о локальных переменных //и параметрах.
vector<var_type> local_var_stack;
// Эта структура инкапсулирует данные о функции, struct func_type {
char f unc_name [MAX_ID_LEN+1 ]; // имя
token_ireps ret_type; // тип возвращаемого значения
char *loc; // положение точки входа в программе
};
// Этот вектор содержит информацию о функциях. vector<func_type> func_table;
// Стек для управления областью видимости функции. stack<int> func_call_stack;
// Стек для управления вложенными областями. stack<int> nest_scope_stack;
char token[MAX_T_LEN+1]; // текущая лексема
tok_types token_type; // тип лексемы
token_ireps tok; // внутреннее представление
int ret_value; // значение, возвращаемое функцией
bool breakfound = false; // true, если обнаружен оператор break
int main(int argc, char *argv[]) {
if(argc != 2)
cout « "Usage: minicpp <filename>\n"; return 1;
}
// Выделяет память для программы, try {
p_buf = new char[PROG_SIZE]; } atch (bad_alloc exc) {
cout « "Could Not Allocate Program Buffer\n"; return 1;
}
// Загружает программу для выполнения.
i f(!loacLprogram(p_buf, argv[1])) return 1;
// Устанавливает указатель программы на начало программного буфера, prog = p_buf;
try {
// Находит местоположение всех функций //и глобальных переменных в программе. prescanO ;
// Затем подготавливает вызов функции main О .
// Находит начальную точку программы, prog = find_func("main");
// Проверяет некорректность функции main() // или ее отсутствие, if(!prog) {
cout « "main() Not FoundNn";
return 1;
}
// Возвращается к открывающей скобке {. prog--;
// Устанавливает значение первой лексемы, равное main, strcpy(token, "main");
// Вызывает main(), чтобы начать интерпретацию. callO;
}
catch(InterpExc exc) { sntx_err(exc.get_err()); return 1;
)
catch(bad_alloc exc) {
cout « "Out Of Memory\n"; return 1;
}
return ret_value;
}
// Загружает программу.
bool load_program(char *р, char * fname)
{
int i=0;
ifstream in(fname, ios::in | ios::binary); if(!in) {
cout « "Cannot Open file.\n";
return false;
}
do {
*p = in.getO; p++; i++;
} while(!in.eof() && i < PROGJSIZE); if(i == PROGLSIZE) {
cout « "Program Too Big\n"; return false;
}
// Завершает нулем код программы. Пропускает любую метку // EOF, присутствующую в файле. if(*(p-2) == Oxla) *(р-2) = '\0'; else *(р-1) = '\0';
in.close();
return true;
>
// Находит местоположение всех функций в программе //и запоминает глобальные переменные, void prescanO {
char *р, *tp;
char temp[MAX_ID_LEN+1];
token_ireps datatype;
func_type ft;
// Если brace равна 0, текущая позиция, в коде // находится за пределами любой функции, int brace = 0;
р = prog;
do {
// Обходит код тела функции while(brace) { get_token();
if(tok == END) throw InterpExc(UNBAL_BRACES); if(*token == '{') brace++; if(*token == '}') brace—;
}
tp = prog; // сохраняет текущую позицию get_token();
// Проверяет, не тип ли глобальной переменной или возвращаемого // значения функции. if(tok==CHAR || tok==INT) {
datatype = tok; // сохраняет тип данных get_token();
if(token_type == IDENTIFIER) { s trcpy(temp, token); get_token();
if(*token != '(') I // должна быть глобальная переменная prog = tp; // возвращается к началу объявления decl^global();
. )
else if(*token == '(') { // должна быть функция
// Проверяет, не определена ли уже функция, for(unsigned i=0; i < func_table.size(); i++) i f(!s trcmp (func_table[i].func_name, temp))
throw InterpExc(DUP_FUNC);
ft.loc = prog; ft.ret_type = datatype; s trcpy(ft.func_name, temp); func_table. push_back (f t) ;
do {
get_token(); } while(*token != ')•);
// Теперь следующей лексемой будет открывающая // фигурная скобка тела функции.
}
else putback();
}
}
else {
if(*to"ken == '{') brace++; if(*token == *}') brace—;
)
} while(tok != END);
k
if(brace) throw InterpExc(UNBAL_BRACES); prog = p;
}
// Интерпретирует отдельный оператор или блок кода. Функция
// interp() возвращается из первоначального вызова, если обнаружена
// конечная фигурная скобка (или return) в функции main().
void interpO
{
int value; int block = 0;
do {
// He интерпретирует, пока не обработан break, if(breakfound) return;
token_type = get_token () ;
// Определяет, какая лексема представлена.
if(token_type == IDENTIFIER || *token == INC || *token == DEC)
{
//He ключевое слово, поэтому обрабатывает выражение. putbackO; // возвращает лексему во входной поток
// для последующей обработки с помощью eval_exp() eval_exp(value); // обрабатывает выражение if(*token != ';')?throw InterpExc(SEMI_EXPECTED);
}
else if(token_type==BLOCK) { // ограничитель блока if(*token =="){// блок
block =1; // интерпретирует блок, а не оператор // Записывает вложенную область видимости. nest_scope_stack.push(local_var_stack.size());
}
else { // фигурная скобка }, поэтому восстанавливает область // видимости и возвращается // Восстанавливает вложенную область видимости. local_var_stack.resize(nest_scope_stack.top()); nes t_scope_stack.pop(); 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 BREAK: // обрабатывает break breakfound = true;
// Восстанавливает вложенную область видимости. local_var_stack.resize(nest_scope_stack.top()); nest_scope_stack.pop(); return;
case SWITCH: // обрабатывает оператор switch exec_switch () ; break;
case COUT: // обрабатывает консольный вывод exec_cout(); break;
case CIN: // обрабатывает консольный ввод
exec_cin() ;
break; case END:
exit(O);
}
} while (tok != END && block); return;
}
// Возвращает точку входа заданной функции. // Возвращает NULL, если не найдена, char *find_func(char *name) {
unsigned i;
for(i=0; i < func_table.size(); i++)
i f (! s t rcmp (name, f unc_tabl e [ i ]. f unc_name)) return func_table[i].loc; return NULL;
}
// Объявление глобальной переменной.
void decl_global()
{
token_ireps vartype; var_type vt;
get_token(); // получает тип
vartype = tok; // сохраняет тип переменной
// Обрабатывает список, разделенный запятыми, do {
vt.v_type = vartype;
vt.value =0; // инициализирует с нулевым значением get_token(); // получает имя
// Проверяет, не дублируется ли переменная, for(unsigned i=0; i < global_vars.size(); i++) i f(!s trcmp(global_vars[i].var_name. token)) throw InterpExc(DUP_VAR);
strcpy(vt.var_.name, token) ; global_vars.push_back(vt);
get_token(); } while(*token == ',');
if(*token != ';') throw InterpExc(SEMI_EXPECTED);
}
// Объявление локальной переменной.
void decl_local()
{
var_type vt;
get_token(); // получает тип переменной vt.v_type = tok; // запоминает тип
vt.value =0; // инициализирует переменную с нулевым значением
// Обрабатывает список, разделенный запятыми, do I
get_token(); // get var name
// Проверяет, нет ли уже в этой области видимости переменной //с тем же именем, что и у локальной переменной, if(!local_var_stack.empty()) for(int i=local_var_stack.size()-1; i >= nest_scope_stack.top(); i—)
{
if(!strcmp (local_var_stack[i].var_name, token)) throw InterpExc(DUP_VAR);
}
s trcpy(vt.var_name, token); local_var_s tack~. push_back (vt) ; get_token(); } while(*token == ',*);
if(*token != •;•) throw InterpExc(SEMI_EXPECTED);
}
// Вызывает функцию.
void call()
{
char *loc, *temp; int lvartemp;
// Сначала находит точку входа функции, loc = find_func(token);
if(loc == NULL)
throw InterpExc(FUNC_UNDEF); // функция не определена
else {
// Сохраняет индекс стека локальных переменных, lvartemp = local_var_stack.size();
get_args(); // получает аргументы функции
temp = prog; // сохраняет местоположение return
func_.call_stack.push(lvartemp); // заносит в стек индекс локальной // переменной
prog = loc; // переустанавливает prog на начало функции get_params(); // загружает параметры функции //со значениями аргументов
interpO; // интерпретирует функцию
prog = temp; // переустанавливает программный указатель
if(func_call_stack.empty()) throw InterpExc(RETJNOCALL);
// Восстанавливает прежнее состояние local_var_stack. local_var_stack.resize(func_call_stack.top()); f unc_cal l_s tack. pop () ;
}
}
// Заносит аргументы функции в стек // локальных переменных, void get_args() {
int value, count, temp[NUM_PARAMS] ; var_type vt;
count = 0; get_token();
if(*token '= '(') throw InterpExc(PAREN_EXPECTED);
// Обрабатывает разделенный запятыми список значений, do {
eval_exp(value);
temp [covint] = value; // сохраняет временно
get_token();
count++; } while(*token == *, '); count—;
// Теперь заносит в local_var_stack в обратном порядке. for(; count>=0; count—) {
vt.value = temp [count];
vt.v_type = ARG;
1ocai_var_stack.push_back(vt);
}
}
// Получает параметры функции.
void get_params()
{
var_type *p; int i;
i = local_var_stack.size()-1;
// Обрабатывает разделенный запятыми список параметров, do {
get_token();
р = &local_var_stack[i]; if(*token •=')'){
if (tok != INT ScSc tok != CHAR)
throw InterpExc(TYPE_EXPECTED);
p->v_type = tok; get_token();
// Связывает имя параметра с аргументом, который уже в // стеке локальных переменных. strcpy(p->var_name, token);
get_token(); (
i—;
}
else break; } while(*token == ',');
if(*token != •)') throw InterpExc(PAREN_EXPECTED);
}
// Обработка возврата из функции.
void func_ret()
{
int value; value = 0;
// Получает значение return, если есть. eval_exp(value); ret_value = value;
}
// Присваивает значение переменной, void assign_var(char *vname, int value) {
// Сначала проверяет, не локальная ли это переменная, if(!local_var_stack.empty())
for4dnt i=local_var_stack.size()-1; i >= func_call_stack.top(); i—)
{
i f(!strcmp(1ocal_var_s tack[i].var_name. vname))
{
if(local_var_stackIi].v_type == CHAR) local_var_stack[i].value = (char) value;
else if(local_var_stack[i].v_type == INT) local_var_stack[i].value = value;
return;
}
}
// В противном случае проверяет глобальные переменные for(unsigned i=0; i < global_vars.size(); i++)
if (!scrcmp(global_vars [i] .varname, vname)) { if(global_vars[i].v_type == CHAR)
global_vars[i].value = (char) value; else if(global_vars[i].v_type == INT)
global_vars[i].value = value; return;
}
throw InterpExc(NOT_VAR); // переменная не найдена
}
// Находит значение переменной.
int find_var(char *vname)
{
// Сначала проверяет, не локальная ли переменная, if(!local_var_stack.empty())
for(int i=local_var_s tack.s ize()-1; i >= func_call_stack.top(); i—)
{
i f(!s trcmp (local_var_s tack[i].var_name, vname)) return local_var_stack[i].value;
}
// В противном случае проверяет глобальные переменные, for(unsigned i=0; i < global_vars.size(); i++)
i f(!s trcmp (global_vars[i].var_name, vname))
return global_vars[i].value;
throw InterpExc(NOT_VAR); // переменная не найдена
}
// Выполняет оператор if.
void exec_ifО
{
int cond;
eval_exp(cond); // получает выражение оператора if.
if(cond) { // если true, обрабатывает блок в составе IF
'// Подтверждает начало блока. if(*token != '{')
throw InterpExc(BRACE_EXPECTED);
interp();
}
else {
// В противном случае пропускает блок IF и // обрабатывает ELSE, если он есть.
find_eob(); // находит начало следующей строки get_token();
if(tok != ELSE) (
// Возвращает лексему, если нет ELSE.
putback();
return;
}
// Подтверждает начало блока.
get_token();
if(*token != '{')
throw InterpExc(BRACE_EXPECTED); putback();
interp();
)
}
// Выполняет оператор switch.
void exec_switch ()
{
int sval, cval; int brace;
eval_exp(sval); // Получает выражение switch.
// Проверяет начало блока. if(*token != '{') throw InterpExc(BRACE_EXPECTED);
// Записывает новую область видимости. nest_scope_stack.push(local_var_stack.size());
// Теперь проверяет варианты case. for(;;) { brace = 1;
// Находит вариант case, do {
get_token();
if(*token == '{') brace++; else if(*token == '}') brace—; } while(tok != CASE && tok != END && brace);
// Если соответствующего варианта case не найдено, то пропускает, i f(!brace) break;
if(tok == END) throw InterpExc(SYNTAX);
// Получает значение варианта case. eval_exp (cval) ;
// Читает и отбрасывает ":и. get_token();
if(*token != *:1)
throw InterpExc(COLON_EXPECTED);
// Если значения совпадают, то интерпретирует, if(cval == sval) {
brace = 1;
do {
interp();
if(*token == '{') brace++; else if(*token == '}') brace—; } while(Ibreakfound && tok != END && brace);
II Находит конец оператора switch, while(brace) { get_token();
if(*token == '{') brace++; else if(*token == '}') brace—;
J
breakfound = falser-break;
}
}
}
// Выполняет цикл while.
void exec_while()
{
int cond; char *cerap;
putbackO; // возвращает во входной поток лексему while temp = prog; // сохраняет адрес начала цикла while
get_token();
eval_exp(cond); // проверяет условное выражение
// Подтверждает начало блока. if(*token != '{')
throw InterpExc(BRACE_EXPECTED);
if(cond)
interpO; // если true, интерпретирует else { // в противном случае переходит к концу цикла find_eob(); return;
}
prog = temp; // возвращается к началу // Ищет оператор break в цикле.
if(breakfound) {
// Ищет начало блока в цикле, do {
get_token(); } while(*token != •{' tok != END);
putback();
breakfound = false;
find_eob(); // теперь ищет конец цикла return;
}
}
// Выполняет цикл do.
void exec_do()
{
int cond; char *temp;
// Сохраняет местоположение начала цикла do. putbackO; // возвращает во входной поток лексему do temp = prog;
get_token(); // получает начало блока цикла
// Подтверждает начало блока. get_token(); if(*token != '{')
throw InterpExc(BRACE_EXPECTED); putback();
interpO; // интерпретирует цикл
// Ищет оператор break в цикле, if(breakfound) { prog = temp;
// Находит начало блока в цикле, do {
get_token();
} while(*token != '{' && tok != END);
// Находит конец блока while, putback(); finc_eob();
// Теперь находит конец выражения while, do {
get_token(); } while(*token != ';' && tok != END); if(tok == END) throw InterpExc(SYNTAX);
breakfound = false; return;
}
get_token();
if(tok ! = WHILE) throw InterpExc(WHILE_EXPECTED); eval_exp(cond); // проверяет условие цикла
// Если true, повторяет цикл; в противном случае идет дальше, if(cond) prog = temp;
}
// Выполняет цикл for.
void exec_for()
{
int cond;
char *temp, *temp2; int paren ;
get_token(); // пропускает открывающую скобку ( eval_exp(cond); // выражение инициализации
if(*token != ';') throw InterpExc(SEMI_EXPECTED); prog++; // переходит за ";" в исходном коде temp = prog;
for(;;) {
// Получает значение условного выражения. eval_exp(cond);
if(*token != ';*) throw InterpExc(SEMI_EXPECTED); prog++; // переходит за в исходном коде temp2 = prog;
// Ищет начало блока for. paren = 1; while(paren) { get_token();
if(*token == '(') paren++; if(*token == ')') paren—;
}
// Подтверждает начало блока. get_token () ; if(*token != '{')
throw InterpExc(BRACE_EXPECTED); putback();
// Если условие true, интерпретирует, if(cond) interp();
else { // в противном случае переходит к концу блока find_eob() ; return;
}
prog = temp2; // переходит к инкрементному выражению
// Ищет оператор break в цикле, if(breakfound) {
// Ищет начало блока в цикле.
do {
get_token () ;
} while(*token != '{' && tok != END);
putback();
breakfound = false;
find_eob(); // теперь ищет конец цикла return;
}
// Вычисляет инкрементное выражение. eval_exp(cond);
prog = temp; // возвращается к началу цикла
}
}
// Выполняет оператор cout.
void exec_cout()
{
int val; get_token();
if(*token != LS) throw InterpExc(SYNTAX);
do {
get_token();
if(token_type==STRING) { // Выводит строку, cout « token;
)
else if(token_type == NUMBER ||
token_type == IDENTIFIER) { // Выводит число, putback(); eval_exp (val) ; cout « val;
}
else if(*token == ' \ ' ') {
// выводит символьную константу, putback(); eval_exp(val);
cout « (char) val;
get_token(); } while(*token == LS);
if(*token != ';') throw InterpExc(SEMI_EXPECTED);
}
// Выполняет оператор cin.
void exec_cin()
{
int val; char chval; token_ireps vtype;
get_token();
if(*token != RS) throw InterpExc(SYNTAX);
do {
get_token();
if(token_type != IDENTIFIER) throw InterpExc(NOT_VAR);
vtype = find_var_type(token);
if(vtype == CHAR) { cin » chval; assign_yar(token, chval);
>
else if(vtype == INT) { cin » val;
assign_var(token, va1);
}
get_token(); } while(*token == RS);
if(*token != ';') throw InterpExc(SEMI_EXPECTED);
}
}
// Находит конец блока.
void find_eob()
{
int brace;
get_token();
if(*token != '{')
throw InterpExc(BRACE_EXPECTED);
brace = 1;
do {
get_token();
if(*token == '{') brace++; else if(*token == '}') brace—; } while(brace && tok != END);
if(tok==END) throw InterpExc(UNBAL_BRACES);
)
// Определяет, является ли идентификатор переменной. Возвращает // true, если найдена переменная; false — в противном случае, bool is_var(char * vname) {
// Проверяет, является ли vname локальной переменной, if(!local_var_stack.empty())
for(int i=local_var_stack.size()-1; i >= func_call_stack.top(); i—)
{
if(!strcmp(local_var_stack[i].var_name, vname)) return true;
}
// Проверяет, является ли vname глобальной переменной, for(unsigned i=0; i < global_vars.size(); i++) if(!strcrap(global_vars[i].var_name, vname)) return true;
return false;
// Возвращает тип переменной. token_ireps find_var_type(char *vname) {
// Сначала проверяет, не локальная ли это переменная, if(!local_var_stack.empty())
for(int i=local_var_stack.size()-1; i >= func_call_stack.top(); i—)
{
i f(!strcmp(local_var_stack[i].var_name, vname)) return local_var_stack[i].v_type;
}
// В противном случае, не глобальная ли. for(unsigned i=0; i < global_vars.size(); i++) if(!strcmp (global_vars[i].var_name, vname)) return local_var_stack[i].v_type;
return UNDEFTOK;
}
|
|
|
|
|
