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

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

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

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

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

 какое правило выбрать для выполнения свертки (в том случае, если сущест­вует несколько правил вида A1α, A2α,... Аnα).

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

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

КС-грамматика обладает свойством 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-грамматик.

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

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

Можно предположить, что класс 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-грамматики для каждого детерминированного КС-языка играет важную роль – всегда есть смысл в каждом конкретном случае пытаться построить такую грамматику.