А. Григорьев - О чём не пишут в книгах по Delphi

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

Прежде чем двигаться дальше, введем базовые определения. Языком мы будем называть множество строк (в большинстве случаев это будет бесконечное множество). Каждое выражение (в некоторых источниках вместо "выражение" употребляются термины "предложение" или "утверждение") может принадлежать или не принадлежать языку. Например, определим язык так: любая строка произвольной длины, состоящая из нулей и единиц. Тогда выражения "000101001" и "1111" принадлежат языку, а выражения "5х" и "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). Со временем в БНФ были добавлены новые правила описания синтаксиса, и эта форма получила название РБНФ — расширенная БНФ (далее для краткости мы не будем делать различия между БНФ и РБНФ). Совокупность правил, записанных в виде БНФ (или другом формализованным способом), называется грамматикой языка .