LexemeType - это поле, содержащая информацию о том, что это за лексема. Тип TLexemeType - это специально определённый перечислимый тип, содержащий значения типа ltPlus, ltNumber, ltLeftBracket и т.п., позволяющие судить о том, какая лексема встретилась анализатору. Поле Pos хранит номер позиции в строке, начиная с которой идёт данная лексема. Это поле нужно только для того, чтобы синтаксический анализатор мог точно указать место ошибки, если встретит недопустимую лексему.

Поле Lexeme хранит саму подстроку, распознанную как лексема. Оно используется только если тип лексемы ltIdentifier или ltNumber. Для остальных типов лексем достаточно информации из поля LexemType.

Лексический анализатор реализован в виде класса TLexicalAnalyzer. В конструкторе класса выполняется разбор строки и формирование списка лексем. Через этот же класс синтаксический анализатор получает доступ к лексемам: свойство Lexeme возвращает текущую лексему, метод Next позволяет перейти к следующей. Так как наша грамматика предусматривает разбор слева направо, таких примитивных возможностей навигации синтаксическому анализатору вполне хватает.

В конец списка лексем помещается специальная лексема типа ltEnd. В предыдущих примерах приходилось постоянно сравнивать указатель позиции P с длиной строки S, чтобы не допустить выход за пределы диапазона. Если бы не было лексемы ltEnd, точно так же пришлось бы проверять, не вышел ли указатель за пределы списка. Но лексема ltEnd не рассматривается как допустимая ни одной из функций синтаксического анализатора, поэтому, встретив её, каждая из них возвращает управление вызвавшей её функции, и заканчивается эта цепочка только на функции Expr. Таким образом, код получается более ясным и компактным.

Аналогичный алгоритм можно было бы использовать и в предыдущих версиях калькулятора: достаточно было добавить в конец строки символ, который в ней заведомо не должен был появляться (например, #1), и проверять в функции Expr или Calculate, что разбор выражения остановился именно на этом символе.

Лексический анализ выражения заключается в чередовании вызовов функций SkipWhiteSpace и ExtractLexeme. Первая из них пропускает всё, что может разделять две лексемы, вторая - распознаёт и помещает в список одну лексему.

Обратите внимание, как в лексическом анализаторе реализована функция Number. Рассмотрим выражение "1e*5". В калькуляторе без лексического анализатора функция Number, дойдя до символа "*", выдавала исключение, т.к. ожидала увидеть здесь знак "+", "-" или число. Но лексический анализатор не должен брать на себя такую ответственность - поиск синтаксических ошибок. Поэтому в данном случае он должен откатиться назад, выделить из строки лексему "1" и продолжить выделение лексем с символа "e". В результате список лексем будет выглядеть так: "1", "e", "*", "5". И уже синтаксический анализатор должен потом разобраться, допустима ли такая последовательность лексем или нет.

Отметим, что для нашей грамматики непринципиально, зафиксирует ли в таком выражении ошибку лексический или синтаксический анализатор. Но в общем случае может существовать грамматика, в которой такое выражение допустимо, поэтому лексический анализатор должен действовать именно так, т.е. выполнять откат, если попытка выделить число зашла на каком-то этапе в тупик. Функция Number вызывается из ExtractLexeme только в том случае, когда в начале лексемы встречается цифра, а с цифры может начинаться только лексема ltNumber. Таким образом, сам факт вызова функции Number говорит о том, что в строке гарантировано обнаружена подстрока (в крайнем случае, состоящая из одного символа), которая является числом.

Функции синтаксического анализатора очень похожи на аналогичные функции из предыдущих примеров, за исключением того, что работают не со строкой, а со списком лексем. Мы не будем останавливаться на них здесь.

Использование лексического анализатора может повысить скорость многократного вычисления одного выражения при разных значениях входящих в него переменных (например, при построении графика функции, введенной пользователем). Действительно, лексический анализ в этом случае достаточно выполнить один раз, а потом пользоваться готовым списком. Можно сделать такие операции ещё более эффективными, переложив вычисление числовых констант на лексический анализатор. Для этого в структуру TLexeme нужно добавить поле Number:Extended, и модифицировать метод Number таким образом, чтобы он сразу преобразовывал выделенную подстроку в число. Тогда дорогостоящий вызов функции StrToFloat будет перенесён из многократно повторяющейся функции Base в однократно выполняемый метод TLexicalAnalyzer.Number. Но самым радикальным средством повышения производительности является переделка синтаксического анализатора таким образом, чтобы он не вычислял выражение самостоятельно, а формировал ассемблерный код для его вычисления. Однако написание компилятора математических выражений выходит за рамки данной статьи.

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

• Расширить определение <Expr> таким образом, чтобы в нем можно было объединять несколько операций сравнения с помощью or, and, xor. При этом потребуется поддержка скобок, т.к. иначе анализатор во многих случаях не сможет отличить логические операторы с низким приоритетом от одноимённых арифметических.
• Изменить грамматику таким образом, чтобы имя функции стало идентификатором, а не зарезервированным словом.
• Ввести функцию Log(a,x), вычисляющую логарифм x по основанию a. Учесть, что если запятая используется для отделения дробной части числа от целой, её уже нельзя использовать для разделения аргументов функции.
• Сделать комментарии вложенными. Сейчас в последовательности символов "{a{b}c}" считается, что комментарий заканчивается перед символом "c", т.к. лексический анализатор игнорирует все открывающие круглые скобки в комментариях.
• Сделать так, чтобы комментарий считался закрытым только тогда, когда число закрывающих скобок сравняется с числом открывающих.
• Добавить поддержку шестнадцатеричных целых констант. Для их записи использовать, как и в Delphi, символ "$", после которого должна идти последовательность из одной или нескольких шестнадцатеричных цифр.
• Добавить возможность использования для изменения приоритета операций не только круглых, но и квадратных скобок. Рассмотреть два варианта: когда круглые и квадратные скобки полностью взаимозаменяемы (т.е., например, допустимо выражение "2*(2+2]") и когда закрывающая скобка должна быть такой же формы, как и открывающая.

Заключение

Конечно, синтаксический анализ - вещь сложная, и в такой короткой статье мы смогли рассмотреть только самые его основы. За рамками статьи остались атрибутивные грамматики, конечные автоматы, генераторы языков и многое другое. Этим сложным вещам посвящены другие работы. К сожалению, у нас сейчас сложно достать общетеоретические книги - спрос на них существенно меньше, чем на всякие "Delphi за 7 дней", печатают их редко. Из более-менее доступной литературы могу посоветовать книги [1, 2]. Хотя они посвящены несколько другим вопросам, из них можно узнать много интересного и о синтаксическом анализе. Особенно рекомендую [1]. Книга [2] содержит больше сведений, но написана более тяжёлым языком, а её авторы крайне предвзято относятся к Паскалю, ставя ему в вину его достоинства и упрекая в несуществующих недостатках. Тем не менее, эту книгу тоже стоит прочитать.

Список литературы

1. Роберт У. Себеста "Основные концепции языков программирования", 5-ое изд.: Пер. с англ. - М.: "Издательский дом "Вильямс", 2001. - 672 с.: ил.
2. Т. Пратт, М. Зелковиц "Языки программирования: разработка и реализация", 4-ое изд.: Пер. с англ. - СПб.: Питер, 2002. - 688 с.: ил.

(c) Антон Григорьев, дата публикации 09-09-1999