Определение LR(k)-грамматики
Восходящие распознаватели выполняют построение дерева вывода снизу вверх. Результатом их работы является правосторонний вывод. Функционирование таких распознавателей основано на модификациях алгоритма “сдвиг-свертка” (или “перенос-свертка”).
Идея состоит в том, чтобы модифицировать этот алгоритм таким образом, чтобы на каждом шаге его работы можно было однозначно дать ответ на следующие вопросы:
что следует выполнять: сдвиг (перенос) или свертку;
какую цепочку символов α выбрать из стека для выполнения свертки;
какое правило выбрать для выполнения свертки (в том случае, если существует несколько правил вида A1α, A2α,... Аnα).
Тогда восходящий алгоритм распознавания цепочек КС-языка не требовал бы выполнения возвратов, поскольку сам язык мог бы быть задан детерминированным расширенным МП-автоматом. Конечно, это нельзя сделать в общем случае, для всех КС-языков (поскольку даже сам класс детерминированных КС-языков более узкий, чем весь класс КС-языков). Но, вероятно, среди всех КС-языков можно выделить такой класс (или классы), для которых подобная реализация распознающего алгоритма станет возможной.
В первую очередь можно использовать тот же самый подход, который был положен в основу определения LL(k)-грамматик. Тогда мы получим другой класс КС-грамматик, который носит название LR(k)-грамматик.
КС-грамматика обладает свойством LR(k), k0, если на каждом шаге вывода для однозначного решения вопроса о выполняемом действии в алгоритме “сдвиг-свертка” (“перенос-свертка”) расширенному МП-автомату достаточно знать содержимое верхней части стека и рассмотреть первые k символов от текущего положения считывающей головки автомата во входной цепочке символов.
Грамматика называется LR(k)-грамматикой, если она обладает свойством LR(k) для некоторого k0.
Название “LR(k)”, как и рассмотренное выше “LL(k)”, также несет определенный смысл. Первая литера “L” также обозначает порядок чтения входной цепочки символов: слева– направо. Вторая литера “R” происходит от слова “right” и, по аналогии с LL(k), означает, что в результате работы распознавателя получается правосторонний вывод. Вместо “k” в названии грамматики стоит число, которое показывает, сколько символов входной цепочки надо рассмотреть, чтобы принять решение о действии на каждом шаге алгоритма “сдвиг-свертка”. Так, существуют LR(0)-грамматики, LR(1)-грамматики и другие классы.
В совокупности все LR(k)-грамматики для всех k0 образуют класс 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-грамматики для каждого детерминированного КС-языка играет важную роль – всегда есть смысл в каждом конкретном случае пытаться построить такую грамматику.