65 (Вопросы по разным темам с ответами (программирование)), страница 2

T'→ *F | *FT'

F → (E) | num

Нетрудно показать, что получившаяся грамматика обладает свойством LL(1).

Еще одна подобная проблема связана с тем, что два правила для одного и того же нетерминала начинаются одними и теми же символами. Например,

S → if E then S else S

S → if E then S

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

S → if E then S S’

S' →

S'→ else S

Для полученной грамматики может быть реализован метод рекурсивного спуска.

Восходящие анализаторы

Восходящий анализатор (bottom-up parsing) предназначен для построения дерева разбора, начиная с листьев и двигаясь вверх к корню дерева разбора. Мы можем представить себе этот процесс как "свертку" исходной строки w к аксиоме грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки w и правой части какого-то правила грамматики и замене этой подстроки на нетерминал, являющийся левой частью правила. Если на каждом шаге подстрока выбирается правильно, то в результате мы получим правый вывод строки w.

Пример. Рассмотрим грамматику

S→aABe

A→Abc

A→b

B→d

Цепочка abbcde может быть свернута в аксиому следующим образом:

abbcde, aAbcde, aAde, aABe, S.

Фактически, эта последовательность представляет собой правый вывод этой цепочки, рассматриваемый справа налево:

S→aABe→aAde→aAbcde→abbcde.

LR(k)-анализатор

LR(k) означает, что

• входная цепочка обрабатывается слева направо (left-to-right parse);

• выполняется правый вывод (rightmost derivation);

• не более k символов цепочки (k-token lookahead) используются для принятия решения.

При LR(k)-анализе применяется метод "перенос-свертка" (shift-reduce). Этот метод использует магазинный автомат. Суть метода сводится к следующему. Символы входной цепочки переносятся в магазин до тех пор, пока на вершине магазина не накопится цепочка, совпадающая с правой частью какого-нибудь из правил (операция "перенос", "shift"). Далее все символы этой цепочки извлекаются из магазина и на их место помещается нетерминал, находящийся в левой части этого правила (операция "свертка", "reduce"). Входная цепочка допускается автоматом, если после переноса в автомат последнего символа входной цепочки и выполнения операции свертка, в магазине окажется только аксиома грамматики.

Анализатор состоит из входной цепочки, выхода, магазина, управляющей программы и таблицы, которая имеет две части (действие и переход). Схема такого анализатора выглядит следующим образом:

Выход

Действие

Переход

Управляющая программа

Входная

цепочка

Управляющая программа анализатора

Управляющая программа одинакова для всех LR-анализаторов, а таблица изменяется от одного анализатора к другому. Программа анализатора читает последовательно символы входной цепочки. Программа использует магазин для запоминания строки следующего вида s₀X₁s₁X₂…X_ms_m, где s_m – вершина магазина. Каждый X_i – символ грамматики, а s_i – символ, называемый состоянием. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним. Комбинация символа состояния на вершине магазина и текущего входного символа используется для индексирования управляющей таблицы и определения операции переноса-свертки. При реализации грамматические символы не обязательно располагаются в магазине; однако, мы будем использовать их при обсуждении для лучшего понимания поведения LR-анализатора.

Программа, управляющая LR-анализатором, ведет себя следующим образом. Рассматривается пара: s_m – текущее состояние на вершине магазина, a_i – текущий входной символ; после этого вычисляется action [s_m, a_i], которое может иметь одно из четырех значений:

1. shift s, где s – состояние,

2. свертка по правилу A→β,

3. допуск (accept)

4. ошибка.

Функция goto получает состояние и символ грамматики и выдает состояние. Функция goto, строящаяся по грамматике G, есть функция переходов детерминированного магазинного автомата, который распознает язык, порождаемый грамматикой G.

Управляющая программа выглядит следующим образом:

Установить ip на первый символ входной цепочки w$;

while (цепочка не закончилась)

{

Пусть s – состояние на вершине магазина,

a – символ входной цепочки, на который указывает ip.

if (action [s, a] == shift s’)

{

push (a);

push (s’);

ip++;

}

else if (action [s, a] == reduce A→β)

{

for (i=1; i<=|β|; i++)

{

pop ();

pop ();

}

Пусть s’ – состояние на вершине магазина;

push (A);

push (goto [s’, A]);

Вывод правила (A→β);

}

else if (action [s, a] == accept)

{

return success;

}

else

{

error ();

}

}