Введение в теорию синтаксического анализа
 

Введение в теорию синтаксического анализа

Данная статья является введением в теорию синтаксического анализа выражений. Под выражением здесь подразумевается любая последовательность символов. Синтаксический анализ - это выяснение, соответствует ли заданное выражение некоторым заранее заданным синтаксическим правилам. Например, синтаксический анализ выражения (т.е. программы) осуществляет компилятор. Если программа не соответствует синтаксису языка, компилятор выдаёт ошибку.

В данной статье в качестве примера мы возьмём разбор и вычисление арифметических выражений. Переходя от простых примеров к сложным, мы построим полноценный калькулятор, способный рассчитать заданное арифметическое выражение с учётом приоритетов операций, с использованием функций и переменных, с возможностью изменения приоритета с помощью скобок. Все примеры даются на языке Delphi и сопровождаются экскурсами в теорию, объясняющими, как эти примеры работают.

Синтаксис и семантика

Прежде чем двигаться дальше, введём базовые определения. Языком мы будем называть множество строк (в большинстве случаев это будет бесконечное множество). Каждое выражение (в некоторых источниках вместо "выражение" используются термины "предложение" или "утверждение") может принадлежать или не принадлежать языку. Например, определим язык так: любая строка произвольной длины, состоящая из нулей и единиц. Тогда выражения "000101001" и "1111" принадлежат языку, а выражения "5x" и "R@8" - нет.

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

С практической точки зрения наиболее интересны те языки, выражения которых не только подчиняются каким-либо синтаксическим правилам, но и несут смысловую нагрузку. Например, выражения языка Delphi - программы - приводят к выполнению компьютером тех или иных действий. В данном случае семантика языка Delphi - это правила, определяющие, к выполнению каких именно действий приведёт то или иное выражение. В более общем смысле семантика языка - это описание смысла языковых выражений.

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

Чтобы подчеркнуть разницу между синтаксисом и семантикой, рассмотрим такой оператор присваивания в Delphi: "X:=Y+Z;". С точки зрения синтаксиса это правильное выражение, т.к. требования синтаксиса заключаются в том, чтобы слева от знака присваивания стоял корректный идентификатор, справа - корректное выражение. Очевидно, что эти правила выполнены. Но с точки зрения семантики это выражение может быть ошибочным, если, например, один из встречающихся в нём идентификаторов не объявлен, или их типы не совместимы, или же идентификатор "X" объявлен как константа. Таким образом, синтаксически верное выражение не всегда является семантически верным. Примером верного синтаксически, но не семантически, арифметического выражения может служить "0/0" - два корректных числа, между которыми стоит допустимый знак операции, т.е. синтаксически всё верно. Однако смысла такое выражение не имеет, т.к. данная операция неприменима к данным операндам.

Таким образом, синтаксический анализ арифметических выражений - это всего лишь выяснение, корректно ли выражение. Мы же выше говорили о вычислении выражений, а это уже имеет отношение к семантике, т.е., строго говоря, мы здесь будем заниматься не только синтаксическим, но и семантическим анализом. С точки зрения теории синтаксический и семантический анализ разделены, т.е. анализировать семантику можно начинать "с нуля" после того, как анализ синтаксиса закончен. Но на практике легче объединить эти два процесса в один, чтобы пользоваться результатами синтаксического разбора при семантическом анализе. Из-за этого, как мы увидим в дальнейшем, иногда приходится вводить сложные синтаксические правила, которые в итоге описывают тот же язык, что и более простые, чтобы упростить семантический анализ.

На примере выражения "X:=Y+Z;" мы могли наблюдать интересную особенность: для заключения о синтаксической корректности или некорректности отдельной части выражения языка нам достаточно видеть только эту часть, в то время как для выяснения её семантической корректности необходимо знать "предысторию", т.е. то, что было в выражении раньше. Это объясняется следующим образом: существуют формальные способы описания синтаксиса, позволяющие выделить отдельные синтаксические конструкции. В принципе, язык может использовать другие синтаксические правила, не позволяющие однозначно выделить отдельные конструкции (примером такого языка является FORTRAN, особенно его ранние версии), но на практике такой синтаксис неудобен, поэтому при разработке языков конструкции стараются всё-таки выделять. Это облегчает как чтение программы, так и создание трансляторов языка.

Что касается семантики, то формальные правила её описания отсутствуют. Поэтому семантика описывается словами, или же язык использует интуитивно понятную семантику. Например, арифметическое выражение "2+2" выглядит очень понятно в силу того, что мы к нему привыкли, хотя с точки зрения математики объяснить, что такое число и что такое операция сложения двух чисел, не так-то просто.

Кроме синтаксического и семантического анализа существует ещё и лексический анализ. Лексемами называются последовательности символов языка, которые имеют смысл только как единое целое. Например, выражение "2+3" не является лексемой, т.к. его части - "2", "3" и "+" - имеют смысл и вне выражения, а смысл всего выражения является суперпозицией смыслов этих частей. А вот идентификатор "TForm" является лексемой, т.к. его невозможно разделить на имеющие смысл части. Таким образом, лексема - это синтаксическая единица самого нижнего уровня. Описание лексических правил может быть обособлено от синтаксических, и тогда сначала лексический анализатор выделяет из выражения все лексемы, а потом синтаксический анализатор проверяет правильность выражения, составленного из этих лексем. Попутно лексический анализатор может удалять из выражения комментарии, лишние разделители и т.п.

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

Формальное описание синтаксиса

Существует несколько различных (но, тем не менее, эквивалентных) способов описания синтаксиса. Мы здесь познакомимся только с самой употребляемой из них - расширенной формой Бэкуса-Наура. Эта форма была предложена Джоном Бэкусом и немного модифицирована Питером Науром, который использовал её для описания синтаксиса языка Алгол. (Примечательно, что практически идентичная форма была независимо изобретена Ноамом Хомски для описания синтаксиса естественных языков.) В русскоязычной литературе форму Бэкуса-Наура обычно обозначают аббревиатурой БНФ (Бэкуса-Наура Форма). Несколько неестественный для русского языка порядок слов используется, чтобы сохранилось сходство с английской аббревиатурой BNF (Backus-Naur Form). Со временем в БНФ были добавлены новые правила описания синтаксиса, и эта форма получила название РБНФ - расширенная БНФ (далее для краткости мы не будем делать различия между БНФ и РБНФ). Совокупность правил, записанных в виде БНФ (или другим способом), называется грамматикой языка.

Основными понятиями БНФ являются терминальные и нетерминальные символы. Терминальные символы - это отдельные символы или их последовательности, являющиеся с точки зрения синтаксиса неразрывным целым. Другими словами, терминальные символы - это лексемы. Терминальные символы могут состоять из одного или нескольких символов в обычном понимании этого слова. Примером терминальных символов, состоящих из нескольких символов, могут служить зарезервированные слова языка Паскаль и символы операций ">=", "<=" и "<>". Чтобы отличать терминальные символы от служебных символов БНФ, мы будем заключать их в одинарные кавычки.

Нетерминальный символ - это некоторая абстракция, которая по определённым правилам сводится к комбинации терминальных и/или других нетерминальных символов. Правила должны быть такими, чтобы существовала возможность выведения из них выражения, полностью состоящего из терминальных символов, за конечное число шагов, хотя рекурсивные определения терминальных символов друг через друга или через самих себя допускаются. Нетерминальные символы имеют имена, которые обычно обрамляются угловыми скобками, например: <operator>.

Операция "::=" означает определение нетерминального символа. Слева от этого знака ставится нетерминальный символ, смысл которого надо определить, справа - комбинация символов, которой соответствует данный нетерминальный символ. Примером использования операции может служить следующее определение:

В данном примере мы определили нетерминальный символ , который можем использовать в дальнейшем, например, при описании синтаксиса записи вещественного числа. Если мы затем захотим поменять разделитель с точки на запятую, нам достаточно будет переопределить смысл символа <Separator>, а не менять определения всех остальных символов, где встречается этот разделитель.

В более сложных случаях нетерминальному символу ставится в соответствие не один символ, а их цепочка, в которую могут входить как терминальные, так и нетерминальные символы. Примером такого определения может служить описание синтаксиса оператора присваивания в Delphi:

При записи синтаксиса в БНФ часто сначала дают определение абстракции самого верхнего уровня, описывающей всё выражение в целом, и только потом - определения абстракций нижнего уровня, которые используются при её определении, т.е. порядок определения абстракций может отличаться от принятого в языках программирования определения идентификаторов, согласно которому идентификатор должен быть сначала описан, и лишь затем использован. В частности, в данном примере символы <var> (переменная) и <Expression> (выражение) могут быть определены после определения <Assignment>.

Операция "|" в БНФ означает "или" - показывает одну из двух альтернатив. Например, если под нетерминальным символом <Sign> может подразумевать знак "+" или "-", его определение будет выглядеть следующим образом:

Если альтернатив больше, чем две, они записываются в ряд, разделённые символом "|", например:

Здесь мы определили нетерминальный символ <digit> (цифра), под которым можем понимать один из символов диапазона '0'..'9'.

При использовании операции "|" подразумевается, что всё, что стоит слева от этого знака, является альтернативой того, что стоит справа (до конца определения или до следующего символа "|"). Если в качестве альтернативы выступает только часть определения, используются круглые скобки, чтобы обособить эту часть, например:

Здесь с помощью БНФ описан синтаксис оператора for, используемого в Delphi.

В квадратные скобки заключается необязательная часть определения, т.е. такая, что синтаксис допускает как присутствие, так и отсутствие этой части, например:

Здесь дано определение условного оператора if, используемого в Delphi. Квадратные скобки указывают на необязательность части else.

Строго говоря, определения операторов if и for в Delphi сложнее, чем те, которые мы здесь привели. Это связано с тем, что <if> и <for> - это варианты <operator>. Поэтому может возникнуть конструкция типа if Condition1 then if Condition2 then Operator1 else Operator2. Из нашего определения невозможно сделать вывод о том, к какому из двух if в данном случае относится else. В языках программирования принято, что else относится к последнему из if, который ещё не имеет else. Чтобы описать это правило, требуется более сложный синтаксис, чем мы здесь привели. Однако этот вопрос выходит за рамки данной статьи. Более подробно он рассмотрен в [1].

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

Это простое определение не совсем верно, т.к. фигурные скобки указывают на повторение ноль или большее число раз, т.е. пустая строка также будет соответствовать нашему определению <Unsigned>. Чтобы это не происходило, исправим наше определение:

Теперь синтаксическое правило, определяемое символом <Unsigned>, требует, чтобы выражение состояло из одной или более цифр. В некоторых случаях после закрывающей фигурной скобки ставят символ "+" в верхнем индексе, чтобы показать, что содержимое скобок должно повторяться не менее одного раза. Например, следующее определение <Unsigned> эквивалентно предыдущему:

Однако это обозначение не является общепризнанным, поэтому мы не будем им пользоваться. Этим исчерпывается набор правил БНФ. Ниже мы будем использовать эти правила для описания различных синтаксических конструкций. При этом мы увидим, что, несмотря на простоту, БНФ позволяет описывать очень сложные конструкции, и это описание просто для понимания.

Синтаксис вещественного числа

Попытаемся использовать БНФ для описания синтаксиса вещественного числа. Сначала опишем этот синтаксис словами: "Перед числом может стоять знак - плюс или минус. Затем идёт одна или несколько цифр. Потом может идти точка, после которой будет ещё одна или несколько цифр. Затем может идти показатель степени E (большое или малое), после которого может стоять знак плюс или минус, а затем должна быть одна или несколько цифр". Указанные правила описывают синтаксис записи вещественных чисел, использующийся в Delphi. Согласно им, правильными вещественными числами считаются, например, выражения "10", "0.1", "+4", "-3.2", "8.26e-5" и т.п. Такие выражения как, например, ".6" и "-.5" этим правилам не удовлетворяют, т.к. перед десятичной точкой должна стоять хотя бы одна цифра. В некоторых языках программирования такая запись допускается, но Delphi требует обязательного наличия целой части.
Теперь переведём описанные выше правила на язык БНФ.

Теперь на основе этих правил напишем функцию IsNumber, которая в качестве параметра принимает строку и возвращает True, если эта строка удовлетворяет правилам записи числа, и False, если не удовлетворяет.

Для каждого нетерминального символа мы ввели отдельную функцию, разбор начинается с символа самого верхнего уровня - <Number> - и следует правилам, записанным для этого символа. Такой способ синтаксического анализа называется левосторонним рекурсивным нисходящим анализом. Левосторонним потому, что символы в выражении перебираются слева направо, нисходящим - потому, что сначала анализируются символы верхнего уровня, а потом - символы нижнего. Рекурсивность метода на данном примере не видна, т.к. наша грамматика не содержит рекурсивных определений, но мы с этим столкнёмся в последующих примерах.

Пример использования функции IsNumber содержится в прилагаемом архиве, в каталоге IsNumberSample.

В заключение рассмотрим альтернативный способ записи грамматики вещественного числа - графический (такой способ называется синтаксическим графом, или рельсовой диаграммой). Это направленный граф (он показан на рисунке), узлами которого являются терминальные (с круглыми углами) и нетерминальные (с прямыми углами) символы. Двигаться от одного узла к другому можно только по линиям в направлениях, указанных стрелками. В таком графе достаточно легко разобраться, а по возможностям описания синтаксиса он эквивалентен БНФ.

http://www.delphikingdom.com/images/synt.gif

Простой калькулятор

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

Таким образом, наш калькулятор будет распознавать и вычислять цепочки чисел, между которыми стоят знаки операции, которые над этими числами выполняются. В вырожденном случае выражение может состоять из одного числа и, соответственно, не содержать ни одного знака операции. Опишем эти правила с помощью БНФ, используя ранее определённый символ <Number>.

Для написания калькулятора нам понадобятся две новых функции - IsOperator, которая проверяет, является ли следующий символ оператором, и Expr, которая получает на входе строку, анализирует её в соответствии с указанными правилам и вычисляет результат. Кроме того, функция IsNumber сама по себе нам тоже больше не нужна - мы создадим на её основе функцию Number, которая получает на входе строку и номер позиции, начиная с которой в этой строке должно быть расположено число, проверяет, так ли это, и возвращает это число. Кроме того, функция Number должна перемещать указатель на следующий после числа символ строки, чтобы функция Expr, вызвавшая Number, могла узнать, с какого символа продолжать анализ. Если последовательность символов не является корректным числом, функция Number возбуждает исключение ESyntaxError, определённое специально для указания на ошибку в записи выражения.

Сама по себе задача преобразования строки в вещественное число достаточно сложна, и чтобы не отвлекаться на её решение, мы будем использовать функцию StrToFloat из модуля SysUtils. Когда функция Number выделит из строки последовательность символов, являющуюся числом, эта последовательность передаётся функции StrToFloat, и преобразованием занимается она. Здесь надо учесть два момента. Во-первых, в нашей грамматике разделителем целой и дробной части является точка, а StrToFloat использует системные настройки, т.е. разделителем может быть и запятая. Чтобы обойти эту проблему, слегка изменим синтаксис и будем сравнивать аргумент функции IsSeparator не с символом ".", а с DecimalSeparator (таким образом, наш калькулятор тоже станет чувствителен к системным настройкам). Во-вторых, не всякое выражение, соответствующее нашей грамматике, будет допустимым числом с точки зрения StrToFloat, т.к. эта функция учитывает диапазон типа Extended. Например, синтаксически верное выражение "2e5000" даст исключение EConvertError, т.к. это число выходит за пределы этого диапазона. Но пока мы остаёмся в рамках типа Extended, мы вынуждены мириться с этим.
Новые функции выглядят следующим образом:

Код приведён практически без комментариев, т.к. он очень простой, и все моменты, заслуживающие упоминания, мы уже разобрали в тексте. В прилагаемом архиве находится программа SimpleCalcSample, которая демонстрирует работу нашего калькулятора. Калькулятор выполняет действия над числами слева направо, без учёта приоритета операций, т.е. вычисление выражения "2+2*2" даст 8.

Грамматика выражения является простой для разбора, т.к. разбор выражения идёт слева направо, и для соотнесения очередной части строки с тем или иным нетерминальным символом на любом этапе анализа достаточно знать только следующий символ. Такие грамматики называются LR(1)-грамматиками (в более общем случае требуется не один символ, а одна лексема). Класс этих грамматик исследован Кнутом.

Грамматика Паскаля не относится к классу LR(1)-грамматик из-за уже упоминавшейся проблемы отнесения else к тому или иному if. Чтобы решить эту проблему, приходится вводить два нетерминальных символа - завершённой формы оператора if (с else) и незавершённой (без else). Таким образом, встретив в тексте программы лексему "if", синтаксический анализатор не может сразу отнести её к одному из этих символов, пока не продвинется вперёд и не натолкнётся на наличие или отсутствие else. А так как оператор if может быть оператором в циклах for, while или в операторе with, для них также приходится вводить завершённую и незавершённую форму. Именно из-за этой проблемы Вирт (разработчик Паскаля) в своих более поздних языках отказался от идеи составного оператора и модифицировал синтаксис таким образом, чтобы проблема else не возникала.

Другим достоинством нашей простой грамматики является её однозначность. Любая синтаксически верная строка не допускает неоднозначной трактовки. Неоднозначность могла бы возникнуть, например, если бы какая-то операция обозначалась символом ".". Тогда было бы непонятно, должно ли выражение "1.5" трактоваться как число "одна целая пять десятых" или как выполнение операции над числами 1 и 5. Этот пример выглядит несколько надуманным, но неоднозначные грамматики, тем не менее, иногда встречаются на практике. Например, если запятая служит для отделения дробной части числа от целой и для разделения значений в списке параметров функций, то выражение "f(1,5)" может, с одной стороны, трактоваться как вызов функции f с одним аргументом 1.5, а с другой - как вызов её с двумя аргументами 1 и 5. Правила решения неоднозначных ситуаций не описываются в виде БНФ, их приходится объяснять "на словах", что затрудняет разбор соответствующих выражений. Другой пример неоднозначной грамматики - грамматика языков C/C++. В них оператор инкремента, записывающийся как "++", имеет две формы записи - префиксную (перед увеличиваемой переменной) и постфиксную (после переменной). Кроме того, этот оператор возвращает значение, поэтому его можно использовать в выражениях. Синтаксически допустимо, например, выражение "a+++b", но грамматика не даёт ответа, следует ли это трактовать как "(a++)+b" или как "a+(++b)". Кроме того, т.к. существует операция "унарный плюс", возможно и третье толкование - "a+(+(+b))".

Учёт приоритета операторов

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

Для примера рассмотрим выражение "2*4+3*8/6". Наш синтаксис должен как-то отразить то, что аргументами операции сложения в данном случае являются не числа 4 и 5, а "2*4" и "3*8/6". В общем случае это означает, что выражение - это последовательность из одного или нескольких слагаемых, между которыми стоят знаки "+" или "-". А слагаемые - это, в свою очередь, последовательности из одного или нескольких чисел, разделённых знаками "*" и "/". А теперь запишем то же самое на языке БНФ:

Определение символа <Operator1> совпадает с определением введённого ранее символа <Sign>. Но использовать <Sign> в определении <Expr> было бы неправильно, т.к., в принципе, в выражении могут существовать и другие операции, имеющие тот же приоритет (как, например, операции арифметического или и арифметического исключающего или в Delphi), и тогда определение <Operator1> будет расширено. Но это не должно затронуть определение символа <Number>, в которое входит <Sign>.

Чтобы приспособить калькулятор к новым правилам, нужно заменить функцию Operator на Operator1 и Operator2, добавить функцию Term и внести изменения в Expr. Функция Number остаётся без изменения. Обновлённая часть калькулятора выглядит следующим образом.

Если вы разобрались с предыдущими примерами, приведённый здесь код будет вам понятен. Некоторых комментариев требует только функция Term. Она выделяет, начиная с заданного символа, ту часть строки, которая соответствует определению <Term>. Вызвавшая её функция Expr должна продолжить разбор выражения со следующего за этой подстрокой символа, поэтому функция Term, как и Number, имеет параметр-переменную P, которая на входе содержит номер первого символа слагаемого, а на выходе - номер первого после этого слагаемого символа.

Пример калькулятора, учитывающего приоритет операций, содержится в архиве под именем PrecedenceCalcSample. Поэкспериментировав с ним, легко убедиться, что теперь вычисление "2+2*2" даёт правильное значение 6.

В заключение заметим, что язык, определяемый такой грамматикой, полностью совпадает с языком, определяемым грамматикой из предыдущего примера, т.е. любое выражение, принадлежащее первому языку, принадлежит и второму и наоборот. Усложнение синтаксиса, которое мы здесь ввели, требуется именно для отражения семантики выражений языка, а не для расширения самого языка.

Выражения со скобками

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

Выражение, заключённое в скобки, допустимо использовать везде, где допустимо использование отдельного числа (из этого, в частности, следует, что допускаются вложенные скобки). Таким образом, мы должны расширить нашу грамматику так, чтобы аргументом операций сложения и умножения могли служить не только числа, но и выражения, заключённые в скобки. Это автоматически позволит использовать такие выражения и в качестве слагаемых, потому что слагаемое - это последовательность из одного или нескольких множителей, разделённых знаками умножения и деления.
На языке БНФ всё вышесказанное выглядит так:

В этих определениях появилась рекурсия, т.к. в определении <Expr> используется (через <Term>) символ <Factor>, а в определении <Factor> - <Expr>. Соответственно, при реализации такой грамматики будут использоваться рекурсивные функции.

Наша грамматика не учитывает, что перед скобками может стоять знак унарной операции "+" или "-", хотя общепринятые правила записи выражений вполне допускают выражения типа "3*-(2+4)". Поэтому, прежде чем приступить к реализации нового калькулятора, введём правила, допускающие такой синтаксис. Можно было бы модифицировать определение <Factor> таким образом:

Однако такой подход страдает отсутствием общности. В дальнейшем мы усложним наш синтаксис, введя другие типы множителей - функции, переменные. Перед каждым из них, в принципе, может стоять знак унарной операции, поэтому логичнее определить синтаксис таким образом, чтобы унарная операция допускалась вообще перед любым множителем. В этом случае можно будет слегка упростить определение <Number>, т.к. знак "+" или "-" в начале числа можно будет трактовать не как часть числа, а как унарный оператор, стоящий перед множителем, представленным в виде числовой константы.
С учётом этого новая грамматика запишется следующим образом:

Здесь опущены определения некоторых вспомогательных символов, которые не изменились.

Мы видим, что грамматика стала "более рекурсивной", т.е. в определении символа <Factor> используется он сам. Соответственно, функция Factor будет вызывать саму себя.

Символ <UnaryOp>, определение которого совпадает с определениями <Operator1> и <Sign>, мы делаем независимым нетерминальным символом по тем же причинам, что и ранее: в принципе, синтаксис может допускать унарные операции (как, например, not в Delphi), которые не являются ни знаками, ни допустимыми бинарными операциями.

Побочным эффектом нашей грамматики стало то, что, например, "-5" воспринимается как множитель, а потому перед ним допустимо поставить унарный оператор, т.е. выражение "--5" также является корректным множителем и трактуется как "-(-5)". А перед "--5", в свою очередь, можно поставить ещё один унарный оператор. И так - до бесконечности. Это может показаться не совсем правильным, но, тем не менее, такая грамматика широко используется. Легко, например, убедиться, что компилятор Delphi считает допустимым выражение "2+-+-2", трактуя его как "2+(-(+(-2)))".
Нижеследующий код иллюстрирует реализацию данной грамматики.

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

Функция Expr теперь может применяться не только к выражению в целом, но и к отдельной подстроке. Поэтому она, как и все остальные функции, теперь имеет параметр-переменную P, через который передаётся начало и конец этой подстроки. Из функции убрана проверка того, что в результате её использования строка проанализирована полностью, т.к теперь допустим анализ части строки.

Функция Expr в своём новом виде стала не очень удобна для конечного пользователя, поэтому была описана ещё одна функция - Calculate. Это вспомогательная функция, которая избавляет пользователя от вникания в детали "внутренней кухни" калькулятора, т.е. использования переменной P и проверки того, что строка проанализирована до конца.

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

Полноценный калькулятор

Последняя версия нашего калькулятора может считать сложные выражения, но для практического использования этого мало. В этом разделе мы научим наш калькулятор использовать функции и переменные. Также будет введена операция возведения в степень, обозначающаяся значком "^".

Имена переменных и функций - это идентификаторы. Идентификатор определяется по общепринятым правилам: он должен начинаться с буквы латинского алфавита или символа "_", следующие символы должны быть буквами, цифрами или "_". Таким образом, грамматика идентификатора выглядит так:

Следствием этой грамматики является то, что отдельно взятый символ "_" является корректным идентификатором. И хотя это может на первый взгляд показаться абсурдным, тем не менее, именно таковы общепринятые правила. Легко убедиться, что, например, Delphi допускает объявление переменных с именем "_".

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

Из приведённых определений видно, что грамматика, использующая их, не относится к классу LR(1)-грамматик, т.к. обнаружив в выражении идентификатор, анализатор не может сразу решить, является ли этот идентификатор переменной или именем функции, это выяснится только при проверки следующего символа - скобка это или нет. Тем не менее, реализация такой грамматики достаточно проста, и это не будет доставлять нам существенных неудобств.

Переменные и функции, так же, как и выражения, заключённые в скобки, выступают в роли множителей. Соответственно, их появление в грамматике учитывается расширением смысла символа <Factor>.

Теперь рассмотрим свойства оператора возведения в степень. Во-первых, его приоритет выше, чем у операций сложения и деления, т.е. выражение "a*b^c" трактуется как "a*(b^c)", а "a^b*c" - как "(a^b)*c". Во-вторых, он правоассоциативен, т.е. "a^b^c" означает "a^(b^c)", а не "(a^b)^c". В-третьих, его приоритет выше, чем приоритет унарных операций, т.е. "-a^b" означает "-(a^b)", а не "(-a)^b". Тем не менее, "a^-b" означает "a^(-b)".

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

Правая ассоциативность также заложена в этих определениях. Рассмотрим, как будет разбираться выражение "a^b^c". Сначала функция Factor (через вызов функции Base) выделит и вычислит множитель "a", а потом вызовет саму себя для вычисления остатка "b^c". Таким образом, а будет возведено в степень b^c, как это и требуют правила правой ассоциативности.

Вообще, вопросы правой и левой ассоциативности операторов, которые мы здесь опустили, оказывают влияние на то, как определяется грамматика языка. Более подробно об этом написано в [1].

Так как определения символов <Expr> и <Term> в нашей новой грамматике не изменились, не изменятся и соответствующие функции. Для реализации нового синтаксиса нам потребуется изменить функцию Factor и ввести новые функции Base, Identifier и Func (будем использовать такое сокращение, т.к. function в Delphi является зарезервированным словом). Идентификаторы будем полагать нечувствительными к регистру символов.

Для простоты обойдёмся тремя функциями: sin, cos и ln. Увеличение количества функций, допустимых в выражении - простая техническая задача, не представляющая особого интереса.

Если у нас появились переменные, то мы должны как-то хранить их значения, чтобы при вычислении выражения использовать их. В нашем примере мы будем хранить их в TStrings, получая доступ через свойство Values. С точки зрения производительности этот способ - один из самых худших, поэтому при создании реального калькулятора лучше придумать что-нибудь другое. Мы здесь будем использовать этот способ исключительно из соображений наглядности.

Пример калькулятора называется FullCalcSample. Его интерфейс содержит новые элементы, с помощью которых пользователь может задавать значения переменных. В левой нижней части окна находится список переменных с их значениями (при запуске программы этот список пустой). Правее находятся поля ввода "Имя переменной" и "Значение переменной", а так же кнопка "Установить". В первое поле следует ввести имя переменной, во второе - её значение. При нажатии на кнопку "Установить" переменная будет внесена в список, а если переменная с таким именем уже есть в списке, то её значение будет обновлено. Все переменные, которые есть в списке, могут использоваться в выражении. Если требуемая переменная в списке не найдена, попытка вычислить выражение приводит к ошибке.
Заметим, что символ <Factor> можно было бы определить несколько иначе:

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

Калькулятор с лексическим анализатором

Прежде чем двигаться дальше, рассмотрим недостатки последней версии нашего калькулятора. Во-первых, бросается в глаза некоторое дублирование функций. Действительно, с одной стороны, выделением числа из подстроки занимается функция Number, но в функции Base также содержится проверка первого символа числа. Функция Identifier также частично дублируется функцией Base.

Второй недостаток - нельзя вставлять разделители, облегчающие чтение выражения. Например, строка "2 + 2" не является допустимым выражением - следует писать "2+2", без пробелов. Если же попытаться учесть возможность вставки пробелов, придётся в разные функции писать много однотипного рутинного кода, который существенно усложнит восприятие программы.

Третий недостаток - сложность введения новых операторов, которые обозначаются не одним символом, а несколькими, например: ">=", "and", "div". Если посмотреть функции Expr и Term, которые придётся в этом случае переделывать, видно, что переделка будет достаточно сложна.

Решить все эти проблемы позволяет лексический анализатор, который выделяет из строки все лексемы, пропуская пробелы и иные разделители, и определяет тип каждой лексемы, не заботясь о том, насколько уместно появление данной лексемы в данном месте выражения. А после лексического анализа начинает работать анализатор синтаксический, который будет иметь дело не с отдельными символами строки, а с целыми лексемами.
В качестве примера рассмотрим реализацию следующей грамматики.

Эта грамматика на первый взгляд может показаться существенно более сложной, чем всё, что мы реализовывали ранее, но это не так: просто здесь приведены определения всех без исключения символов. Определение символа <Number> несколько изменено, но это касается только формы его представления - синтаксис числа остался без изменения. То, что раньше называлось <Expr>, теперь называется <MathExpr>, а выражение <Expr> состоит из одного <MathExpr>, с которым, возможно, сравнивается другое <MathExpr>. Семантика <Expr> такова: если в выражении присутствует только обязательная часть, результатом будет число, которое получилось в результате вычисления <MathExpr>. Если же имеется необязательное сравнение с другим <MathExpr>, то результатом будет "True" или "False" в зависимости от результатов сравнения.

В новой грамматике также расширен набор операторов. Операторы or, xor, and и not являются арифметическими, т.е. применяются к числовым, а не к логическим выражениям. Все операторы, которые применимы только к целым числам (т.е. вышеперечисленные, а также div и mod), игнорируют дробную часть своих аргументов.
Лексический анализатор должен выделять из строки следующие лексемы:

• Все знаки операций, которые используются в определении символов <Comparison>, <Operator1>, <Operator2>, <UnaryOp>, а также символ "^".
• Открывающую и закрывающую скобки.
• Имена функций.
• Идентификаторы (т.е. переменные).
• Числовые константы.

Напомним, что лексический анализатор не должен определять допустимость появления лексемы в данном месте строки. Он просто сканирует строку, выделяет из неё последовательности символов, распознаваемые как отдельные лексемы, и сохраняет информацию о них в специальном списке, которым потом пользуется синтаксический анализатор. Так, например, встретив цифру, лексический анализатор выделяет числовую константу. Встретив букву, он выделяет последовательность буквенно-цифровых символов. Затем сравнивает эту последовательность с одним из зарезервированных слов ("and", "div" и т.п.) и распознаёт лексему соответственно как идентификатор (переменную) или как зарезервированное слово. При этом выяснение, объявлена ли такая переменная, также не входит в обязанности лексического анализатора - это потом сделает синтаксический анализатор.

Из нашей грамматики следует, что имена функций являются зарезервированными словами, т.е. объявить переменные с именами "sin", "cos" и "ln", в отличие от предыдущего примера, нельзя. Это само по себе не упрощает и не усложняет задачу (просто при использовании в качестве имён функций зарезервированных слов эти имена распознаёт лексический анализатор, а при использовании идентификаторов - синтаксический).

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

В зависимости от типа лексем разделители между ними могут быть обязательными или необязательными. Например, в выражении "2+3" разделители между лексемами "2", "+" и "5" не нужны, потому что они могут быть отделены друг от друга и без этого. А вот в выражении "6 div 3" разделитель между "div" и "3" необходим, потому что в противном случае эти лексемы будут восприняты как идентификатор "div3". А вот разделитель между "6" и "div" не обязателен, т.к. "6div" не является допустимым идентификатором, и анализатор сможет отделить эти лексемы друг от друга и без разделителя. Вообще, если подстрока, получающаяся в результате слияния двух лексем, может быть целиком интерпретирована как какая-либо другая лексема, разделитель между ними необходим, в противном случае - необязателен. Разделитель внутри отдельной лексемы не допускается (т.е. подстрока "a 1" будет интерпретироваться как последовательность лексем "a" и "1", а не как лексема "a1").

Чтобы продемонстрировать возможности лексического анализатора, добавим поддержку комментариев. Комментарий - это последовательность символов, начинающаяся с "{" и заканчивающаяся "}", которая может содержать внутри себя любые символы, кроме "}". Комментарий считается разделителем, он допустим в любом месте, где допустимо появление других разделителей, т.е. в начале и в конце строки и между лексемами.

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

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

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

Практически вся ставтья не про СИНТАКСИЧЕСКИЙ, а про ЛЕКСИЧЕСКИЙ анализ.

кусок мини-курсовой чтоли ? почитаемс на досуге

"Т. Пратт, М. Зелковиц "Языки программирования: разработка и реализация"" - офигенная книга.

Статья хорошая-написано простым языком. Но на написание чего-то серьезного с ней не уйдешь.

Для этого Dragon Book есть)