Нисходящий разбор в терминах грамматик

Синтез процедуры

Пусть есть грамматика с правилами:

S:=aSbS;

S:=aS;

S:=c.

Рассмотрим цепочку aacbc и запишем для нее функцию отбражения:

1. d (q, e, SZ) = (q, aSbS, 1); Группу 1.,2. можно заменить на:

2. d (q, e, SZ) = (q, aS, 2); d (q, e, SZ) = (q, SbS, 1);

3. d (q, e, SZ) = (q, c, 3); d (q, e, SZ) = (q, S, 2).

d (q, i, iZ) = (q, Z, e).

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

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

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

Будем использовать входной указатель, который в начальный момент времени указывает на самый левый символ рассматриваемой цепочки. Процесс начнем с корня. Вершина, которую мы рассматриваем в данный момент, – активная. Если активная вершина помечена некоторым нетерминалом «А», нужно выбрать первую его альтернативу. (Пусть A:=x₁…x_k) К вершине А добавить к прямых потомков и сделать активной вершину х₁ (самую левую). Если активная вершина помечена терминалом, нужно сравнить с ним текущий входной символ и сделать активной вершину справа от нее, а также сдвинуть входной указатель на одну позицию вправо. Если этот терминал не совпадает с текущим входным символом, нужно вернуться к вершине, где было использовано предыдущее правило.

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

Начало: первая активная вершина – корень дерева (S). Правила занумерованы (альтернативы нетерминала). В соответствии с установленным порядком выбираемая альтернатива в данном случае 1.Входной указатель стоит на первом символе исследуемой цепочки. В рассматриваемом случае активная вершина – терминал.

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

Снова используется альтернатива 1. Активный символ - терминал (а) совпадает с символом, который помечен указателем. Передвигаем указатель вправо. Активная вершина S. У первых двух альтернатив первый терминал не совпадает с символом, который помечен указателем. Испытывается 3-я альтернатива. Передвинуть указатель. Активная вершина – вершина, помеченная терминальным символом (b). Сравнить и передвинуть указатель. Активная вершина – вершина справа от b. Используем альтернативу 3. Вершины совпадают, входная цепочка прочитана. Однако в дереве остались 2 неиспользованных вершины. Последовательность используемых правил не позволила констатировать факт принадлежности рассматриваемой цепочки к данной грамматике.

Осуществить возврат по дереву до вершины, у которой имеется не опробованная альтернатива.

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