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

Статьи к прочтению:

взлом дверной цепочки без следов

Похожие статьи: