Алгоритм проверки синтаксиса модели

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

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

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

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

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

• 1. Для группы альтернатив с опционной возможностью выбора конструкций внутри нее анализатор возвращается к стартовому символу — символу, следующему за последней корректно разобранной конструкцией, предшествующей данной группе, и рассматривает его, как одну из альтернатив внутри группы.
• 1.1. Если конструкция программы не может быть интерпретирована как одна из альтернатив, анализатор возвращается на предыдущий уровень и анализирует символ, следующий за рассматриваемой группой.
• 1.2. Если стартовый символ какой-либо из альтернатив соответствует текущему рассматриваемому символу, то анализатор начинает разбор текста программы в соответствии с правилами данной альтернативы. Если в какой-то момент текст программы не может интерпретирован как конструкция выбранной группы, анализатор вновь возвращается к стартовому символу и ищет другую подходящую альтернативу в рассматриваемой группе, до того момента пока все альтернативы не будут рассмотрены, либо разбор группы успешно не завершится.
• 1.3. После успешного завершения разбора альтернативы рассматриваемой группы происходит возврат на предыдущий уровень к анализу следующего символа. Если в какой-то момент символ программы не может быть интерпретирован как конструкция языка, анализатор возвращается к стартовому символу и выполняет шаги, описанные в пункте 1.2 настоящего списка.
• 2. Для группы с возможностью множественного присутствия конструкций в тексте языка анализатор выполняет действия аналогичные пункту 1 с той лишь разницей, что после успешного завершения разбора одной из альтернатив, он переходит к началу группы и пытается представить текущий рассматриваемый символ, как одну из альтернатив.
• 2.1. Если на каком-либо этапе анализа невозможно представить текущую лексему как ожидаемую конструкцию языка, анализатор возвращается к символу, следующему за N-1 успешно разобранной альтернативой группы, где N общее количество корректно сопоставленных альтернатив с конструкциями программы, и ищет другой вариант разбора текста программы по алгоритму, описанному в пункте 2.
• 2.2. При появлении ошибки компиляции для последней примененной альтернативы устанавливается статус «Некорректно», количество успешно примененных альтернатив (N) уменьшается на 1, и на следующей итерации разбора программы данная альтернатива исключается из списка возможных вариантов интерпретации текста модели.

Если описание нетерминала содержит метасимвол, определяющий альтернативность применения конструкций языка («|») без использования группировки, данное правило интерпретируется как группа альтернатив, и ее анализ выполняется в соответствие с описанным алгоритмом.

Разбор считается успешным при одновременном завершении анализа дерева разбора и текста программы.

• 1. Если цепочка терминалов стартового символа языка завершилась, а текст программы до конца не разобран, или рассмотрены все возможные варианты представления конструкций модели, и ни один из них не позволяет корректно проанализировать программу, то последняя, наиболее продвинувшаяся в разборе строка считается ошибочной.
• 2. В случае окончания текста программы при незавершенном разборе строки терминалов, выводимых из стартового символа, в качестве ошибочно принимается последняя непустая строка текста модели.

Рассмотрим пример выполнения проверки синтаксиса модели (Иванов Иван Россия Пермский край;), построенной на основе метамодели, приведенной ранее (см. раздел 2.4).

Разбор начинается с первого символа модели («Иванов»), параллельно выполняется обход по построенному дереву (со стартового нетерминала «Адресная книга») (см. рис. 2.7). В качестве ожидаемых символов выступают терминалы, составляющие описание предопределенного нетерминала «Идентификатор», который в свою очередь является дочерним узлом по отношению к элементам дерева разбора «Адресная книга» и «Адресная запись». синтаксис языковой инструментарий программный Однако поскольку нетерминал «Адресная запись» представляет собой группу альтернатив, стартовые символы которой являются одинаковыми, анализатор пытается выполнить разбор правила по первому из вариантов. Таким образом, соответствие первых двух лексем конструкциям языка представлено на рисунке (см. рис. 2.8).

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

Данные шаги повторяются до того момента, пока в строке модели не встретится терминал «;», поскольку ожидаемым символом является пропуск, что не соответствует текущей рассматриваемой лексеме. Поэтому данный вариант разбора признается некорректным (рис. 2.9).

Рисунок 2.8. Проверка синтаксиса модели — разбор первых двух лексем

Анализатор возвращается к самой первой группе (лексема модели «Иванов») и пытается выполнить разбор по второй альтернативе. Одновременное завершение анализа текста модели и конструкций синтаксического дерева определяет успешность последнего варианта, строка разбора (разметка текста) которого выглядит следующим образом: .

Рисунок 2.9. Проверка синтаксиса модели — повторная ошибка компиляции