Алгоритм Эрли основан на том, что для заданной КС-грамматики G(VT,VN,P,S) и входной цепочки = а1a2…an, VT*, || = n строится последовательность списков ситуаций I0, I1,..., In. Каждая ситуация, входящая в список Ij, для входной цепочки , представляет собой структуру вида [AX1X2...Xk•Xk+1...Xm,i], k: Xk(VNVT), причем правило AX1...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ледует всегда помнить, что проблема преобразования КС-грамматик алгоритмически неразрешима. Если какая-то грамматика не принадлежит к требуемому классу КС-грамматик, это еще не значит, что заданный ею язык не может быть описан грамматикой такого класса. Иногда удается выполнить преобразования и привести исходную грамматику к требуемому виду. Но, к сожалению, этот процесс не формализован, не поддается алгоритмизации и требует участия человека. Чаще всего такую работу вынужден выполнять разработчик компилятора (правда, выполняется она только один раз для синтаксических конструкций каждого языка программирования).
Существуют два принципиально разных класса распознавателей. Первый – нисходящие распознаватели, которые порождают цепочки левостороннего вывода и строят дерево вывода сверху вниз. Второй – восходящие распознаватели, которые порождают цепочки правостороннего вывода и строят дерево вывода снизу вверх. Названия “нисходящие” и “восходящие” связаны с порядком построения дерева вывода. Как правило, все распознаватели читают входную цепочку символов слева направо, поскольку предполагается именно такая нотация в написании исходного текста программ.
Нисходящие распознаватели используют модификации алгоритма с подбором альтернатив. При их создании применяются методы, которые позволяют однозначно выбрать одну и только одну альтернативу на каждом шаге работы МП-автомата (шаг “выброс” в этом автомате всегда выполняется однозначно).
Восходящие распознаватели используют модификации алгоритма “сдвиг-свертка” (или “перенос-свертка”, что то же самое). При их создании применяются методы, которые позволяют однозначно выбрать между выполнением “сдвига” (“переноса”) или “свертки” на каждом шаге работы расширенного МП-автомата, а при выполнении свертки однозначно выбрать правило, по которому будет производиться свертка.
