46190 (Системное программное обеспечение), страница 2

int ii = 0; // хэш-код

const char* pp = p;

while (*pp) ii = ii<<1 ^ *pp++;

if (ii < 0) ii = -ii;

ii %= TBLSZ;

Иными словами, с помощью операции ^ ("исключающее ИЛИ") все символы входной строки p поочередно добавляются к ii. Разряд в результате x^y равен 1 тогда и только тогда, когда эти разряды в операндах x и y различны.

До выполнения операции ^ значение ii сдвигается на один разряд влево, чтобы использовался не только один байт ii. Эти действия можно записать таким образом:

ii <<= 1;

ii ^= *pp++;

Для хорошего хэш-кода лучше использовать операцию ^, чем +. Операция сдвига важна для получения приемлемого хэш-кода в обоих случаях.

Операторы

if (ii < 0) ii = -ii;

ii %= TBLSZ;

гарантируют, что значение ii будет из диапазона 0...TBLSZ-1. Напомним, что % - это операция взятия остатка. Ниже полностью приведена функция look:

#include

name* look(const char* p, int ins =0)

{

int ii = 0; // хэш-код

const char* pp = p;

while (*pp) ii = ii<<1 ^ *pp++;

if (ii < 0) ii = -ii;

ii %= TBLSZ;

for (name* n=table[ii]; n; n=n->next) // поиск

if (strcmp(p,n->string) == 0) return n;

if (ins == 0) error("имя не найдено");

name* nn = new name; // занесение

nn->string = new char[strlen(p)+1];

strcpy(nn->string,p);

nn->value = 1;

nn->next = table[ii];

table[ii] = nn;

return nn;

}

После вычисления хэш-кода ii идет простой поиск имени по членам next. Имена сравниваются с помощью стандартной функции сравнения строк strcmp(). Если имя найдено, то возвращается указатель на содержащую его запись, а в противном случае заводится новая запись с этим именем.

Добавление нового имени означает создание нового объекта name в свободной памяти с помощью операции new, его инициализацию и включение в список имен. Последнее выполняется как занесение нового имени в начало списка, поскольку это можно сделать даже без проверки того, есть ли список вообще. Символьная строка имени

также размещается в свободной памяти. Функция strlen() указывает, сколько памяти нужно для строки, операция new отводит нужную память, а функция strcpy() копирует в нее строку. Все строковые функции описаны в :

extern int strlen(const char*);

extern int strcmp(const char*, const char*);

extern char* strcpy(char*, const char*);

5. Обработка ошибок

Поскольку программа достаточно проста, не надо особо беспокоиться об обработке ошибок. Функция error просто подсчитывает число ошибок, выдает сообщение о них и возвращает управление обратно:

int no_of_errors;

double error(const char* s)

{

cerr << "error: " << s << "\n";

no_of_errors++;

return 1;

}

Небуферизованный выходной поток cerr обычно используется именно для выдачи сообщений об ошибках.

Управление возвращается из error() потому, что ошибки, как правило, встречаются посреди вычисления выражения. Значит надо либо полностью прекращать вычисления, либо возвращать значение, которое не должно вызвать последующих ошибок. Для простого калькулятора больше подходит последнее. Если бы функция get_token() отслеживала номера строк, то функция error() могла бы указывать пользователю приблизительное место ошибки. Это было бы полезно при неинтерактивной работе с калькулятором.

Часто после появления ошибки программа должна завершиться, поскольку не удалось предложить разумный вариант ее дальнейшего выполнения. Завершить ее можно с помощью вызова функции exit(), которая заканчивает работу с выходными потоками и завершает программу, возвращая свой параметр в качестве ее результата.

6. Драйвер

Когда все части программы определены, нужен только драйвер, чтобы инициализировать и запустить процесс. В нашем примере с этим справится функция main():

int main()

{

// вставить предопределенные имена:

insert("pi")->value = 3.1415926535897932385;

insert("e")->value = 2.7182818284590452354;

while (cin) {

get_token();

if (curr_tok == END) break;

if (curr_tok == PRINT) continue;

cout << expr() << '\n';

}

return no_of_errors;

}

Принято, что функция main() возвращает нуль, если программа завершается нормально, и ненулевое значение, если происходит иначе. Ненулевое значение возвращается как число ошибок. Оказывается, вся инициализация сводится к занесению предопределенных имен в таблицу.

В цикле main читаются выражения и выдаются результаты. Это делает одна строка:

cout << expr() << '\n';

7. Параметры командной строки

Для удобства пользования интерпретатором используем параметры командной строки.

Как уже было сказано, выполнение программы начинается вызовом main(). При этом вызове main() получает два параметра: число параметров (обычно называемый argc) и массив строк параметров (обычно называемый argv).

Параметры - это символьные строки, поэтому argv имеет тип char*[argc+1]. Имя программы (в том виде, как оно было задано в командной строке) передается в argv[0], поэтому argc всегда не меньше единицы. Например, для командной строки

dc 150/1.1934

параметры имеют значения:

argc 2

argv[0] "dc"

argv[1] "150/1.1934"

argv[2] 0

int main(int argc, char* argv[])

{

switch(argc) {

case 1: // считывать из стандартного входного потока

break;

case 2: // считывать из строки параметров

cin = *new istream(argv[1],strlen(argv[1]));

break;

default:

error("слишком много параметров");

return 1;

}

// вставить предопределенные имена:

insert("pi")->value = 3.1415926535897932385;

insert("e")->value = 2.7182818284590452354;

while (cin) {

get_token();

if (curr_tok == END) break;

if (curr_tok == PRINT) continue;

cout << expr() << '\n';

}

return no_of_errors;

}

При этом istrstream - это функция istream, которая считывает символы из строки, являющейся ее первым параметром. Чтобы использовать istrstream нужно включить в программу файл , а не обычный . В остальном же программа осталась без изменений, кроме добавления параметров в функцию main() и использования их в операторе switch. Можно легко изменить функцию main() так, чтобы она могла принимать несколько параметров из командной строки. Однако это не слишком нужно, тем более, что можно нескольких выражений передать как один параметр:

dc "rate=1.1934;150/rate;19.75/rate;217/rate"

Кавычки необходимы потому, что символ ';' служит в системе UNIX разделителем команд. В других системах могут быть свои соглашения о параметрах командной строки.

8. Полный вариант программы:

#include

#include

#include

enum token_value {

NAME, NUMBER, END,

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

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

};

token_value curr_tok;

struct name {

char* string;

name* next;

double value;

};

const TBLSZ = 23;

name* table[TBLSZ];

int no_of_errors;

double error(char* s) {

cerr << "error: " << s << "\n";

no_of_errors++;

return 1;

}

name* look(char* p, int ins = 0)

{

int ii= 0;

char *pp = p;

while (*pp) ii = ii<<1 ^ *pp++;

if (ii < 0) ii = -ii;

ii %= TBLSZ;

for (name* n=table [ii]; n; n=n->next)

if (strcmp(p,n->string) == 0) return n;

if (ins == 0) error("name not found");

name* nn = new name;

nn->string = new char[strlen(p) + 1];

strcpy(nn->string,p);

nn->value = 1;

nn->next = table[ii];

table[ii] = nn;

return nn;

}

inline name* insert(char* s) { return look (s,1); }

token_value get_token();

double term();

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;

}

}

double prim();

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("divide by o");

left /= d;

break;

default:

return left;

}

}

int number_value;

char name_string[80];

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(") expected");

get_token();

return e;

case END:

return 1;

default:

return error ("primary expected");

}

}

token_value get_token()

{

char ch = 0;

do {

if(!cin.get(ch)) return curr_tok = END;

} while (ch!='\n' && isspace(ch));

switch (ch) {

case ';':

case '\n':

cin >> WS;

return curr_tok=PRINT;

case '*':

case '/':

case '+':

case '-':

case '(':

case ')':

case '=':

return curr_tok=ch;

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;

default:

if (isalpha(ch)) {

char* p = name_string;

*p++ = ch;

while (cin.get(ch) && isalnum(ch)) *p++ = ch;

cin.putback(ch);

*p = 0;

return curr_tok=NAME;

}

error ("bad token");

return curr_tok=PRINT;

}

}

int main(int argc, char* argv[])

{

switch (argc) {

case 1:

break;

case 2:

cin = *new istream(strlen(argv[1]),argv[1]);

break;

default:

error("too many arguments");

return 1;

}

// insert predefined names:

insert("pi")->value = 3.1415926535897932385;

insert("e")->value = 2.7182818284590452354;

while (1) {

get_token();

if( curr_tok == END) break;

if (curr_tok == PRINT) continue;

cout << expr() << "\n";

}

return no_of_errors;

}