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

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

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

S -> aABe
A -> Abc
A -> b
B -> d

Свертка цепочки abbcde в аксиому S:

abbcde, aAbcde, aAde, aABe, S.

Правый вывод цепочки:

S->aABe->aAde->aAbcde->abbcde

Восходящий анализатор (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) означает, что

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

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

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

Управляющая программа одинакова для всех LR-анализаторов, а таблица изменяется от одного анализатора к другому. Программа анализатора читает последовательно символы входной цепочки. Программа использует магазин для запоминания строки следующего вида s0X1s1X2…Xmsm, где s m - вершина магазина. Каждый Xi - символ грамматики, а si - символ, называемый состоянием. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним. Комбинация символа состояния на вершине магазина и текущего входного символа используется для индексирования управляющей таблицы и определения операции переноса-свертки. При реализации грамматические символы не обязательно располагаются в магазине; однако, мы будем использовать их при обсуждении для лучшего понимания поведения LR-анализатора.

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

Функция 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 ();       
   }
}

Управляющая таблица LR(0)-анализатора

Обсудим подробно алгоритм построения управляющей таблицы на примере LR(0)-анализаторов.

Заметим, что LR(0)-анализатор принимает решение о своих действиях только на основании содержимого магазина, не учитывая символы входной цепочки. Для иллюстрации построения таблиц LR(0)-анализатора мы будем использовать грамматику G0:

Определение.Пусть G = (VT, VN, P, S) - КС-грамматика. Пополненной грамматикой (augmented grammar) будем называть грамматику G' = (VT, VN +{S'}, P+{S'->S}, S') , где S' - нетерминал, непринадлежащий множеству N.

Определение.Пусть G = (VT, VN, P, S) - КС-грамматика. Будем называть [A->w1.w2, u] LR(k)-ситуацией (LR(k)-item), если A-> w1w2 является правилом из P и u - цепочка терминалов, длина которой не превосходит k .

Понятно, что LR(0)-ситуации не должны содержать терминальной цепочки, то есть мы можем записывать их следующим образом: [A-> w1.w2] .

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

Состояния 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);
}

Алгоритм построения конечного автомата

Теперь обсудим алгоритм построения анализатора. Во-первых, пополним грамматику. Обозначим T множество состояний, E - множество переходов.

T = {closure ([S'->.S])};
E = {};
do 
{
   for (каждого состояния I из T)
   {
      for (каждой ситуации [A->w.Xv] из  I)
      {
         J = goto (I, X);
         T+={J};      /* ко множеству состояний добавляется новое состояние */
         E+=(I->J);   /* ко множеству ребер добавляется ребро, идущее из  
                         состояния I в состояние J. Этот переход 
                         осуществляется по символу X */
      }
   }
} while (E или T изменились);

Поскольку для символа $ операция goto (I, $) не определена, мы выполняем действие accept .

Автомат для грамматики

Для определенной нами грамматики автомат получится следующим:

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

0: {[S'.S], [S->.x], [S->.(L)]}
1: {[S->x.]}
2: {[S-> (.L)], [L->.L,S], [L->.S], [S->.(L)], [S->.x]}
3: {[S'->S.]
4: {[S-> (L.)], [L->L., S]}
5: {[S-> (L).]}
6: {[L->S.]}
7: {[L->L,.S], [S->.(L)], [S->.x]}
8: {[L->L,S.]}

Управляющая таблица

Теперь мы можем вычислить множество сверток R :

R = empty set;
for (each state I in T)
{
   for (each item [A->w.] in I)
   {
      R+={(I, A->w)};
   }
}

Таким образом, алгоритм построения управляющей таблицы автомата состоит из следующих шагов:

Для того, чтобы построить таблицу анализатора для грамматики, поступим следующим образом:

Приведем управляющую таблицу для грамматики G0:

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

LR(1)-анализатор использует для принятия решения один символ входной цепочки. Алгоритм построения управляющей таблицы LR(1)-анализатора подобен уже рассмотренному алгоритму для LR (0)-анализатора, но понятие ситуации в LR(1)-анализаторе более сложное: LR(1)-ситуация состоит из правила грамматики, позиции правой части (представляемой точкой) и одного символа входной строки (lookahead symbol). LR(1)-ситуация выглядит следующим образом: [A-> w1 . w2 , a] , где a - терминальный символ. Ситуация [A-> w1 .w2, a] означает, что цепочка w1 находится на вершине магазина, и префикс входной цепочки выводим из цепочки w2 x. Как и прежде, состояние автомата определяется множеством ситуаций. Для построения управляющей таблицы необходимо переопределить базовые операции closure и goto.

closure (I) {
   do {
      Iold =I;
      for (каждой ситуации [A-> w1.Xw2, z] из I)
         for (любого правила X-> u)
            for (любой цепочки w, принадлежащей FIRST (w2 z))
               I+=[X->.u, w];
   } while (I != Iold);
   return I;
}
goto (I, X) {
   J = {};
   for (каждой ситуации [A-> w1.Xw2, z] из I)
      J+=[A-> w1 X.w2, z];
   return closure (J);
}

Естественно, операция reduce также зависит от символа входной цепочки:

R=[]
foreach (I из T)
   foreach ([A->w., z] из I)
      R+={(I, z, A->w)}

Тройка (I, z, A->w) означает, что в состоянии I для символа z входной цепочки анализатор будет осуществлять свертку по правилу A->w.

Управляющая таблица LR(1)-анализатора

Управляющая таблица LR(1)-анализатора

Построим управляющую таблицу анализатора для следующей грамматики:

E -> E+T 
E  ->  T
T ->  T*F 
T ->  F
F ->  (E) 
F ->  id

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

(1)	E+T
(2)	E->T
(3)	T->T*F
(4)	T->F
(5)	F-> (E)
(6)	F->id

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

Как обычно,

LALR(1)-анализатор

Таблицы LR(1)-анализатора могут оказаться очень большими, ведь даже маленькая грамматика нашего примера привела к автомату с двенадцатью состояниями. Таблицы меньшего размера можно получить путем слияния любых двух состояний, которые совпадают с точностью до символов входной строки (lookahead symbols).

Пример.Рассмотрим грамматику G1 с правилами:

S -> AA
A -> aA
A -> b

Пополним эту грамматику правилом S' -> S.

Для этой грамматики мы получим следующие состояния:

0: {[S'->.S, $], [S->.AA, $], [A->.aA, a], [A->.aA, b], [A->.b, a], [A->.b, b]}
1: {[S'->S., $]}
2: {[S'->A.A, $], A->.aA, $], [A->.b, $]}
3: {[A->a.A, a], [A->a.A, b], [A->.a.A, a], [A->.a.A, b], [A->.b, a], [A->.b, b]}
4: {[A->b., a], [A->b., b]}
5: {[S->AA. $]}
6: {[A->a.A, $], [A->.aA, $], [A->.b, $]}
7:  {[A->b., $]}
8:  {[A->aA.,a], [A->aA.,b]}
9:  {[A->aA.,$]}

Граф переходов выглядит так:

Таблица LALR-анализатора для грамматики G1

Теперь можно построить таблицу LR-анализатора:

Нетрудно заметить, что пары состояний 3 и 6, 4 и 7, 8 и 9 различаются только вторыми компонентами, определяющих их ситуаций. Поэтому мы можем "склеить" эти пары. В результате получится таблица LALR-анализатора:

Пример LR(1)-грамматики

Таким образом, LALR анализатор имеет значительное преимущество в размере таблиц по сравнению с LR. Однако, существуют грамматики, которые можно обработать LR анализатором, но нельзя LALR анализатором. LALR анализатор будет считать их неоднозначными, а LR анализатор не будет.

Пример.Грамматика

S -> aAd   
S -> bBd
S -> aBe
S -> bAe
A -> c
B -> c

не является LALR грамматикой, поскольку для входной цепочки ac мы можем выполнить свертку либо по правилу A -> c (если текущий входной символ d ) либо по правилу B -> c (если текущий входной символ e ).

Однако на практике большинство таких неоднозначностей можно устранить. Перейдем к рассмотрению различных возможных неоднозначностей и методов их устранения.

Неоднозначные грамматики. Конфликты "перенос-свертка"

Вопрос неоднозначности становится особенно важным в процессе построения управляющей таблицы анализатора LR(k)-языка, так как неоднозначность грамматики приводит к конфликтам при построении таблицы.

Рассмотрим сначала конфликты типа перенос-свертка ( shift/reduce ). Конфликты данного типа возникают, когда в процессе работы анализатора возникает выбор между переносом текущего символа на вершину стека и сверткой последовательности, расположенной на вершине стека.

Пример.Пусть дана грамматика G₁, имеющая следующий набор правил:

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

На следующем слайде рассмотрим, что происходит при анализе следующей входной цепочки:

if E1 then if E2 then S1 else S2.

Пример конфликта перенос-свертка

Итак, имеется следующая входная цепочка: if E1 then if E2 then S1 else S2. Рассмотрим работу анализатора пошагово:

После последнего шага возникают две альтернативы: либо (а) применить свертку по правилу 1 к последовательности if E2 then S1 на вершине стека, либо (б) перенести символ else на вершину стека. Обе альтернативы легко угадываются из вида правил 1 и 2. Грамматики с правилами такого типа называются грамматиками с "висящим" (dangling) else .

Для подавляющего большинства языков программирования, имеющих условные операторы описанного вида, действие (б) предпочтительно. Общепринятым правилом для данной ситуации является соотнесение каждого else с "ближайшим" then . Это правило может быть формализовано с использованием однозначной грамматики. Идея в том, чтобы установить соответствие между then и else , что эквивалентно требованию, чтобы между then и else могли появиться только оператор, не являющийся условным оператором, или условный оператор с обязательным else ( if expr then stmt else stmt ).

Разрешение конфликта перенос-свертка

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

Новая грамматика порождает тот же язык, что и старая, но вывод цепочки if E1 then if E2 then S1 else S2 теперь не содержит конфликтов.

Альтернативой построению новой грамматики может служить "соглашение", что в случае конфликта перенос-свертка, перенос является предпочтительным действием.

После принятия одной из этих альтернатив вывод может быть продолжен следующим образом:

Неоднозначные грамматики. Конфликт перенос-перенос

Второй тип конфликта, который может возникнуть, это так называемый конфликт перенос-перенос ( reduce/reduce ), который возникает, когда на вершине стека анализатора возникает строка терминалов, к которой может быть применена свертка по двум различным правилам.

Пример.Рассмотрим грамматику G 2 ('id', '(', ')', '=' и ',' - терминалы) .

В процессе разбора входной цепочки id (id, id) происходит следующее:

Очевидно, что после выполнения последнего шага необходимо произвести свертку находящегося на вершине стека терминала id . Но какое правило использовать? Если использовать правило (5), то будет получен вызов процедуры, если использовать правило (7), то получится вырезка из массива. Чтобы избежать неоднозначности, в первом правиле можно заменить терминал id на другой терминал, например, procid . Но в этом случае, чтобы вернуть правильный лексический класс, лексический анализатор должен выполнить сложную работу по определению, является ли данный идентификатор обозначением процедуры или массива.

Неоднозначные грамматики. Приоритет операций

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

Рассмотрим процесс анализа входной цепочки 2*3+4 .

После выполнения последнего описанного шага возникают две альтернативы: либо (а) произвести свертку последовательности, находящейся на вершине стека, используя правило 3, либо (б) произвести перенос символа + на вершину стека. Так как приоритет умножения больше приоритета сложения, следует сделать свертку. Однако, это противоречит общему правилу, согласно которому, в случае конфликта перенос-свертка, перенос является предпочтительной операцией (которое было таким удобным способом разрешить конфликт в первом случае).

В данной ситуации существует эквивалентная грамматика G 4 , в которой цепочка 2*3+4 имеет единственный вывод:

Неоднозначные грамматики. Ассоциативность

Рассмотрим конфигурации, возникающие при анализе строки 1+2+3 .

После последнего шага возникает конфликт перенос-свертка. Выбор переноса делает сложение правоассоциативным, выбор свертки - левоассоциативным. Так как левоассоциативное сложение более естественно, свертка предпочтительна. В данном случае не существует эквивалентной однозначной грамматики. Формализма грамматик не хватает для описания данной ситуации и необходимы дополнительные средства.

Таким образом, существуют ряд стандартных ситуаций, в которых возникают неоднозначные грамматики. Большая часть подобных ситуаций может быть решена преобразованием грамматик ("висящие" else , приоритет операций и т.д.), но не всегда это необходимо ("висящие" else ) и не всегда является лучшим решением. Существуют ситуации, когда подходящее преобразование грамматики не существует, в таких случаях необходимо привлекать дополнительные механизмы, как это сделано, например, для определения ассоциативности операций.

Литература к лекции