Pull to refresh

Пишем LR(0)-анализатор. Простыми словами о сложном

Reading time 10 min
Views 27K

Введение



Добрый день.
Не нашел простого и внятного описания данного алгоритма на русском языке. Решил восполнить сей пробел. Прежде всего что это такое? LR(0)-анализатор в первую очередь это синтаксический анализатор. Цель синтаксического анализатора обработать входной поток лексем(базовые элементы языка, которые производит лексический анализатор на основе входного потока символов, примеры лексем — число, запятая, символ) и сопоставить его с описанием языка заданного в определенном формате. Сопоставление заключается в построении определенной структуры данных, чаще всего — дерева. Дальше эта структура пойдет на следующий этап — семантический анализ, где уже компилятор пытается понять смысл, заключенный в дереве.

Существует 2 класса синтаксических анализаторов — восходящие анализаторы и нисходящие. Первые строят дерево начиная с листьев, которые являются входными лексемами, вторые соответственно наоборот начинают с корня дерева. Собственно LR и значит то, что анализатор будет читать поток слева направо (L — 'Left') и строить дерево снизу вверх (пусть не смущает буква R, которая значит Right, объяснения даны чуть ниже). Индекс 0 обозначает то что мы не предпросматриваем следующие лексемы, а работаем только с текущей. Какие же плюсы даёт нам выбор этого типа анализаторов?
  • Он быстр.
  • Покрывает множество языков. То есть если вы придумали язык и описали его, то с большой долей вероятности LR-анализатор его сможет обработать.
  • Синтаксические ошибки обнаруживаются так быстро как это возможно. Сразу же как встречается символ, который не соответствует предыдущему входному потоку, мы можем вывести ошибку об этом.

Есть и недостатки:
  • Относительная сложность построения.
  • Можно вогнать анализатор в ступор неоднозначностью описания языка.




Терминология



Терминальный символ (терминал, terminal) — символ, который может быть дан на вход анализатору пользователем, в нашем случае это лексемы.
Нетерминальный символ (нетерминал, nonterminal) — символ, который обозначает объект языка. Например зададим, что символ A это слагаемое. Конечно, мы можем выбирать и многосимвольные названия — term вместо A.
Контекстно-свободная грамматика (Context-free grammar, CFG) — набор правил вида image, где A — нетерминал, w — произвольный набор терминалов и нетерминалов. В статье я буду употреблять просто грамматика, подразумевая под этом именно контекстно-свободную.
Небольшой пример грамматики, для которой и будем строить анализатор:
image
Эта грамматика описывает неполный набор арифметических операций над двумя числами — 0 и 1. Грамматика является описанием языка. Для того чтобы проверить принадлежит ли входной поток нашему языку, или где-то допустили синтаксическую ошибку (написали 1+, вместо 1+1) ищем возможный путь получения этого входного потока следуя правилам, начиная со стартового нетерминала(у нас это E). Для 1+1 путь будет такой E, применяем правило 2, E + F, правило 1, F + F, правило 4, T + F, правило 8, 1 + F, опять 4, 1 + T, и в конце восьмое, 1 + 1. Как видим мы смогли получить входную строку, это значит что она синтаксически корректна.
Теперь можно и объяснить буковку R в названии анализатора. Она обозначает то, что мы идём от крайних правых частей правил к аксиоме, то есть из более простых правил (7 и 8) собираем исходное (1). L-анализаторы (LL) пытаются по левым частям правил выбрать следующее направление анализа.

Еще следует упомянуть о конечных автоматах (Final-state machine, FSM). Это такая модель, которая имеет набор состояний и входной поток. Стартует автомат с начального состояния и меняет своё состояние исходя из текущего и входного символа. То есть начинаем с состояния 0, если на вход поступает a, то автомат переходит в состояние 1, а если b — в состояние 2. Механика переходов задаётся таблицей, где колонки — текущее состояние, столбцы — входной символ.

Алгоритм



Анализатору требуется несколько вещей для его работы:
  • Сам входной поток, который будем анализировать.
  • Стек (структура данных, которая отвечает правилу LIFO(Last In First Out), проще всего представить как стопку листов — кладём листок в стопку последним, и первым же его берём когда потребуется элемент из стека) для состояний парсера.
  • Таблица действий. Она подсказывает что нам делать в текущем состоянии и с текущим символом на входе.
  • Таблица переходов. Вспомогательная таблица, которая используется в одном из действий.


Здесь необходимо уточнить как будет работать анализатор. Текущим состоянием считается состояние на вершине стека. Смотрим в таблицу действий (индексами являются текущий входной символ и текущее состояние). В этой таблице могут быть 4 типа записей:
  • успех(accepted) — значит то, что входная строка принадлежит данной грамматике.
  • пустота (error) — нет никаких действий, мы в тупике, пользователь ошибся с текущим символом.
  • перенос (shift) — на вершину стека кладём состояние которое отвечает входному символу, читаем следующий
  • свертка (reduce) — у нас в стеке набрались состояния, которые мы можем заменить одним, используя правило грамматики, здесь-то мы и берём значение в таблице переходов. Первый индекс — текущее состояние. Второй — левая часть правила. То есть во что мы свернули последовательность состояний.


В виде кода он выглядит примерно так:
  1.     stack.push(states[0]);
  2.     while (!accepted)
  3.     {
  4.         State * st = stack.top();
  5.         Terminal term = s[inp_pos];
  6.         if (!terms.IsTerm(term))
  7.             error();
  8.         Action * action = actionTable.Get(st, term);
  9.         if (!action)
  10.             error();
  11.         switch (action->Type())
  12.         {
  13.         case ActionAccept:
  14.             accepted = true;
  15.             break;
  16.         case ActionShift:
  17.             inp_pos++;
  18.             stack.push(action->State());
  19.             break;
  20.         case ActionReduce:
  21.             Rule * rule = action->Rule();
  22.             stack.pop(rule->Size());
  23.             State * transferState = transferTable.Get(stack.top(), rule->Left());
  24.             if (!transferState)
  25.                 error();
  26.             stack.push(transferState);
  27.             break;
  28.         }
  29.     }


Как видно, ничего сложного в самом анализе нет. Однако вся заковырка заключается в построении этих хитрых таблиц. Для начала разберёмся что же такое состояние парсера. Это довольно нетривиальная часть алгоритма. И нет, это не просто число. Нам придётся ввести ряд новых понятий.
В первую очередь это пункты (items). Это правило с новым свойством — маркером. Маркер указывает на то, какой элемент мы сейчас ожидаем. Соответственно каждое правило порождает n+1 маркеров, где n — количество символов в правой части правила. Для примера возьмём правило 3. Плюс в кружке обозначает место маркера.
image
Маркер во втором пункте, к примеру, указывает то, что мы ожидаем увидеть знак минуса текущим символом. Объединение нескольких пунктов это набор пунктов (item set). Собственно состояние и является набором пунктов собранных вместе определенным образом.

Но для работы с состояниями нам в первую очередь необходимо замкнуть набор. Это означает что мы хотим получить полноценную ветку анализатора. То есть если в наборе есть пункт, в котором маркер указывает на нетерминал (а у нас все нетерминалы являются левыми частями), то необходимо «развернуть»соответствующий нетерминал. Это происходит простым добавлением пунктов, левыми частями которых является этот нетерминал, и маркер указывает на первый символ. Само собой разворачиваем рекурсивно, если в новом добавленном пункте первый символ — нетерминал, то его тоже замыкаем. Пока не получим полноценный набор. Замкнём набор, в котором только один пункт (номер 3 в предыдущем примере):
image
Развернув F, получаем пункты 2, 3, 4. В 3 и 4 опять нам предлагают разворачивать F, однако у нас в наборе уже есть эти правила, так что пропускаем. А вот T не развернута, сделав это, получим 5 и 6. Всё, замыкание готово.

  1.     for (closed_item in itemset)
  2.     {
  3.         if (closed_item.isClose)
  4.             continue;
  5.         Element marker = closed_item.Marker();
  6.         if (marker.Type() != ElementNonTerm)
  7.         {
  8.             closed_item.isClose = true;
  9.             continue;
  10.         }
  11.         NonTerminal nonTerm = marker.NonTerm();
  12.         item = allitems->First(0, nonTerm);
  13.         while (!item.isend())
  14.         {
  15.             if (!itemset.exists(item))
  16.                 itemset.add(item);
  17.             item.next(0, nonTerm);
  18.         }
  19.         closed_item.isClose = true;
  20.     }

Разобравшись что из себя представляют состояния, можем начать их строить. Для начала введём новое правило, которое является базой вывода и к которому мы должны придти в конце.
image

Первое состояние, конечно, и будет замыкание пункта, основанного на этом правиле и с маркером указывающим на E. Теперь начинаем строить таблицу временного конечного автомата, которая послужит базой для таблиц перехода и действий. Разбиваем состояние на группы по критерию символа на который указывает маркер. Для замыкания из примера будет 4 группы — F-группа, T-группа, 0-группа и 1-группа. Каждая группа — это переход в новое состояние. Первый индекс из перехода — это символ, по которому собственно и группируем (F, T, 0, 1). Второй индекс — текущее состояние. А значение в таблице — это состояние к которому перейдем. Таким образом у нас получиться 4 новых состояния. Их сконструировать довольно просто — в группе в каждом пункте сдвигаем маркер на онду позицию вправо и замыкаем получившийся набор. Это и будет новое состояние.

  1.     firstState.Add(items.First());
  2.     firstState.MakeClosure();
  3.     states.add(firstState);
  4.     size_t state_idx = 0;
  5.     while (state_idx < states.size())
  6.     {
  7.         State * st = states[state_idx];
  8.         GroupedItems group = st->Group();
  9.         for (group_class in group)
  10.         {
  11.             if (group_class->first.Type() == ElementEnd)
  12.                 continue;
  13.             State newState(&items, states.size());
  14.             for (group_item in group_class)
  15.                 newState.Add(group_item, group_item.MarkerInt() + 1);
  16.             newState.MakeClosure();
  17.             State oldState = states.find(newState)
  18.             if (!oldState)
  19.             {
  20.                 states.add(newState);
  21.                 fsmTable.Add(st, group_class->first, newState);
  22.             }
  23.             else
  24.                 fsmTable.Add(st, group_class->first, oldState);
  25.         }
  26.         state_idx++;
  27.     }


Таблица переходов строится очень просто — переносим колонки из таблицы FSM'a, индексы которых являются нетерминалами.

Таблица действий немного интереснее. Часть также переносится из FSM, в свою очередь колонки с терминальными индексами, при этом в ячейки таблицы записывается действие shift с параметром состояния, которое было записано в оригинальной таблице КА. Затем мы добавляем новую колонку '$', которая обозначает конец входной строки. В эту колонку мы заносим события accepted, которое записывается если индекс-состояние содержит пункт image. Значит успех, свернули в первичное правило и при этим входной поток закончился. Затем идут действия свёртки. Для каждого состояния, в котором есть пункт image, где w — любое сочетание терминалов и нетерминалов, записываем во весь ряд (конечно имеется в виду только свободные ячейки, не занятые другими командами) команду reduce, с параметром соответствующего правила, которому принадлежит этот пункт.

  1.     fsmTable.FeedTransferTable(transferTable);
  2.     fsmTable.FeedActionTable(actionTable);
  3.     Item endItem = items.GetItem(1'S', Elements("E", nonTerms));
  4.     for (st in states)
  5.         if (st.HaveItem(endItem))
  6.             actionTable.Add(st, '$'new Action());
  7.     for (st in states)
  8.     {
  9.         ItemList list = st.GetReducable();
  10.         for (listItem in list)
  11.             actionTable.Add(st, new Action(listItem.GetRule()));
  12.     }


Литература



Compilers: Principles, Techniques, and Tools, 1986, Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman
Tags:
Hubs:
+67
Comments 17
Comments Comments 17

Articles