Отношение предшествования символов в ФГ

Для формального метода построения управляющей таблицы можно использовать простые соотношения, которые устанавливаются между символами ФГ в соответствии с имеющейся вложенностью ее правил. Для начала посмотрим, какие отношения между символами ФГ требуется установить при восходящем разборе, представляющем собой построение дерева «снизу-вверх» и «слева-направо». Напомним, что в методе «свертка-перенос» в стеке находится верхняя граница строяшегося дерева (на рисунке – символы dbDc). Если в процессе переноса символов входной строки в стек в нем оказывается полная правая часть правила «основа», то происходит свертка – замена левой части на правую. На самом дереве это выглядит как достраивание очередной вершины. Решение об обнаружении основы принимается, исходя из сочетания пары символов в вершине стека и во входной строке (c и d).

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

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