Построение отношения предшествования

Отношение «глубины» официально называется отношением предшествования. Затрагивает оно не все пары символов (вершин) в синтаксических деревьях, а только граничные вершины поддеревьев. Образно говоря, это отношения типа «старший сын младшего брата». Для их построения необходимо рассматривать структуру порождаемой грамматикой деревьев. Понятно, что это можно сделать и простым перебором, но в общем виде можно обойтись анализом правых частей правил ФГ и с использованием множествам FIRST и LAST встречающихся нетерминальных символов.

Напомним, что множество FIRST(U) нетерминального символа U – это терминальные символы, которые могут стоять первыми в цепочках, выводимых из U. Аналогичным образом определяется множество LAST⁺(U), которое включает не только терминалы, но и промежуточные нетерминалы, на которые может оканчиваться цепочка, выводимая из U. При отсутствии аннулирующих правил (правил с пустыми правыми частями) в ФГ, используемых в восходящих методах разбора, эти множества строятся довольно легко. На синтаксическом дереве множества FIRST и LAST⁺ выглядят как левая нижняя граница и правая границы множества всех деревьев с корневой вершиной U.

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

1. Все пары соседних терминальных символов находятся в отношении «равенства» = или одинаковой глубины. Этим все и ограничивается, поскольку они не порождают поддеревьев

E:: aabb => a = b

2. Для пары нетерминал-терминал правая граница поддерева, выстраиваемая на основе нетерминала (множество LAST ⁺) находится «глубже» правого терминала, т.е.

E:: aAbb => LAST⁺(A) > b

Кроме того, сами символы этой пары находятся «на одинаковой глубине», т.е.

E:: aAbb => A = b

3. Аналогичное обратное отношение выстраивается для пары терминал-нетерминал: левая нижняя граница поддерева, выстраиваемого на нетерминале «глубже» левого терминала

E:: aaBb => a < FIRST(B)

Отношение a=B эта пара не устанавливает, поскольку для метода «свертка-перенос» правый символ является символом входной строки и не может быть терминальным (этот элемент отношения для метода не является необходимым).

4. Наиболее сложное, но и самое «продуктивное» соотношение – два рядом стоящих нетерминала, которые производят сразу два отношения:

E:: aABb => LAST⁺(A) > FIRST(B), A < FIRST(B)

Что «в переводе на русский язык означает»: правая граница левого поддерева «глубже» левой нижней границы правого смежного поддерева, но при этом корневая вершина левого поддерева «выше» той же самой левой нижней границы правого смежного поддерева.

Этот элемент отношения также «имеет отношение» к механизму распознавания. Дело в том, что метод свертка-перенос последовательно сворачивает в стеке основу, используя предшествование LAST⁺(A) > FIRST(B) до появления в стеке нетерминала A, после чего отношение меняется на противоположное и начинается перенос следующего фрагмента входного предложения.