6.7.Алгоритм построения множества first(1,a)

Алгоритм строит множества FIRST(1,A) сразу для всех нетерминальных символов грамматики G(VT,VN,P,S), А VN. Для выполнения алгоритма надо пред­варительно преобразовать исходную грамматику G(VT,VN,P,S) в граммати­ку G'(VT,VN',P',S'), не содержащую -правил.

На основании полученной грамматики G' и выполняется построение множеств FIRST(1,A) для всех AVN (если A VN, то согласно алгоритму преобразования также справедливо AVN'). Множества строятся методом последовательно­го приближения. Если в результате преобразования грамматики G в граммати­ку G' множество VN' содержит новый символ S', то при построении множества FIRST(l.A) он не учитывается.

Алгоритм состоит из нескольких шагов.

Шаг 1. Для всех AVN: FIRST₀(1,A) = X | АХ  Р, X (VTVN),  (VTVN)'} (первоначально вносим во множество первых символов для каждого нетерми­нального символа А все символы, стоянию в начале правых частей правил для этого символа A); i:=0.

Шаг 2. Для всех AVN: FIRST_i+1(1,A) = FIRST_i(1,A)  FIRST_i(1,B), для всех не­терминальных символов B (FIRST_i(l,A)  VN).

Шаг 3. Если  AVN: FIRST_i+1(1,A)  FIRST_i(1,A), то i:=i+l и вернуться к шагу 2, иначе перейти к шагу 4.

Шаг 4. Для всех AVN: FIRST(l,A) = FIRST_i,(1,A) \ VN (исключаем из постро­енных множеств все нетерминальные символы).

6.8.Алгоритм построения множества follow(1,a)

Алгоритм строит множества FOLLOW(l,A) сразу для всех нетерминальных символов грамматики G(VT,VN,P,S), AVN. Для выполнения алгоритма предварительно надо построить все множества FIRST(l,A),  AVN. Множества строят­ся методом последовательного приближения. Алгоритм состоит из нескольких шагов.

Шаг 1. Для всех AVN: FOLLOW₀(1,A) = X│В αAXβР, ВÎVN, X (VTVN), β (VTVN)*}, (первоначально вносим во множество последующих символов для каждого нетерминального символа А все символы, которые в правых частях правил встречаются непосредственно за символом A); i:=0.

Шаг 2. FOLLOW₀(l,S) = FOLLOW₀(l,S)  {} (вносим пустую цепочку во мно­жество последующих символов для целевого символа S — это означает, что в конце разбора за целевым символом цепочка кончается, иногда для этой цели используется специальный символ конца цепочки: _K).

Шаг 3. Для всех AÎVN: FOLLOW’_i(l,A) = FOLLOW_i(l,A)  FIRST(1,B), Для всех нетерминальных символов B Î (FOLLOW_i(l,A)  VN).

Шаг 4. Для всех AÎVN: FOLLOW”_i(l,A) = FOLLOW’_i(l,A)  FOLLOW’_i(l,B), для всех нетерминальных символов B Î (FOLLOW’_i(l,A)  VN) и существует пра­вило В→.

Шаг5. Для всех A ÎVN: FOLLOW_i+1(l,A) = FOLLOW’_i(l,A)  FOLLOW’_i(l,B), для всех нетерминальных символов B ÎVN, если существует правило B→αA, α Î(VT  VN)*.

Шаг 6. Если  A ÎVN: FOLLOW_i+1(l,A) ≠ FOLLOW_i(l,A), то i:=i+l и вернуться к шагу 3, иначе перейти к шагу 7.

Шаг 7. Для всех AÎVN: FOLLOW(1,A) = FOLLOW_i(l,A) \ VN (исключаем из построенных множеств все нетерминальные символы).

6.9.Восходящие распознаватели кс-языков без возвратов

6.9.1.Определение lr(k)-грамматики

Восходящие распознаватели выполняют построение дерева вывода снизу вверх. Результатом их работы является правосторонний вывод. Функционирование таких распознавателей основано на модификациях алгоритма «сдвиг-свертка».

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

• что следует выполнять: сдвиг (перенос) или свертку;

• какую цепочку символов  выбрать из стека для выполнения свертки;

• какое правило выбрать для выполнения свертки (в том случае, если сущест­вует несколько правил вида А₁, А₂, .. А_n).

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

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

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

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

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

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

На рис. 6.3 схематично показано частичное дерево вывода для некоторой LR(k)-грамматики. В нем  обозначает уже разобранную часть входной цепочки а, на основе которой построена левая часть дерева у. Правая часть дерева х — это еще не разобранная часть, а А — это нетерминальный символ, к которому на очеред­ном шаге будет свернута цепочка символов z, находящаяся на верхушке стека МП-автомата. В эту цепочку уже входит прочитанная, но еще не разобранная часть входной цепочки . Правая часть дерева х будет построена на основе части входной цепочки . Свойство LR(k) предполагает, что однозначный выбор дей­ствия, выполняемого на каждом шаге алгоритма «сдвиг-свертка», может быть сделан на основе цепочки  и k первых символов цепочки , являющихся частью входной цепочки . Этим очередным действием может быть свертка цепочки z к сим­волу А или перенос первого символа из цепочки  и добавление его к цепочке z.

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

Рассмотрев схему построения дерева вывода для LR(k)-грамматики на рис. 6.3 и сравнив ее с приведенной выше на рис. 6.2 схемой для LL(k)-грамматики, можно предположить, что класс LR-грамматик является более широким, чем класс LL-грамматик. Основанием для такого предположения служит тот факт, что на каждом шаге работы распознавателя LR(k)-грамматики обрабатывается больше информации, чем на шаге работы распознавателя LL(k)-грамматики. Действительно, для принятия решения на каждом шаге алгоритма распознава­ния LL(k)-грамматики используются первые k символов из цепочки , а для принятия решения на шаге распознавания LR(k)-грамматики — вся цепочка  и еще первые k символов из цепочки . Очевидно, что по втором случае можно проанализировать больший объем информации и, таким образом, построить вы­вод для более широкого класса КС-языков.

Приведенное выше довольно нестрогое утверждение имеет строго обоснованное доказательство. Доказано, что класс LR-грамматик является более широким, чем класс LL-грамматик. То есть для каждого КС-языка, заданного LL-грамматикой, может быть построена LR-грамматика, задающая тот же язык, но не на­оборот.

Существуют также языки, заданные LR-грамматиками, для которых не­возможно построить LL-грамматику, задающую тот же язык. Иначе говоря, для всякой LL-грамматики существует эквивалентная ей LR-грамматика, но не для всякой LR-грамматики существует эквивалентная ей LL-грамматика¹.

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

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

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

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

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

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

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

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