Глава 3 Выражения и Операторы

С другой стороны, мы не можем игнорировать эффективность

- Джон Бентли

С++ имеет небольшой, но гибкий набор различных видов операторов для контроля потока управления в программе и бога­тый набор операций для манипуляции данными. С наиболее общеп­ринятыми средствами вас познакомит один законченный пример. После него приводится резюмирующий обзор выражений и с до­вольно подробно описываются явное описание типа и работа со свободной памятью. Потом представлена краткая сводка опера­ций, а в конце обсуждаются стиль выравнивания* и комментарии.

--------------------

* Нам неизвестен русскоязычный термин, эквивалентный ан­глийскому indentation. Иногда это называется отступами. (прим. перев.)

3.1 Настольный калькулятор

С операторами и выражениями вас познакомит приведенная здесь программа настольного калькулятора, предоставляющего четыре стандартные арифметические операции над числами с пла­вающей точкой. Пользователь может также определять перемен­ные. Например, если вводится

r=2.5

area=pi*r*r

(pi определено заранее), то программа калькулятора напишет:

2.5

19.635

где 2.5 - результат первой введенной строки, а 19.635 - результат второй.

Калькулятор состоит из четырех основных частей: програм­мы синтаксического разбора (parser'а), функции ввода, таблицы имен и управляющей программы (драйвера). Фактически, это ми­ниатюрный компилятор, в котором программа синтаксического разбора производит синтаксический анализ, функция ввода осу­ществляет ввод и лексический анализ, в таблице имен хранится долговременная информация, а драйвер распоряжается инициали­зацией, выводом и обработкой ошибок. Можно было бы многое до­бавить в этот калькулятор, чтобы сделать его более полезным, но в существующем виде эта программа и так достаточно длинна (200 строк), и большая часть дополнительных возможностей просто увеличит текст программы не давая дополнительного по­нимания применения С++.

3.1.1 Программа синтаксического разбора

Вот грамматика языка, допускаемого калькулятором:

program:

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

expr_list END

expr_list:

expression PRINT // PRINT - это или '\n' или ';'

expression PRINT expr_list

expression:

expression + term

expression - term

term

term:

term / primary

term * primary

primary

primary:

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

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

NAME = expression

- primary

( expression )

Другими словами, программа есть последовательность

строк. Каждая строка состоит из одного или более выражений,

разделенных запятой. Основными элементами выражения являются

числа, имена и операции *, /, +, - (унарный и бинарный) и =.

Имена не обязательно должны описываться до использования.

Используемый метод обычно называется рекурсивным спуском это популярный и простой нисходящий метод. В таком языке, как С++, в котором вызовы функций относительно дешевы, этот метод к тому же и эффективен. Для каждого правила вывода грамматики имеется функция, вызывающая другие функции. Терминальные сим­волы (например, 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, как указано грамматикой.

Странная запись for(;;) - это стандартный способ задать бесконечный цикл. Можно произносить это как "навсегда"*. Это вырожденная форма оператора for, альтернатива - while(1). Вы­полнение оператора switch повторяется до тех пор, пока не бу­дет найдено ни + ни -, и тогда выполняется оператор return в случае default.

--------------------

* игра слов: "for" - "forever" (навсегда). (прим. перев.)

Операции +=, -= используются для осуществления сложения и вычитания. Можно было бы не изменяя смысла программы ис­пользовать left=left+term() и left=left-term(). Однако left+= term() и left-=term() не только короче, но к тому же явно вы­ражают подразумеваемое действие. Для бинарной операции @ вы­ражение x@=y означает x=x@y за исключением того, что x вычис­ляется только один раз. Это применимо к бинарным операциям

+ - * / % & ! ^ << >>

поэтому возможны следующие операции присваивания:

+= -= *= /= %= &= != ^= <<= >>=

Каждая является отдельной лексемой, поэтому a+ =1 является синтаксической ошибкой из-за пробела между + и =. (% является операцией взятия по модулю; &,! и ^ являются побито­выми операциями И, ИЛИ и исключающее ИЛИ; << и >> являются операциями левого и правого сдвига). Функции term() и get_token() должны быть описаны до expr().

Как организовать программу в виде набора файлов, обсуж­дается в Главе 4. За одним исключением все описания в данной программе настольного калькулятора можно упорядочить так, чтобы все описывалось ровно один раз и до использования. Иск­лючением является expr(), которая обращается к term(), кото­рая обращается к prim(), которая в свою очередь обращается к expr(). Этот круг надо как-то разорвать;

Описание

double expr(); // без этого нельзя

перед prim() прекрасно справляется с этим.

Функция term() аналогичным образом обрабатывает умноже­ние и сложение:

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(char*) будет описана позже. Переменная d вво­дится в программе там, где она нужна, и сразу же инициализи­руется. Во многих языках описание может располагаться только в голове блока. Это ограничение может приводить к довольно скверному искажению стиля программирования и/или излишним ошибкам. Чаще всего неинициализированные локальные переменные являются просто признаком плохого стиля; исключением являются переменные, подлежащие инициализации посредством ввода, и пе­ременные векторного или структурного типа, которые нельзя удобно инициализировать одними присваиваниями*. Заметьте, что = является операцией присваивания, а == операцией сравнения.

--------------------

* В языке немного лучше этого с этими исключениями тоже надо

бы справляться. (прим. автора)

Функция prim, обрабатывающая primary, написана в основ­ном в том же духе, не считая того, что немного реальной рабо­ты в ней все-таки выполняется, и нет нужды в цикле, поскольку мы попадаем на более низкий уровень иерархии вызовов:

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

(*

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("должно быть primary");

*)

*)

При обнаружении NUMBER (то есть, константы с плавающей точкой), возвращается его значение. Функция ввода get_token() помещает значение в глобальную переменную number_value. Ис­пользование в программе глобальных переменных часто указывает на то, что структура не совсем прозрачна, что применялась не­которого рода оптимизация. Здесь дело обстоит именно так. Те­оретически лексический символ обычно состоит из двух частей: значения, определяющего вид лексемы (в данной программе token _value), и (если необходимо) значения лексемы. У нас имеется только одна простая переменная curr_tok, поэтому для хранения значения последнего считанного NUMBER понадобилась глобальная переменная переменная number_value. Это работает только пото­му, что калькулятор при вычислениях использует только одно число перед чтением со входа другого.

Так же, как значение последнего встреченного NUMBER хра­нится в number_value, в name_string в виде символьной строки хранится представление последнего прочитанного NAME. Перед тем, как что-либо сделать с именем, калькулятор должен загля­нуть вперед, чтобы посмотреть, осуществляется ли присваивание ему, или оно просто используется. В обоих случаях надо спра­виться в таблице имен. Сама таблица описывается в #3.1.3; здесь надо знать только, что она состоит из элементов вида:

srtuct name (*

char* string;

char* next;

double value;

*)

где next используется только функциями, которые поддерживают

работу с таблицей:

name* look(char*);

name* insert(char*);

Обе возвращают указатель на name, соответствующее пара­метру - символьной строке; look() выражает недовольство, если имя не было определено. Это значит, что в калькуляторе можно использовать имя без предварительного описания, но первый раз оно должно использоваться в левой части присваивания.