Разработка компиляторов
Базовые операции
В ситуации [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); }
