Алгоритмы разбора грамматики DSL

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

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

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

Метамодель может содержать следующие семантические ошибки:

• 1. Наличие нескольких корней дерева разбора.
• 2. Отсутствие корня в дереве.
• 3. Неоднократное описание нетерминала.
• 4. Рекурсивное описание нетерминала, то есть определение его через самого себя.

Рассмотрим пример построения дерева синтаксического разбора для заданного языка (рис. 2.3). В данном дереве окружностями с непрерывной линией обозначены нетерминалы, с пунктирной линией — терминалы, а со штрих пунктирной — метасимволы. Корневые элементы каждого поддерева выделены жирной линией, стартовый символ всего языка представлен окружностью с двойной линией.

Рисунок 2.3. Язык для построения дерева разбора.

Изначально в списке поддеревьев содержатся предопределенные нетерминалы (цифра, буква, идентификатор (идент.), пропуск) и их описание. Далее в качестве корневого элемента нового поддерева добавляется нетерминал «Адресная книга» (АК) и его описание в виде узлов: метасимволы «{», «}», «;». нетерминал «Адресная запись» (АЗ) (см. рис. 2.4).

Рисунок 2.4. Дерево разбора — добавление первого правила

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

Рисунок 2.5. Дерево разбора — добавление ссылки на нетерминал первого правила

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

Рисунок 2.6. Дерево разбора — добавление второго правила

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

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

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

Рисунок 2.7. Дерево разбора — результат