Анализ текста на формальном языке

Описание (текст) на ФЯ, подлежащее анализу, должно находиться в файле стандартного текстового формата DOS; файл может иметь любое имя и расширение, по умолчанию предлагается расширение "snt". Анализ реализуется в три прохода (фазы): лексический, синтаксический и семан­тический анализ.

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

- ключевые слова языка, " •

- разделители языка,

- идентификаторы, не являющиеся ключевыми словами языка,

- целые числа без знака (в диапазоне 0..65535),

- вещественные числа без знака (в диапазоне 2.9е-39.. 1.7е38).

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

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

Лексический анализ может сопровождаться протоколированием -фиксированием в отдельном файле последовательности принимаемых анализатором решений; файл протокола имеет имя, совпадающее с име­нем описания, и расширение "lap". Пользователь системы управляет соз­данием и отображением на экран дисплея протокола.

Синтаксический анализ предложения проводится левосторонним нисходящим методом с ограниченными возвратами (бектрекинг).

Пользователю системы предоставлена возможность управления состоянием грамматики и описания на ФЯ во время анализа. Синтак­сический анализ может сопровождаться построением дерева разбора предложения, представляемого в скобочной форме. Особенности такого представления проиллюстрируем на примере.

Грамматика арифметических выражений:

врж::=?_<_терм_>+<_врж_>_|_<_терм_>-<_врж_>_|_<_терм_>_?**

терм::=?_<_мнж_>*<_терм_>_|_<_мнж_>/<_терм_>_|_<_мнж_>_? *

мнж::=?_ (<_врж_>) _|_ <_Numb_> _? **

Предложение, соответствующее этой грамматике:

6-4/2

Две различные графические формы дерева разбора приведены на рис. 2. В случае а) имена продукций не указаны, в случае б) имена про­дукций указаны.

Дерево разбора этого предложения в скобочной форме имеет вид: (врж (терм (мнж 6 мнж) терм)-(терм (мнж 4 мнж) / (мнж 2 мнж) терм) врж)

Файл, содержащий дерево разбора, имеет расширение "t". Пользо­вателю предоставлена возможность управления созданием, отображени­ем и составом дерева.

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

Система "Грамматика" регламентирует связь СП с синтаксисом ФЯ следующим образом. СП нумеруются целыми числами из диапазона 0..65535. В описании грамматики указываются точки вызова и номера СП записью вида (_ N _), где "(_", "_)" - метасимволы языка описания грамматик, N - номер СП.

Просматривая в процессе синтаксического анализа продукции и встречая в них точки вызова СП, система формирует план семантических действий - последовательность записей, содержащих номер СП и пара­метр СП, которым является последнее на данный момент встреченное в анализируемом описании ключевое слово или разделитель языка, иден­тификатор, целое или вещественное число. В случае успешного заверше­ния синтаксического анализа полученная последовательность записыва­ется в отдельный файл. План семантических действий может быть сфор­мирован в двоичном или символьном представлении в зависимости от цели, преследуемой пользователем: план в двоичном представлении эф­фективно обрабатывается компьютером, тогда как план в символьном представлении более удобен для изучения, контроля, понимания принци­пов его формирования и использования. Файл с планом в двоичном представлении имеет расширение "smb", план в символьном представле­нии - расширение "sms"; имена обоих файлов совпадают с именем файла, содержащего разбираемое предложение.

Семантический анализ является синтаксически управляемым в том смысле, что последовательность семантических действий полностью определяется синтаксической структурой предложения. В приложении 1 приведена грамматика с вызовами СП, эквивалентная в синтаксическом отношении рассмотренной выше грамматике паскалеподобного языка. Точки вызова расставлены так, что обеспечивают получение всей необ­ходимой для проведения семантического анализа информации: имен, чисел, операций и т.д.

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

Система "Грамматика" предлагает несложный программный ин­терфейс для программ семантического анализа, создаваемых на языке Turbo Pascal. Исчерпывающее описание интерфейса приведено в прило­жении 2. Пример программы на языке Pascal, осуществляющей простей­ший семантический анализ - вывод на экран дисплея плана семан­тических действий, приведен в приложении 3.