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

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

Активный 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 формируется в вершине стека.

Т.о. опять основа y опять оказалась в вершине стека. Стек содержит префикс правой сентенциальной формы.

21. SLR (1) – разбор. Ситуация. Пополненная грамматика.

SLR(1) — восходящий алгоритм синтаксического разбора. Представляет собой расширение алгоритма LR(0) и работает тогда когда LR(0) таблицы грамматики невозможно из-за конфликтов сдвиг-приведение или приведение-приведение.

В процессе работы в стеке формируется активный префикс, это начальная часть правой сентенциальной формы. Если активный префикс содержит основу то можно делать свертку. Основу в стеке мы будем распознавать конечным автоматом. В случае неоднозначности выбора операций будем использовать м-во FOLLOW.

Рассмотрим простые SLR грамматики.

Существуют 3 класса построения табл. Action и Goto:

1)LR(0) грам. они не обращают внимания на входные символы, но используют множество Follow. Этот класс позволяет получить минимальную по размеру таблицу.

2)LR(1) грам. таблицы получаются гораздо больше чем SLR грам.

3)LALR(1) занимает промежуточное место между SLR и LR(1) грам. Этот метод дает такие же по объему табл., как и при SLR.

Рассмотрим SLR методы.

Метод не анализирует, а использует множество Follow. Каждая продукция грамматики может ожидать в стеке свою основу, это ожидание разбивается на ряд этапов, в зависимости, какая часть основы уже распознана.

Фазу ожидания правила называют – ситуацией (Item).

Если есть правило [A→XYZ], то для этого правила возможны 4 ситуации (LR(0) – ситуации):

1. [A → • X Y Z]

2. [A → X • Y Z]

3. [A → X Y • Z]

4. [A → X Y Z •]

‘•’ – указывает какой фрагмент основы уже распознан в данной ситуации

f → ε [A→ •] эту ситуацию можно представить парой чисел:

1. Номер продукции;

2. Позиция точки;

Эти ситуации можно расшифровать как состояния конечного не детерминированного автомата распознающего основы.

Если грамматика G имеет стартовый символ S, то грамматика G’ будет для нее дополненной грамматикой, если в нее добавить стартовый символ S’ и продукцию S→ S’.

Фазу ожидания основы будем называть ситуацией, т.е.ситуация – это продукция из заданной грамматики, в которую помещена точка, отделяющая распознанную часть от нераспознанной части. Например, если в грамматике есть продукция Аxyz, то для нее возможна ситуация [Аxyz], которая соответствует состоянию автомата в котором анализатор получил на входе x и y и теперь ожидает z. Вообще для продукции Аxyz возможны следующие ситуации: [Аxyz], [Аxyz], [Аxyz], [Аxyz]. Для продукции вида А возможна только одна ситуация [A].

Начальное правило S' вводится для того, чтобы свертка, в которой используется нулевое правило, можно было интерпретировать как признак того, что входная цепочка допустима, т.е успешное завершение разбора (accept).