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

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

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

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

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

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

какое правило выбрать для выполнения свертки (в том случае, если сущест­вует несколько правил вида A₁->a, A₂->a, … A_n->a).

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

В первую очередь можно использовать тот же самый подход, который был поло­жен в основу определения 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-грамматик.

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

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

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

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

Дата добавления: 2014-01-20