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

Введение

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

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

• Он быстр.
• Покрывает множество языков. То есть если вы придумали язык и описали его, то с большой долей вероятности LR-анализатор его сможет обработать.
• Синтаксические ошибки обнаруживаются так быстро как это возможно. Сразу же как встречается символ, который не соответствует предыдущему входному потоку, мы можем вывести ошибку об этом.

Есть и недостатки:

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

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

Терминальный символ (терминал, terminal) — символ, который может быть дан на вход анализатору пользователем, в нашем случае это лексемы.
Нетерминальный символ (нетерминал, nonterminal) — символ, который обозначает объект языка. Например зададим, что символ A это слагаемое. Конечно, мы можем выбирать и многосимвольные названия — term вместо A.
Контекстно-свободная грамматика (Context-free grammar, CFG) — набор правил вида , где A — нетерминал, w — произвольный набор терминалов и нетерминалов. В статье я буду употреблять просто грамматика, подразумевая под этом именно контекстно-свободную.
Небольшой пример грамматики, для которой и будем строить анализатор:

Эта грамматика описывает неполный набор арифметических операций над двумя числами — 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. Плюс в кружке обозначает место маркера.

Маркер во втором пункте, к примеру, указывает то, что мы ожидаем увидеть знак минуса текущим символом. Объединение нескольких пунктов это набор пунктов (item set). Собственно состояние и является набором пунктов собранных вместе определенным образом.

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

Развернув 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.     }

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


Первое состояние, конечно, и будет замыкание пункта, основанного на этом правиле и с маркером указывающим на 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, которое записывается если индекс-состояние содержит пункт . Значит успех, свернули в первичное правило и при этим входной поток закончился. Затем идут действия свёртки. Для каждого состояния, в котором есть пункт , где 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