LL (n) распознаватели. Алгоритм разбора

Суще­ствует класс грамматик, основанный на выборе одной альтернативы из множества возможных на основе нескольких очередных симво­лов в цепочке. Это так называемые LL(k)-грамматики.

Грамматика обладает свойством LL(k), k > 0, если на каждом шаге вывода для однозначного выбора очередной альтернативы МП-автомату достаточно знать символ на верхушке стека и рассмотреть первые k символов от текущего поло­жения считывающей головки во входной цепочке символов.

Грамматика называется LL(k)-грамматикой, если она обладает свойством LL(k) для некоторого k > 0.

Название «LL(k)» несет определенный смысл. Первая литера «L» происходит от слова «left» и означает, что входная цепочка символов читается в направлении слева направо. Вторая литера «L» также происходит от слова «left» и означает, что при работе распознавателя используется левосторонний вывод. Вместо «k» в названии класса грамматики стоит некоторое число, которое показывает, сколь­ко символов надо рассмотреть, чтобы однозначно выбрать одну из множества аль­тернатив. Так, существуют LL(1)-грамматики, LL(2)-грамматики и другие классы. Очевидно, что LL(0)-грамматика бессмысленна, т.к. этом случае разбор вообще не зависит от входной цепочки.

В совокупности все LL(k)-грамматики для всех k>0 образуют класс LL-грамматик.

На рис.8.1 схематично показано частичное дерево вывода для некоторой LL(k)-грамматики. В нем w обозначает уже разобранную часть входной цепочки a, ко­торая построена на основе левой части дерева y. Правая часть дерева х — это еще не разобранная часть, а А — текущий нетерминальный символ на верхушке стека МП-автомата. Цепочка х представляет собой незавершенную часть цепочки вы­вода, содержащую как терминальные, так и нетерминальные символы. После за­вершения вывода символ А раскрывается в часть входной цепочки u, а правая часть дерева х преобразуется в часть входной цепочки t. Свойство LL(k) предпо­лагает, что однозначный выбор альтернативы для символа А может быть сделан на основе k первых символов цепочки ut, являющейся частью входной цепоч­ки a.

Алгоритм разбора входных цепочек для LL(k)-грамматики носит название «k-предсказывающего алгоритма». Принципы его выполнения во многом соответст­вуют функционированию МП-автомата с той разницей, что на каждом шаге работы этот алгоритм может просматривать k символов вперед от текущего поло­жения считывающей головки автомата.

Рис. 8.1. Схема построения дерева вывода для LL(k)-грамматики

Для LL(k)-грамматик известны следующие полезные свойства:

всякая LL(k)-грамматика для любого k>0 является однозначной;

существует алгоритм, позволяющий проверить, является ли заданная грамма­тика LL(k)-грамматикой для строго определенного числа k.

Кроме того, известно, что все грамматики, допускающие разбор по методу рекур­сивного спуска, являются подклассом LL(1)-грамматик. То есть любая грамма­тика, допускающая разбор по методу рекурсивного спуска, является LL(1)-грамматикой (но не наоборот!).

Есть, однако, неразрешимые проблемы для произвольных КС-грамматик:

не существует алгоритма, который бы мог проверить, является ли заданная КС-грамматика LL(k)-грамматикой для некоторого произвольного числа k;

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

Это несколько ограничивает применимость LL(k)-грамматик, поскольку не все­гда для произвольной КС-грамматики можно очевидно найти число k, для кото­рого она является LL(k)-грамматикой, или узнать, существует ли вообще для нее такое число k.

Для LL(k)-грамматики при k>1 совсем не обязательно, чтобы все правые части правил грамматики для каждого нетерминального символа начинались с k различ­ных терминальных символов.

Для LL(1)-грамматики, очевидно, для каждого нетерминального символа не мо­жет быть двух правил, начинающихся с одного и того же терминального симво­ла. Однако это менее жесткое условие, чем то, которое накладывает распознава­тель по методу рекурсивного спуска, поскольку в принципе LL(1)-грамматика допускает в правой части правил цепочки, начинающиеся с нетерминальных символов, а также l-правила.

Поскольку все LL(k)-грамматики используют левосторонний нисходящий рас­познаватель, основанный на алгоритме с подбором альтернатив, очевидно, что они не могут допускать левую рекурсию. Поэтому никакая леворекурсивная грам­матика не может быть LL-грамматикой. Следовательно, первым делом при по­пытке преобразовать грамматику к виду LL-грамматики необходимо устранить в ней левую рекурсию (соответствующий алгоритм был рассмотрен выше).

Класс LL-грамматик широк, но все же он недостаточен для того, чтобы покрыть все возможные синтаксические конструкции в языках программирования (к ним относим все детерминированные КС-языки). Известно, что существуют детер­минированные КС-языки, которые не могут быть заданы LL(k)-грамматикой ни для каких k. Однако LL-грамматики удобны для использования, поскольку по­зволяют построить распознаватели с линейными характеристиками (линейной зависимостью требуемых для работы алгоритма распознавания вычислительных ресурсов от длины входной цепочки символов).

Принципы построения распознавателей для LL(k)-грамматик

Для построения распознавателей LL(k)-грамматик используются два важных мно­жества, определяемые следующим образом:

FIRST(k, a) — множество терминальных цепочек, выводимых из aÎ(VTÈVN)*, укороченных до k символов;

FOLLOW(k, A) — множество укороченных до k символов терминальных це­почек, которые могут следовать непосредственно за AÎVN в цепочках вывода

Формально эти два множества могут быть определены следующим образом:

FIRST(k, a) = {wÎVT* | либо |w| £ k и a Þ* w, либо |w|>k и a Þ* wх, xÎ(VTÈVN)*}, aÎ(VTÈVN)*, k>0.

FOLLOW(k,A) = {wÎVT* | SÞ*aAg и wÎFIRST(k, g), aÎVT*}, AÎVN, k>0.

Очевидно, что если имеется цепочка терминальных символов aÎVT*, то FIRST(k,a) — это первые k символов цепочки a.

Доказано, что грамматика G(VT,VN,P,S) является LL(k )-грамматикой тогда и только тогда, когда выполняется следующее условие: " А®b Î Р и " А®g Î Р (b¹g): FIRST(k,bw)) Ç FIRST(k,gw)) = Æ для всех цепочек w таких, что S Þ* aAw.

Иначе говоря, если существуют две цепочки вывода:

S Þ* aAg Þ azg Þ* aw

S Þ* aAg Þ atg Þ* au

то из условия FIRST(k, w) = FIRST(k, u) следует, что z = t.

На основе этих двух множеств строится алгоритм работы распознавателя для LL(k)-грамматик, который представляет собой k-предсказывающий алгоритм для МП-автомата, заданного так: R({q},VT,Z,d,q,S,{q}), где Z = VTÈVN, a S - целевой символ грамматики G. Функция переходов автомата строится на основе управ­ляющей таблицы М, которая отображает множество (ZÈ{l}) x VT* на множест­во, состоящее из следующих элементов:

пар вида (b,i), где b — цепочка символов, помещаемая автоматом на верхушку стека, a i — номер правила вида А®b, AÎVN, bÎZ*;

«выброс»;

«допуск»;

«ошибка».

Конфигурацию распознавателя можно отобразить в виде конфигурации МП-автомата с дополнением цепочки p, в которую помещаются номера применен­ных правил. Поскольку автомат имеет только одно состояние, его в конфигура­ции можно не указывать. Если считать, что Х — это символ на верхушке стека автомата, a — непрочитанная автоматом часть входной цепочки символов, a u = FIRST(k,a), то работу алгоритма распознавателя можно представить сле­дующим образом:

(a, Хg, p) ¸ (a, bg, pi), gÎZ*, если М(Х,u) = (b,i);

(a, Хg, p) ¸ (a', g, p), если Х = a Î VT и a = аa', M(a,u) = «выброс»;

(l, l, p) — завершение работы, при этом М(l, l) - «допуск»;

иначе — «ошибка».

Цепочка u = FIRST(k, a) носит в работе автомата название «аванцепочка».

Таким образом, для создания алгоритма распознавателя языка, заданного произ­вольной LL(k)-грамматикой, достаточно уметь построить управляющую табли­цу М. Управляющую таблицу М, а также множества FIRST и FOLLOW можно получить на основе правил исходной грамматики.

Не нашли, что искали? Воспользуйтесь поиском по сайту: