Восходящие методы анализа. Свертка-перенос

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

T = {a, *, +, #} N = {Z, U, B, A}

Z:: U# // 1

U:: U+B // 2

U:: B // 3

B:: *B // 4

B:: A // 5

A:: Aa // 6

A:: a // 7

Приведенная грамматика продуцирует цепочки вида **aa+aa+*aaa. Из правил грамматики видно, что первая замена производится по правилу A:: a, иначе в цепочке просто нет необходимых нетерминалов для подстановки. Затем в нетерминалу A справа «присоединяются» терминалы a из входной строки, а уже затем – символы * слева.

Теперь нужно обсудить, как будет выглядеть распознаватель и каковы будут принципы его работы. Во-первых, по аналогии с нисходящим разбором можно предположить, что для обнаружения основы достаточно пары символов – последнего символа основы и следующего символа строки (в нашем примере это сочетание aa). Т.е. для каждой пары символов грамматики однозначно можно сформулировать утверждение, является ли эта пара концом основы или нет. Опять-таки это связано с глубиной просмотра вперед входной строки – она равна 1.

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

Теперь можно сформулировать основные принципы восходящего разбора c использованием магазинного автомата (МА), именуемого также методом «свертка-перенос»:

• Первоначально в стек помещается первый символ входной строки, а второй становится текущим;
• МА выполняет два основных действия: перенос (сдвиг - shift) очередного символа из входной строки в стек (с переходом к следующему);
• Поиск правила, правая часть которого хранится в стеке и замена ее на левую – свертка (reduce);
• Решение, какое из действий – перенос или свертка выполняется на данном шаге, принимается на основе анализа пары символов – символа в вершине стека и очередного символа входной строки. Свертка соответствует наличию в стеке основы, при ее отсутствии выполняется перенос. Управляющими данными МА является таблица, содержащая для каждой пары символов грамматики указание на выполняемое действие (свертка, перенос или недопустимое сочетание -ошибка) и сами правила грамматики.
• Положительным результатом работы МА будет наличие начального нетерминала грамматики в стеке при пустой входной строке.

Как следует из описания, алгоритм не строит синтаксическое дерево, а производит его обход «снизу-вверх» и «слева-направо». В соответствии с этим, грамматика, допускающая распознавание подобным методом, называется LR(1) – (left – просмотр входной строки слева направо, right- правая подстановка – замена правой части на левую, восходящий разбор, 1- глубина просмотра входной строки для принятия решения ).

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

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