Алгоритм Эрли (основные принципы)

Алгоритм Эрли основан на том, что для заданной КС-грамматики G(VT,VN,P,S) и входной цепочки  = а1a2…an, VT*, || = n строится последовательность спис­ков ситуаций I0, I1,..., In. Каждая ситуация, входящая в список Ij, для входной це­почки , представляет собой структуру вида [AX1X2...Xk•Xk+1...Xm,i], k: Xk(VNVT), причем правило AX1...Xmпринадлежит множеству правил Р грамматики G, и 0in, 0km. Символ • (“точка”) – это метасимвол особого вида, который не входит ни во множество терминальных (VN), ни во множест­во нетерминальных (VT) символов грамматики, В ситуации этот символ может стоять в любой позиции, в том числе в начале (•X1...Xm) или в конце (X1…Xm•) всей цепочки символов правила A X1...Xm. Если цепочка символов правила пустая (А), то ситуация будет выглядеть так; [A•,i].

Список ситуаций строится таким образом, что j, 0jn: [Aα•β,i]Ij, тогда и только тогда, если  S*γA, γ *a1...ai, и α*ai+1...aj. Иначе говоря, между вто­рым компонентом ситуации и номером списка, в котором он появляется, заклю­чена часть входной цепочки, выводимая из А. Условия ситуации Ijгарантируют возможность применения правила Аαβ в выводе некоторой входной цепочки, совпадающей с заданной цепочкой  до позиции j.

Условием существования вывода заданной входной цепочки в грамматике G(VN,VT,P,S) после завершения алгоритма Эрли служит [S•,0]In. На осно­вании полученного в результате выполнения алгоритма списка ситуаций можно затем с помощью специальной процедуры построить всю цепочку вывода и по­лучить номера применяемых правил. Причем проще построить правосторонний вывод.

Как и все табличные алгоритмы, алгоритм Эрли обладает полиномиальными характеристиками в зависимости от длины входной цепочки. Доказано, что для произвольной КС-грамматики G(VN,VT,P,S) время выполнения данного алго­ритма Тэбудет иметь кубическую зависимость от длины входной цепочки, а не­обходимый объем памяти Мэ– квадратичную зависимость от длины входной цепочки: α, αVT*, n=|α|: Тэ= О(n3) и Мэ= О(n2). Но для однозначных КС-грамматик алгоритм Эрли имеет лучшие характеристики – его время выполне­ния в этом случае квадратично зависит от длины входной цепочки: Тэ= О(n2). Кроме того, для некоторых классов КС-грамматик время выполнения этого ал­горитма линейно зависит от длины входной цепочки (правда, для этих классов, как правило, существуют более простые алгоритмы распознавания).

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

3.7. Принципы построения распознавателей
КС-языков без возвратов

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

К сожалению, универсальных распознавателей с лучшими характеристиками для КС-языков построить не удается. Среди универсальных распознавателей лучши­ми по эффективности являются табличные.

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

Для многих классов КС-грамматик (и соответствующих им классов КС-языков) можно построить распознаватели, имеющие лучшие характеристики, чем рассмот­ренные выше распознаватели с возвратами и табличные. Эти распознаватели уже не будут универсальными – они будут применимы только к заданному классу КС-языков с соответствующими ограничениями, зато они будут иметь лучшие характеристики.

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

Существуют два принципиально разных класса распознавателей. Первый – нисходящие распознаватели, которые порождают цепочки левостороннего вывода и строят дерево вывода сверху вниз. Второй – восходящие распознаватели, кото­рые порождают цепочки правостороннего вывода и строят дерево вывода снизу вверх. Названия “нисходящие” и “восходящие” связаны с порядком построения дерева вывода. Как правило, все распознаватели читают входную цепочку симво­лов слева направо, поскольку предполагается именно такая нотация в написании исходного текста программ.

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

Восходящие распознаватели используют модификации алгоритма “сдвиг-сверт­ка” (или “перенос-свертка”, что то же самое). При их создании применяются методы, которые позволяют однозначно выбрать между выполнением “сдвига” (“переноса”) или “свертки” на каждом шаге работы расширенного МП-автома­та, а при выполнении свертки однозначно выбрать правило, по которому будет производиться свертка.