ЭВМ
Разработка интерпретатора
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*);
Обе функции возвращают указатель на ту запись name, которая соответствует их параметру-строке. Функция look() "ругается", если имя не было занесено в таблицу. Это означает, что в калькуляторе можно использовать имя без предварительного описания, но в первый раз оно может появиться только в левой части присваивания.
3. Функция ввода
Получение входных данных - часто самая запутанная часть программы. Причина кроется в том, что программа должна взаимодействовать с пользователем, то есть "мириться" с его прихотями, учитывать принятые соглашения и предусматривать кажущиеся редкими ошибки.
Попытки заставить человека вести себя более удобным для машины образом, как правило, рассматриваются как неприемлемые, что справедливо.
Задача ввода для функции низкого уровня состоит в последовательном считывании символов и составлении из них лексемы, с которой работают уже функции более высокого уровня. В этом примере низкоуровневый ввод делает функция get_token().
Правила ввода для интерпретатора были специально выбраны несколько громоздкими для потоковых функций ввода. Незначительные изменения в определениях лексем превратили бы get_token() в обманчиво простую функцию.
Первая сложность состоит в том, что символ конца строки '\n' важен для калькулятора, но потоковые функции ввода воспринимают его как символ обобщенного пробела. Иначе говоря, для этих функций '\n' имеет значение только как символ, завершающий лексему.
Поэтому приходится анализировать все обобщенные пробелы (пробел, табуляция и т.п.). Это делается в операторе do :
char ch;
do { // пропускает пробелы за исключением '\n'
if(!cin.get(ch)) return curr_tok = END;
} while (ch!='\n' && isspace(ch));
Функция cin.get(ch) читает один символ из стандартного входного потока в ch. Значение условия if(!cin.get(ch)) - ложь, если из потока cin нельзя получить ни одного символа. Тогда возвращается лексема END, чтобы закончить работу калькулятора. Операция ! (NOT) нужна потому, что в случае успешного считывания get() возвращает ненулевое значение.
Функция-подстановка isspace() из <ctype.h> проверяет, не является ли ее параметр обобщенным пробелом. Она возвращает ненулевое значение, если является, и нуль в противном случае. Проверка реализуется как обращение к таблице, поэтому для скорости лучше вызывать isspace(), чем проверять самому. То же можно сказать о функциях isalpha(), isdigit() и isalnum(), которые используются в get_token().
После пропуска обобщенных пробелов следующий считанный символ определяет, какой будет начинающаяся с него лексема. Прежде, чем привести всю функцию, рассмотрим некоторые случаи отдельно. Лексемы '\n' и ';', завершающие выражение, обрабатываются следующим образом:
switch (ch) {
case ';':
case '\n':
cin >> ws; // пропуск обобщенного пробела
return curr_tok=PRINT;
Необязательно снова пропускать пробел, но, сделав это, мы избежим повторных вызовов функции get_token(). Переменная ws, описанная в файле <stream.h>, используется только как приемник ненужных пробелов.
Ошибка во входных данных, а также конец ввода не будут обнаружены до следующего вызова функции get_token(). Обратите внимание, как несколько меток выбора помечают одну последовательность операторов, заданную для этих вариантов. Для обоих символов ('\n' и ';') возвращается лексема PRINT, и она же помещается в curr_tok.
Числа обрабатываются следующим образом:
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
case '.':
cin.putback(ch);
cin >> number_value;
return curr_tok=NUMBER;
Поскольку оператор >> может читать константу с плавающей точкой типа double, программа тривиальна: прежде всего начальный символ (цифра или точка) возвращается назад в cin, а затем константу можно считать в number_value. Имя, т.е. лексема NAME, определяется как буква, за которой может идти несколько букв или цифр: