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

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

В данной статье в качестве примера мы возьмём разбор и вычисление арифметических выражений. Переходя от простых примеров к сложным, мы построим полноценный калькулятор, способный рассчитать заданное арифметическое выражение с учётом приоритетов операций, с использованием функций и переменных, с возможностью изменения приоритета с помощью скобок. Все примеры даются на языке 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.

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

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

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

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