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

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

1. Расширить определение таким образом, чтобы в нем можно было объединять несколько операций сравнения с помощью or, and, xor. При этом потребуется поддержка скобок, т.к. иначе анализатор во многих случаях не сможет отличить логические операторы с низким приоритетом от одноименных арифметических.

2. Изменить грамматику таким образом, чтобы имя функции стало идентификатором, а не зарезервированным словом.

3. Сделать комментарии вложенными. Сейчас в последовательности символов "{a{b}c}" считается, что комментарий заканчивается перед символом "с", т.к. лексический анализатор игнорирует все открывающие фигурные скобки в комментариях. Сделать так, чтобы комментарий считался закрытым только тогда, когда число закрывающих скобок сравняется с числом открывающих.

4. Добавить поддержку шестнадцатеричных целых констант. Для их записи использовать, как и в Delphi, символ "$", после которого должна идти последовательность из одной или нескольких шестнадцатеричных цифр.

5. Добавить возможность изменения приоритета операций с помощью не только круглых, но и квадратных скобок. Рассмотреть два варианта: когда круглые и квадратные скобки полностью взаимозаменяемы (т.е., например, допустимо выражение 2*(2+2]) и когда закрывающая скобка должна быть такой же формы, как и открывающая.

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

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

Теперь, познакомившись с синтаксическим анализом на практике, вернемся к теории и немного поговорим о типах грамматик и об альтернативных методах синтаксического анализа и вычисления выражений. Эти вопросы мы здесь рассмотрим только ознакомительно, а более детальное их описание можно найти в [6–8].

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

1. Общие грамматики . Синтаксические правила в этих грамматиках имеют вид a ::= b, где аи b— произвольные цепочки из терминальных и нетерминальных символов (возможно, пустые). Единственное требование — хотя бы в одной из этих цепочек должен быть хотя бы один нетерминальный символ.

2. Контекстно-зависимые грамматики . Здесь правила имеют следующий вид ab ::= acb, где а, bи c— произвольные цепочки терминальных и нетерминальных символов, — некоторый нетерминальный символ. Таким образом, символ может заменяться на последовательность символов cтолько в контексте цепочек aи b.

3. Контекстно-свободные грамматики . Это контекстно-зависимые грамматики, из которых убран контекст, т.е. правила записываются в виде ::= с. В контекстно-свободных грамматиках нетерминальный символ заменяется на цепочку cв любом контексте.

4. Регулярные (они же — автоматные ) грамматики. Это контекстно-свободные грамматики, в которых запрещены любые формы рекурсивных определений.

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

Регулярные грамматики описывают множество синтаксических правил, встречающихся в жизни, поэтому их часто применяют. Существует также альтернативный способ записи регулярной грамматики — регулярные выражения (мы их здесь рассматривать не будем). Различные библиотеки для распознавания регулярных выражений очень популярны, классы для распознавания регулярных выражений входят в .NET. Функция поиска в Delphi (меню Search/Find…. и т.п.) включает в себя возможности поиска последовательностей символов, заданных регулярным выражением (опция Regular expressionsв диалоговом окне), поэтому краткое описание синтаксиса регулярных выражений можно найти в справке Delphi.

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

С регулярными грамматиками тесно связаны конечные автоматы. Конечный автомат — это устройство (виртуальное), с входом, на который подаются данные, набором состояний и набором правил перехода из одного состояния в другое. Правила перехода определяются символами, подаваемыми на вход, и формулируются следующим образом: "Если автомат находится в состоянии А, и на вход поступил символ X, автомат переходит в состояние В". Таким образом, выражение посимвольно передается на вход конечного автомата, и каждый символ вызывает переход автомата из одного состояния в другое (допустима ситуация, когда символ оставляет текущее состояние неизменным). Если при поступлении очередного символа автомат не находит правила, которое определяет очередной переход, считается, что на вход подан некорректный символ, т.е. выражение ошибочно. Допустимость выражения определяется также тем, в каком состоянии оказывается автомат после того, как все выражение подано на его вход. Часть состояний считается допустимыми в качестве конечного состояния, часть — недопустимыми. Если по окончании своей работы автомат оказывается в недопустимом состоянии, выражение также признается ошибочным.