part31

Пред.Страница След.Страница Раздел Содержание

3.4. Нисходящие распознаватели, LL(K) и разделенные грамматики. Построение распознавателя.

Распознаватели и LL(K) - грамматики

Моделирование работы недетерминированных магазинных распознавателей связано с поиском последовательности переходов из начального в одно из конечных состояний. Поиск состоит из отдельных шагов, каждый из которых может окончиться неудачно и привести к возврату в исходное состояние для выполнения следующего шага. Такой поиск с возвратом связан со значительными затратами времени, поэтому на практике используют более экономичные детерминированные распознаватели, работающие без возвратов. Эти распознаватели допускают только ограниченные классы КС-языков, которые однако отражают все синтаксические черты языков программирования.
Распознаватели можно разделить на две категории: нисходящие и восходящие. Каждая категория характеризуется порядком, в котором располагаются правила в дереве вывода. Нисходящие распознаватели обрабатывают правила сверху вниз, верхние правила раньше нижних, в то время как восходящие анализаторы используют нижние правила раньше тех, что расположены выше. Чтобы показать возможности детерминированных автоматов и способы их построения, в настоящем разделе рассматриваются нисходящие распознаватели, допускающие языки, порождаемые грамматиками вида LL(K).

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

Название LL произошло от слова Left, поскольку анализатор просматривает входную цепочку слева-направо , и слова Leftmost, поскольку он обнаруживает появление правила по одному или группе символов, образующих левый край цепочки. На практике наибольшее применение имеет класс LL(1) грамматик, для которых детерминированный распознаватель работает по дному входному символу, расположенному в текущей позиции. В качестве первого шага изучения нисходящих распознавателей рассмотрим их построение для одного из подклассов LL(1) грамматик.

Разделенные грамматики

Определение. Контекстно-свободная грамматика, не содержащая аннулирующих правил,
называется разделенной или простой , если выполняются следующие два условия:

1. Правая часть каждого правила начинается терминалом.
2. Если два правила имеют одинаковые левые части, то правые части этих правил
должны начинаться различными терминальными символами.

Например, следующая грамматика, заданная схемой:

Г_3.4: R = { ® ab,

 ® bb,
  ®a,
  ®b},

является разделенной грамматикой, т.к. выполняются условия (1) и (2).
С другой стороны, грамматика

Г_{3. 5}: R = { (1)  ® a

(2)  ®  b
 (3)  ® b
 (4)  ® ba } ,

не является разделенной грамматикой, т.к. в правиле (2) нарушается условие (1), а в правилах (3) и (4) - условие (2).
Важным свойством разделенных грамматик является то, что для каждой из них можно построить детерминированный нисходящий распознаватель.

Построение детерминированного нисходящего распознавателя.

Способ построения распознавателя предусматривает сопоставление каждому правилу грамматики команды распознавателя .
Согласно общему способу построения распознавателей для КС-грамматик, описанному в предыдущем разделе, каждому правилу разделенной грамматики, которые имеют вид:
<A> ® a a , где a - цепочка символов полного словаря и a принадлежит
терминальному словарю, нужно поставить в соответствие команду

(*) f ⁰( s₀ , e , <A> ) = ( s₀ , a ' a) ,

которая задает такт работы без сдвига входной головки и в которой a ' представляет собой зеркальное отображение цепочки a . Отметим, что в результате выполнения этой команды, в вершине магазина окажется терминал a. Общий способ построения редусматривает также построение для каждого a символа грамматики команды:

(**) f ( s₀ , a , a ) = ( s₀ , $ )

которая удаляет этот терминал из магазина и сдвигает входную головку.
Учитывая, что в разделенной грамматике каждое правило начинается с терминального символа, и что эти терминалы не повторяются, можно сделать вывод о том , что команда (*) должна выполняться только в том случае, когда под входной головкой находится терминал a, и после нее всегда должна выполняться команда (**).
Чтобы исключить неопределенность правил вида (*) и уменьшить число тактов работы распознавателя, объединим команды вида (*) и (**) в одну команду. Построение такой команды должно выполняться следующим образом: каждому правилу разделенной грамматики <A> ® a a поставим в соответствие команду

f ( s₀ , a , <A>) = ( s₀ , a ') ,

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

f ( s₀ , b , b ) = ( s₀ , $ )

Для перехода в заключительное состояние добавим правило:

f ( s₀ , $ ,h₀ ) = ( s₁ , $ ) ,

а в качестве начальной конфигурации распознавателя примем, как
обычно, следующее выражение :

( s₀ , a , h₀ ) ,

где  - начальный символ грамматики, а a - заданная входная цепочка.

Применяя приведенные выше правила, построим распознаватель для разделенной грамматики
Г_{3. 4} . В результате получаем:

М _3.1 : P = { a , b }, H = { a , b , , , h₀ }, S = {s₀}, F= {s₀},

f ( s₀ , a , ) = ( s₀ , b )
f ( s₀ , a , ) = ( s₀ , $ )
f ( s₀ , b , ) = ( s₀ , b )
f ( s₀ , b , ) = ( s₀ , )
f ( s₀ , b , b ) = ( s₀ , $ )
f ( s₀ , e , h₀ ) = ( s₀ , $ )

Работу построенного автомата покажем на примере анализа цепочки bbabab.

( s₀ , bbababa , h₀ ) |--- ( s₀ , bababa , h₀b ) |---

( s₀ , ababa , h₀b ) |--- ( s₀ , baba , h₀b ) |---

( s₀ , aba , h₀ ) |--- ( s₀ , ba , h₀b ) |--- ( s₀ , a , h₀ )

|--- ( s₀ , $ , h₀ ) |--- ( s₀ , $ , $ ) .

Приведенная последовательность конфигураций показывает, что в каждой конфигурации может быть применена единственная команда детерминированного распознавателя.