6.3.2. Лексемы
Теперь (каким-то образом) мы должны заранее узнать, содержит ли строка символ * (или /). Если да, то мы должны (каким-то образом) скорректировать порядок выполнения вычислений. К сожалению, пытаясь заглянуть вперед, мы сразу же наталкиваемся на многочисленные препятствия.
1. Выражение не обязательно занимает только одну строку. Рассмотрим пример.
1
+
2
Это выражение до сих пор вычислялось без проблем.
2. Как обнаружить символ * (или /) среди цифр и символов +, –, ( и ) в нескольких строках ввода?
3. Как запомнить, в каком месте стоит символ *?
4. Как вычислить выражение, которое не выполняется слева направо (как 1+2*3). Если бы мы были безоглядными оптимистами, то сначала решили бы задачи 1–3, отложив задачу 4 на более позднее время. Кроме того, нам понадобится помощь. Кто-то ведь должен знать, как считать такие вещи, как числа и операторы, из входного потока и сохранить их так, чтобы с ними было удобно работать. Общепринятый и самый полезный ответ на эти вопросы таков: разложите выражение на лексемы, т.е. сначала считайте символы, а затем объедините их в лексемы (tokens). В этом случае после ввода символов
45+11.5/7
программа должна создать список лексем
45
+
11.5
/
7
Лексема (token) — это последовательность символов, выражающих нечто, что мы считаем отдельной единицей, например число или оператор. Именно так компилятор языка С++ работает с исходным кодом программы. На самом деле разложение на лексемы часто в том или ином виде применяется при анализе текста. Анализируя примеры выражений на языке С++, можно выделить три вида лексем.
• Литералы с плавающей точкой, определенные в языке C++, например 3.14, 0.274e2 и 42.
• Операторы, например +, –, *, /, %.
• Скобки (, ).
Внешний вид литералов с плавающей точкой может создать проблемы: считать число 12 намного легче, чем 12.3е–3, но калькуляторы обычно выполняют вычисления над числами с плавающей точкой. Аналогично, следует ожидать, что скобки в программе, имитирующей вычисления калькулятора, окажутся весьма полезными.
Как представить такие лексемы в нашей программе? Можно попытаться найти начало (и конец) лексемы, но это может привести к путанице (особенно, если позволить выражениям занимать несколько строк). Кроме того, если хранить числа в виде строки символов, то позднее следует идентифицировать это число по его цифрам; например, если мы видим строку 42 и где-то храним символы 4 и 2, то позднее должны выяснить, что эта строка представляет число 42 (т.е. 4*10+2). Общепринятое решение этой задачи — хранить каждую лексему в виде пары (вид, значение).
Вид идентифицирует лексему как число, оператор или скобку. Для чисел (в нашем примере — только для чисел) в качестве значения используется само число.
Итак, как же выразить идею о паре (вид, значение) в программе? Для этого определим тип Token, представляющий лексемы. Почему? Вспомните, почему мы вообще используем типы: они хранят данные, которые нам нужны, и предоставляют возможность выполнять полезные операции над этими данными. Например, тип int позволяет хранить целые числа и выполнять операции сложения, вычитания, умножения и вычисления остатка, в то время как тип string позволяет хранить последовательности символов и выполнять конкатенацию и доступ к символу по индексу. В языке С++ и его стандартной библиотеке определено много типов, например char, int, double, string, vector и ostream, но не тип Token. На самом деле существует огромное количество типов — тысячи и сотни тысяч, — которые мы хотели бы иметь, но которых нет в языке и в стандартной библиотеке.
Среди наших любимых типов, которых нет в библиотеке, — классы Matrix (см. главу 24), Date (см. главу 9) и целые числа с бесконечной точностью (поищите в веб класс Bignum). Если вы еще раз поразмыслите над этим, то поймете, что язык не может поддерживать десятки тысяч типов: кто их определит, кто их реализует, как их найти и какое толстое руководство по использованию языка при этом получится? Как и большинство современных языков программирования, язык С++ решает эту проблему, позволяя программисту при необходимости определять свои собственные типы (типы, определенные пользователем).