1. Общее описание.

Данный интерпретатор реализует основных арифметических действия в виде инфиксных операций над числами с плавающей точкой. Например входной поток имеет вид:

r=2.5

area=pi*r*r

(здесь pi имеет предопределенное значение). Тогда программа калькулятора

выдаст:

2.5

19.635

Результат вычислений для первой входной строки равен 2.5, а результат для второй строки - это 19.635. Программа интерпретатора состоит из четырех основных частей: анализатора, функции ввода, таблицы имен и драйвера.

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

2. Анализатор.

Грамматика языка калькулятора определяется следующими правилами:

программа:

END // END - это конец ввода

список-выражений END

список-выражений:

выражение PRINT // PRINT - это '\n' или ';'

выражение PRINT список-выражений

выражение:

выражение + терм

выражение - терм

терм

терм:

терм / первичное

терм * первичное

первичное

первичное:

NUMBER // число с плавающей запятой в С++

NAME // имя в языке С++ за исключением '_'

NAME = выражение

- первичное

( выражение )

Иными словами, программа есть последовательность строк, а каждая строка содержит одно или несколько выражений, разделенных точкой с запятой. Основные элементы выражения - это числа, имена и операции *, /, +, - (унарный и бинарный минус) и =. Имена необязательно описывать до использования.

Для синтаксического анализа используется метод, обычно называемый рекурсивным спуском. Это распространенный и достаточно очевидный метод. В таких языках как С++, то есть в которых операция вызова не сопряжена с большими накладными расходами, это метод эффективен. Для каждого правила грамматики имеется своя функция, которая вызывает другие функции. Терминальные символы (например, END, NUMBER, + и -) распознаются лексическим анализатором get_token(). Нетерминальные символы распознаются функциями синтаксического анализатора expr(), term() и prim(). Как только оба операнда выражения или подвыражения стали известны, оно вычисляется. В настоящем трансляторе в этот момент создаются команды, вычисляющие выражение.

Анализатор использует для ввода функцию get_token(). Значение последнего вызова get_token() хранится в глобальной переменной curr_tok. Переменная curr_tok принимает значения элементов перечисления token_value:

enum token_value {

NAME, NUMBER, END,

PLUS='+', MINUS='-', MUL='*', DIV='/',

PRINT=';', ASSIGN='=', LP='(', RP=')'

};

token_value curr_tok;

Для всех функций анализатора предполагается, что get_token() уже была вызвана, и поэтому в curr_tok хранится следующая лексема, подлежащая анализу. Это позволяет анализатору заглядывать на одну лексему вперед. Каждая функция анализатора всегда читает на одну лексему больше, чем нужно для распознавания того правила, для которого она вызывалась. Каждая функция анализатора вычисляет "свое" выражение и возвращает его результат. Функция expr() обрабатывает сложение и вычитание. Она состоит из одного цикла, в котором распознанные термы складываются или вычитаются:

double expr() // складывает и вычитает

{

double left = term();

for(;;) // ``вечно''

switch(curr_tok) {

case PLUS:

get_token(); // случай '+'

left += term();

break;

case MINUS:

get_token(); // случай '-'

left -= term();

break;

default:

return left;

}

}

Отметим, что выражения вида 2-3+4 вычисляются как (2-3)+4, что предопределяется правилами грамматики.

Функция term() справляется с умножением и делением аналогично тому, как функция expr() со сложением и вычитанием:

double term() // умножает и складывает

{

double left = prim();

for(;;)

switch(curr_tok) {

case MUL:

get_token(); // случай '*'

left *= prim();

break;

case DIV:

get_token(); // случай '/'

double d = prim();

if (d == 0) return error("деление на 0");

left /= d;

break;

default:

return left;

}

}

Проверка отсутствия деления на нуль необходима, поскольку результат деления на нуль неопределен и, как правило, приводит к катастрофе.

Функция error() будет рассмотрена позже. Переменная d появляется в программе там, где она действительно нужна, и сразу же инициализируется.

Функция prim, обрабатывающая первичное, во многом похожа на функции expr и erm().

double number_value;

char name_string[256];

double prim() // обрабатывает первичное

{

switch (curr_tok) {

case NUMBER: // константа с плавающей точкой

get_token();

return number_value;

case NAME:

if (get_token() == ASSIGN) {

name* n = insert(name_string);

get_token();

n->value = expr();

return n->value;

}

return look(name_string)->value;

case MINUS: // унарный минус

get_token();

return -prim();

case LP:

get_token();

double e = expr();

if (curr_tok != RP) return error("требуется )");

get_token();

return e;

case END:

return 1;

default:

return error("требуется первичное");

}

}

Когда появляется NUMBER (то есть константа с плавающей точкой), возвращается ее значение. Функция ввода get_token() помещает значение константы в глобальную переменную number_value. Если в программе используются глобальные переменные, то часто это указывает на то, что структура не до конца проработана, и поэтому требуется некоторая оптимизация. Именно так обстоит дело в данном случае. В идеале лексема должна состоять из двух частей: значения, определяющего вид лексемы

(в данной программе это token_value), и (если необходимо) собственно значения лексемы. Здесь же имеется только одна простая переменная curr_tok, поэтому для хранения последнего прочитанного значения NUMBER требуется глобальная переменная number_value. Такое решение проходит потому, что калькулятор во всех вычислениях вначале выбирает одно число, а затем считывает другое из входного потока.

Если последнее значение NUMBER хранится в глобальной переменной number_value, то строковое представление последнего значения NAME хранится в name_string. Перед тем, как что-либо делать с именем, интерпретатор должен заглянуть вперед, чтобы выяснить, будет ли ему присваиваться значение, или же будет только использоваться существующее его значение. В обоих случаях надо обратиться к таблице имен. Эта таблица состоит из записей, имеющих вид:

struct name {

char* string;

name* next;

double value;

};

Член next используется только служебными функциями, работающими с таблицей:

name* look(const char*);

name* insert(const char*);