Бьерн Страуструп. Язык программирования С++

возвращается лексема PRINT, и она же помещается в curr tok. Числа обрабатываются следующим образом:

cin.putback(ch); cin >> number value; return curr tok=NUMBER;

Размещать метки вариантов горизонтально, а не вертикально,- не самый лучший способ, поскольку такой текст труднее читать; но писать строку для каждой цифры утомительно. Поскольку оператор >> может читать константу с плавающей точкой типа double, программа тривиальна: прежде всего начальный символ (цифра или точка) возвращается назад в cin, а затем константу можно считать в number value. Имя, т.е. лексема NAME, определяется как буква, за которой может идти несколько букв или цифр:

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;

Этот фрагмент программы заносит в name string строку, оканчивающуюся нулевым символом. Функции isalpha() и isalnum() определены в <ctype.h>. Результат isalnum(c) ненулевой, если c - буква или цифра, и нулевой в противном случае.

Приведем, наконец, функцию ввода полностью:

token value get token()

char ch;

do { пропускает обобщенные пробелы за исключением \n

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=token value(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: NAME, NAME= или ошибка

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( недопустимая лексема ); return curr tok=PRINT;

Преобразование операции в значение лексемы для нее тривиально, поскольку в перечислении token value лексема операции была определена как целое (код символа операции).

3.1.3 Таблица имен

Есть функция поиска в таблице имен:

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

Второй ее параметр показывает, была ли символьная строка, обозначающая имя, ранее занесена в таблицу. Инициализатор =0 задает стандартное значение параметра, которое используется, если функция look() вызывается только с одним параметром. Это удобно, так как можно писать look( sqrt2 ), что означает look( sqrt2 ,0), т.е. поиск, а не занесение в таблицу. Чтобы было так же удобно задавать операцию занесения в таблицу, определяется вторая функция:

inline name* insert(const char* s) { return look(s,1); } Как ранее упоминалось, записи в этой таблице имеют такой тип:

struct name { char* string; name* next; double value;

Член next используется для связи записей в таблице. Собственно таблица - это просто массив указателей на объекты типа name:

const TBLSZ = 23; name* table[TBLSZ];

Поскольку по умолчанию все статические объекты инициализируются нулем, такое тривиальное описание таблицы table обеспечивает также и нужную инициализацию.

Для поиска имени в таблице функция look() использует простой хэш-код (записи, в которых имена имеют одинаковый хэш-код, связываются вместе):

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

const char* pp = p; while (*pp) ii = ii<<1 *pp++; if (ii < 0) ii = -ii; ii %= TBLSZ;

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

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

ii <<= 1;

ii = *pp++;

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

if (ii < 0) ii = -ii; ii %= TBLSZ;

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

#include <string.h>

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 (см. $$3.2.6), его инициализацию и включение в список имен. Последнее выполняется как занесение нового имени в начало списка, поскольку это можно сделать даже без проверки того, есть ли список вообще. Символьная строка имени также размещается в свободной памяти. Функция strlen() указывает, сколько памяти нужно для строки, операция new отводит нужную память, а функция strcpy() копирует в нее строку. Все строковые функции описаны в <string.h>:

extern int strlen(const char*);

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

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

3.1.4 Обработка ошибок

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

int no of errors;

double error(const char* s)

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

no of errors++;

return 1;

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