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

Введение



Добрый день.
Не нашел простого и внятного описания данного алгоритма на русском языке. Решил восполнить сей пробел. Прежде всего что это такое? 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
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 17

    0
    «Можно вогнать анализатор в ступор неоднозначностью описания языка.»
    Например, как?
      +1
      Очень просто. Есть у нас язык, который представляет из себя последовательность символов 'a' неопределенной длины. Примеры конструкций языка — a, aaaa, aaa....aaa.
      Грамматика его крайне проста:
      image
      Так вот, здесь LR(0)-парсер спасует из-за того, что состояние номер 1 (сразу после начального) будет таким:
      image
      И когда начнём строить таблицы, то получим то, что для этого состояния применимо и свертка (по правилу 1), и перенос (по правилу 2).
        0
        Круто. Теперь я чувствую себя умным. :D
          +10
          А я, блин, наоборот :(
          0
          А вы не могли бы поправить грамматику и сделать ее однозначной?
            0
            достаточно во втором правиле в правой части поменять A и a местами.
        0
        Молодец, отличная статья.
        Тема, кстати, для меня сейчас очень актуальна.
          0
          Про неоднозначность описания языка я бы опустил момент, потому что она может вогнать в ступор не только LR-анализатор, но и многие другие алгоритмы, хорошие и разные, а так же некоторых высших приматов.

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

            Ну, почему, на русском есть книги. Например:


            Возможно, также, есть в этих книгах, но их сейчас нет под рукой и точно я не уверен:



            За статью спасибо, многим пригодится.
              0
              ключевое слово — простого :)
              В Dragon book'e всё же довольно много математики и формальных определений, да и есть несколько моментов, которые можно оптимизировать с точки зрения программирования. К примеру — в книге предлагается использовать не таблицу переходов, а функцию GOTO, с таким описанием, что я не сразу и въехал что от меня хотят.
              +1
              «Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов.» Мы в свое время в ВУЗе по этой книжке писали для MINI Basic компилятор. В ней настолько все полно описано, хотя в некоторых местах есть ошибки. Но куда уж без них!
                +1
                Покрывает множество языков. То есть если вы придумали язык и описали его, то с большой долей вероятности LR-анализатор его сможет обработать.


                С большой долей вероятности вам придется подпиливать грамматику под тот тип парсера, который вы выбрали. Причем что для LL, что для LR.

                  0
                  Класс грамматик которые обрабатывает LR включает в себя все грамматики, обрабатываемые LL.
                  То есть условия использования LL строже, и значит для LR придётся допиливать куда меньше.
                  А так да, грамматика сложнее Hello World'a (арифметические операции) скорее всего будет нуждаться в доработке, но часто не столь существенной.
                  Само собой это всё сферические кони в вакууме, и без конкретных примеров говорить трудно.
                  +2
                  Синтаксические ошибки обнаруживаются так быстро как это возможно. Сразу же как встречается символ, который не соответствует предыдущему входному потоку, мы можем вывести ошибку об этом.


                  Вот это крайне спорно. Как правило для LR приходится прилагать дополнительные усилия, чтобы ошибки указывались на самый левую лексему ошибочной части.
                    0
                    Жаль, что совсем не упомянуто про packrat.
                      0
                      Эх, без картинок вообще ничего не понятно…
                        0
                        И правда. Автор! «Аааах автора вы мои авторрррра!» О чём это я? Ах да. Обновите, пожалуйста, ссылки на картинки. Без них совсем грустно. Спасибо.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое