Далее мы рассмотрим поведение анализатора грамматики при разборе входной цепочки

Состояния 0 и 1

В начале работы магазин пуст (на самом деле, на вершине магазина находится маркер конца $), и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация [ S’→.S ].

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

Состояние автомата определяется множеством ситуаций. Назовем это состояние 0.

Теперь мы должны выяснить, что произойдет, если анализатор выполнит перенос или свертку. Предположим, что мы выполним перенос x (то есть на вершине магазина окажется x). Этому случаю соответствует ситуация [ S→x. ]. Понятно, что правила S'→S и S→(L) не могут быть применены, поэтому мы их игнорируем. Таким образом, новое состояние, в которое автомат перейдет после переноса в магазин символа x, определяется ситуацией

Это состояние назовем 1.

Состояния 2 и 3

Теперь предположим, что выполнен перенос открывающей круглой скобки. Этому случаю соответствует ситуация [ S→(.L) ]. То есть на вершине магазина окажется открывающая круглая скобка, а входная цепочка должна начинаться с некоторой цепочки, которая выводится из L и перед которой находится открывающая круглая скобка. Таким образом, к нашей ситуации мы должны добавить все ситуации, получающиеся из правил, левая часть которых суть нетерминал L, т.е. [ L→.L,S ] и [ L→.S ]. Помимо этого, поскольку правая часть правила L→S начинается нетерминалом S, мы должны добавить все ситуации, получающиеся из правил, левая часть которых суть нетерминал S, т.е. [ S→.L ] и [ S→.x ]. Таким образом, новое состояние, в которое автомат перейдет после переноса в магазин открывающей круглой скобки, определяется ситуациями:

Это состояние 2. Мы можем изобразить часть первой строки таблицы переходов автомата:

Понятно, что в состоянии 0 свертка выполняться не может.

Обсудим, что произойдет, если в состоянии 0 мы оказались после анализа некоторой цепочки, которая выводится из аксиомы грамматики. Это может случиться, если после переноса x или открывающей круглой скобки произошла свертка по правилу, левая часть которого – S. Все символы правой части такого правила будут извлечены из магазина, и анализатор будет выполнять переход для символа S в состоянии 0. Этому случаю соответствует ситуация [ S'→S.$ ], определяющая состояние 3.

Базовые операции

В ситуации [ S→x. ], определяющей состояние 1, точка стоит в конце правой части правила. Это означает, что вершина магазина, на которой сформирована правая часть правила S→x, готова к свертке. В таком состоянии анализатор выполняет свертку.

Для построения множества состояний определим базовые операции closure (I) и goto (I, X), где I – множество ситуаций, X – символ грамматики (терминал или нетерминал). Операция closure добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал

.

closure (I)

{

do {

for (каждой ситуации [A->w.Xv] из I) {

for (каждого правила грамматики X->u) {

I+=[X->.u]; /* Операция += добавляет элемент к множеству */

}

}

} while (I изменилось);

return I;

}

Операция goto "переносит" точку после символа X. Это означает переход из одного состояния в другое под воздействием символа X.

goto (I, X)

{

J={}; /* {} обозначает пустое множество */

for (каждой ситуации [A->w.Xv] из I) {

J+=[A->wX.v];

}

return closure (J);

}