Введение в теорию синтаксического анализа
Данная статья является введением в теорию синтаксического анализа выражений. Под выражением здесь подразумевается любая последовательность символов. Синтаксический анализ - это выяснение, соответствует ли заданное выражение некоторым заранее заданным синтаксическим правилам. Например, синтаксический анализ выражения (т.е. программы) осуществляет компилятор. Если программа не соответствует синтаксису языка, компилятор выдаёт ошибку.
В данной статье в качестве примера мы возьмём разбор и вычисление арифметических выражений. Переходя от простых примеров к сложным, мы построим полноценный калькулятор, способный рассчитать заданное арифметическое выражение с учётом приоритетов операций, с использованием функций и переменных, с возможностью изменения приоритета с помощью скобок. Все примеры даются на языке 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:
Код:
<Assignment> ::= <var> ':=' <Expression>
При записи синтаксиса в БНФ часто сначала дают определение абстракции самого верхнего уровня, описывающей всё выражение в целом, и только потом - определения абстракций нижнего уровня, которые используются при её определении, т.е. порядок определения абстракций может отличаться от принятого в языках программирования определения идентификаторов, согласно которому идентификатор должен быть сначала описан, и лишь затем использован. В частности, в данном примере символы <var> (переменная) и <Expression> (выражение) могут быть определены после определения <Assignment>.
Операция "|" в БНФ означает "или" - показывает одну из двух альтернатив. Например, если под нетерминальным символом <Sign> может подразумевать знак "+" или "-", его определение будет выглядеть следующим образом:
Код:
<Sign> ::= '+' | '-'
Если альтернатив больше, чем две, они записываются в ряд, разделённые символом "|", например:
Код:
<digit> ::= '0' | '1' | '2' | '3' | '4'| '5' | '6' | '7' | '8' | '9'
Здесь мы определили нетерминальный символ <digit> (цифра), под которым можем понимать один из символов диапазона '0'..'9'.
При использовании операции "|" подразумевается, что всё, что стоит слева от этого знака, является альтернативой того, что стоит справа (до конца определения или до следующего символа "|"). Если в качестве альтернативы выступает только часть определения, используются круглые скобки, чтобы обособить эту часть, например:
Код:
<for> ::= 'for' <var> ':=' <Expression> ('to' | 'downto') <Expression> 'do'
<operator>
Здесь с помощью БНФ описан синтаксис оператора for, используемого в Delphi.
В квадратные скобки заключается необязательная часть определения, т.е. такая, что синтаксис допускает как присутствие, так и отсутствие этой части, например:
Код:
<if> ::= 'if' <condition> 'then' <operator> ['else' <operator>]
Здесь дано определение условного оператора 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> ::= {<digit>}
Это простое определение не совсем верно, т.к. фигурные скобки указывают на повторение ноль или большее число раз, т.е. пустая строка также будет соответствовать нашему определению <Unsigned>. Чтобы это не происходило, исправим наше определение:
Код:
<Unsigned> ::= <digit> {<digit>}
Теперь синтаксическое правило, определяемое символом <Unsigned>, требует, чтобы выражение состояло из одной или более цифр. В некоторых случаях после закрывающей фигурной скобки ставят символ "+" в верхнем индексе, чтобы показать, что содержимое скобок должно повторяться не менее одного раза. Например, следующее определение <Unsigned> эквивалентно предыдущему:
Код:
<Unsigned> ::= {<digit>}+
Однако это обозначение не является общепризнанным, поэтому мы не будем им пользоваться. Этим исчерпывается набор правил БНФ. Ниже мы будем использовать эти правила для описания различных синтаксических конструкций. При этом мы увидим, что, несмотря на простоту, БНФ позволяет описывать очень сложные конструкции, и это описание просто для понимания.
Синтаксис вещественного числа
Попытаемся использовать БНФ для описания синтаксиса вещественного числа. Сначала опишем этот синтаксис словами: "Перед числом может стоять знак - плюс или минус. Затем идёт одна или несколько цифр. Потом может идти точка, после которой будет ещё одна или несколько цифр. Затем может идти показатель степени E (большое или малое), после которого может стоять знак плюс или минус, а затем должна быть одна или несколько цифр". Указанные правила описывают синтаксис записи вещественных чисел, использующийся в Delphi. Согласно им, правильными вещественными числами считаются, например, выражения "10", "0.1", "+4", "-3.2", "8.26e-5" и т.п. Такие выражения как, например, ".6" и "-.5" этим правилам не удовлетворяют, т.к. перед десятичной точкой должна стоять хотя бы одна цифра. В некоторых языках программирования такая запись допускается, но Delphi требует обязательного наличия целой части.
Теперь переведём описанные выше правила на язык БНФ.
Код:
<Number< ::= [<Sign>] <digit> {<digit>}[<Separator> <digit> {<digit>}]
[<Exponent> [<Sign>] <digit> {<digit>}]
<digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<Sign> ::= '+' | '-'
<Separator> ::= '.'
<Exponent> ::= 'E' | 'e'
Теперь на основе этих правил напишем функцию IsNumber, которая в качестве параметра принимает строку и возвращает True, если эта строка удовлетворяет правилам записи числа, и False, если не удовлетворяет.
PHP код:
// Проверка символа на соответствие
function IsDigit(Ch:Char):Boolean;
begin
Result:=Ch in ['0'..'9']
end;
// Проверка символа на соответствие
function IsSign(Ch:Char):Boolean;
begin
Result:=(Ch='+') or (Ch='-')
end;
// Проверка символа на соответствие
function IsSeparator(Ch:Char):Boolean;
begin
Result:=Ch='.'
end;
// Проверка символа на соответствие
function IsExponent(Ch:Char):Boolean;
begin
Result:=(Ch='E') or (Ch='e')
end;
function IsNumber(const S:string):Boolean;
// Номер символа выражения, который сейчас проверяется
var P:Integer;
begin
Result:=False;
// Проверка, что выражение содержит хотя бы один символ.
// пустая строка не является числом
if Length(S)=0 then
Exit;
// Начинаем проверку с первого символа
P:=1;
// Если первый символ - , переходим к следующему
if IsSign(S[P]) then
Inc(P);
// Проверяем, что в данной позиции стоит хотя бы одна цифра
if (P>Length(S)) or not IsDigit(S[P]) then
Exit;
// Переходим к следующей позиции, пока не достигнем
// конца строки или не встретим не цифру
repeat
Inc(P)
until (P>Length(S)) or not IsDigit(S[P]);
// Если достигли конца строки, выражение корректно - число,
// не имеющее дробной части и экспоненты
if P>Length(S) then
begin
Result:=True;
Exit
end;
// Если следующий символ - , проверяем,
// что после него стоит хотя бы одна цифра
if IsSeparator(S[P]) then
begin
Inc(P);
if (P>Length(S)) or not IsDigit(S[P]) then
Exit;
repeat
Inc(P)
until (P>Length(S)) or not IsDigit(S[P]);
// Если достигли конца строки, выражение корректно - число
// без экспоненты
if P>Length(S) then
begin
Result:=True;
Exit
end
end;
// Если следующий символ - , проверяем,
// что после него стоит всё то, что требуется правилами
if IsExponent(S[P]) then
begin
Inc(P);
if P>Length(S) then
Exit;
if IsSign(S[P]) then
Inc(P);
if (P>Length(S)) or not IsDigit(S[P]) then
Exit;
repeat
Inc(P)
until (P>Length(S)) or not IsDigit(S[P]);
if P>Length(S) then
begin
Result:=True;
Exit
end
end
// Если выполнение дошло до этого места, значит,
// в выражении остались ещё какие-то символы. Т.к. никакие
// дополнительные символы синтаксисом не предусмотрены,
// такое выражение не считается корректным числом.
end;
Для каждого нетерминального символа мы ввели отдельную функцию, разбор начинается с символа самого верхнего уровня - <Number> - и следует правилам, записанным для этого символа. Такой способ синтаксического анализа называется левосторонним рекурсивным нисходящим анализом. Левосторонним потому, что символы в выражении перебираются слева направо, нисходящим - потому, что сначала анализируются символы верхнего уровня, а потом - символы нижнего. Рекурсивность метода на данном примере не видна, т.к. наша грамматика не содержит рекурсивных определений, но мы с этим столкнёмся в последующих примерах.
Пример использования функции IsNumber содержится в прилагаемом архиве, в каталоге IsNumberSample.
В заключение рассмотрим альтернативный способ записи грамматики вещественного числа - графический (такой способ называется синтаксическим графом, или рельсовой диаграммой). Это направленный граф (он показан на рисунке), узлами которого являются терминальные (с круглыми углами) и нетерминальные (с прямыми углами) символы. Двигаться от одного узла к другому можно только по линиям в направлениях, указанных стрелками. В таком графе достаточно легко разобраться, а по возможностям описания синтаксиса он эквивалентен БНФ.
Введение в теорию синтаксического анализа
Похожие темы
Древовидный вид