Активный префикс. Обосновать, что основа всегда формируется в вершине стека.

Множество префиксов правой сентенциальной формы, которые могут появиться в стеке при разборе методом «сдвиг-свертка» наз-ся активными префиксами.

Активный viable – с английского «способный к жизни», «жизнеспособный».

Активные префиксы можно распознать конечным автоматом, который будет решать, какую команду можно выполнить: сдвиг, свертка, ошибка. Необходимо убедиться, что основа всегда появляется на поверхности стека и не может сформироваться внутри него. Чтобы убедится в этом нужно рассмотреть два случая: 1) Когда есть в правой части нетерминал: S=>* αAz => (используя продукцию A->βBy) αβByz => (B-> γ) αβγyz 2) когда терминалов нет: S ⇒^* α B x A z ⇒ ( A → y ) α B x y z ⇒( B → γ ) α γ x y z

В данном случае в обоих примерах основой является терминал z

Рассмотрим состояние стека в первом случае:

стек $ α β γ Буфер y z $

После свертки:

стек $ α β B Буфер y z $

Сдвиг

стек $ α β B y Буфер y z $

Рассмотрим состояние стека во втором случае:

стек $ α γ Буфер x y z $

После свертки

стек $ α B Буфер x y z $

Сдвиг-Сдвиг

стек $ α B x y Буфер z $

В обоих случаях основа S формируется в вершине стека. Стек содержит префикс правой сентенциальной формы.

Синтезируемые атрибуты. Их обработка в алгоритме сдвиг–свертка.

Атрибутные грамматики – продукции КС грамматики, которые снабжены атрибутами и функциями, вычисляющие эти атрибуты. Они являются расширением контекстно-свободными грамматик. С грамматическими символами связывают множество атрибутов. Синтезируемые атрибуты вычисляют свои значения, используя только значения атрибутов потомков. Наследуемые атрибуты вычисляют свои значения, обращаясь к братьям и родителям Атрибутные грамматики, которые используют только синтезируемые атрибуты, называются S-атрибутными грамматиками.

Вычисление синтез. атрибутов: В соответствие каждой продукции ставиться семантическое правило. Атрибуты хранятся в стеке вместе с грамматическими символами (в отдельном поле записи или отдельной таблицы связанной индексами). Когда в стек попадет терминал вместе с ним заноситься и его лексическое значение. Когда выполняется свертка, тогда из стека извлекаются атрибуты правой части продукции и исходя из семантического правила выполняется вычисление атрибута нетерминала левой части продукции (значение записывается также в стек). Указатель на вершину стека атрибута равен указателю стека грамматических символов.

яв-ся узлами графа зависимости. Дуги этого графа направлены и обозначают зав-ть одного атрибута от другого. От х зависит а – это как мы читаем стрелки.

Переходы в SLR (1) анализаторе. Функция GOTO. Допустимая ситуация.

Переход представляет собой множество ситуаций, в которые можно перейти из множества ситуаций I по грамматическому символу х, то есть по терминалу или нетерминалу. При выполнении функции (goto (I,x)) строят замыкание множества состояний вида [Aàax×b], если в I есть ситуация [Aàa×xb], то есть точка переходит за символ х в ситуациях. С помощью этих переходов строится таблица goto.

Функция goto (I, X), где I-множество ситуаций, X - символ грамматики. goto (I, X) определяется как замыкание множества ситуаций, принадлежащих I. Функция возвращает новое состояние конечного автомата.

Пусть есть I={[E’→E*], [E→E*+T]}

Построим результат Goto(I,+):

[E→*E+T]

[T →*T•F]

[T →*F]

[F →*(E)]

[F →*id].

Ситуация A->β1*β2 называется допустимой для активного префикса αβ1 если существует порождение S’ =>_R* αAq =>_R αβ1β2γ. Ситуация может быть допустимой для многих активных префиксов.

Главная теорема LR-разбора: Множество допустимых ситуаций активного префикса γ – в точности то множество ситуаций, которые допустимы из начального состояния по пути, помеченному γ в детерминированном конечном автомате, построенному из канонической совокупности множеств ситуаций и переходов, определенных функцией goto.

Наследуемые атрибуты. Граф зависимостей.

Значения атрибутов определяется семантическими правилами, связанными с продукциями грамматики. в зависимости от вида семантических правил атрибуты м.б. синтезируемыми и наследуемыми.

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

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

Если есть продукция A → XY и связанное с ней семантическое правило A.a:= f (X.x, Y.y), то для них получится сл. фрагмент графа зависимостей:

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

У нас есть функция, которая получает два аргумента, функция вычисляет значение, которое присваивается атрибутам узла. В таком случае получится след. фрагмент графа зависимостей. Здесь мы видим фрагмент дерева разбора. Кружками обозначены атрибуты. Эти атрибуты

Алгоритм LR – разбора.

LR-грамматический разбор используется для большого класса КСГ. Полное название – LR(k), т.е. синтаксический анализатор рассматривает последовательность слева направо (L),используется правый вывод (R), k определяет количество символов, рассмотренных во входной последовательности для выбора продукции. Если К не указывается, то К=1.

Алгоритм LR-разбора состоит в следующем.

Занести в стек символ конца входной последовательности (eof)

Занести в стек начальное состояние конечного автомата

Распознать лексему

Повторять

Если action[состояние в вершине стека, лексема]=shift S

то занести в стек лексему и состояние S, после чего распознать следующую лексему

Если action[состояние в вершине стека, лексема]=reduce P

то извлечь из стека столько пар <состояние, грамматический символ>, сколько грамматических символов составляют правую часть правила P. В стек занести нетерминал левой части продукции P и goto[состояние в вершине стека, нетерминал левой части продукции P]

Если action[состояние в вершине стека, лексема] = accept

то вывести пользователю сообщение об успешном разборе и выйти из цикла

Если action[состояние в вершине стека, лексема] = ошибка

то обработать ошибочную ситуацию

Пока false

Достоинства LR- разбора:

1) LR-анализатор может использоваться практически для всех конструкций языков программирования, которые описываются при помощи КСГ.

2) LR-анализатор позволяет обнаруживать ошибки, как только они встретятся во входной последовательности.

3) достаточно сложно строить таблицы разбора.