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

real Аф, В, C

Хотя это не относится к ситуации

real А, В,

IDLIST

real

IDLIST

real

Допускается также, чтобы правые части более чем одного правила появились в вершине стека, например, в ситуации

real А, Вф, C

ID IDLIST

real

Здесь правильным было бы выполнять приведение с помощью правила (2) и неправильным - с помощью правила (3).

Детерминированный метод разбора снизу вверх предлагает некоторый критерий для выбора решения в случае возникновения подобнтх конфликтов. Так, решение можно принять на основании одного или более предварительно просмотреннтх символов (как в LL-разборе) или на основании информации, имеющейся в стеке разбора. Если считать, что за предложением в вышеприведенном примере следует, например, знак окончания то когда стек содержит

IDLIST

real

решение о сдвиге или приведении посредством правила (1) определяется тем, каким будет предварительно просматриваемый символ: "," или

Некоторые методы разбора снизу вверх, такие, как методы с предшествованием и с ограниченным контекстом [20], могут применяться только к относительно небольшому подмножеству языков. Наиболее универсальным является LR-метод, поскольку он применим ко всем языкам (и грамматикам), разбираемым детерминированно. LR (к) -грамматикой называется грамматика, при использовании которой в качестве основы для анализатора снизу вверх все конфликты типа сдвиг/приведение и приведение/приведение можно разрешать на основании уже

прочитанного текста и фиксированного числа предварительно просматриваемых символов (максимум к). Буква L в LR показывает, что строки читаются слева направо, aR - что получается правосторонний разбор. Теперь нам ясно, что правила, используемые в правостороннем разборе, который обтчно ассоциируется с методом разбора снизу вверх, перечисляются в порядке, обратном порядку при продвижении от начального символа предложения вправо (см. разд. 2.4).

При первоначальном описании LR-разбора [32] этот метод казался довольно громоздким и неэффективным. Однако в последующих работах [1], [16] и др. он стал более привлекательным с практической точки зрения.

5.2. ЬР(1)-ГРАММАТИКИ К ЯЗЫКИ

В предыдущем разделе мы объяснили, что подразумевается под LR(k)-грамматикой. На практике к всегда принимает значение 0 или 1. Рассмотрение множеств даже двух предварительно просматриваемых символов при разрешении конфликтов сделало бы метод крайне громоздким. Более того, мы не смогли бы разбирать никакие другие языки с помощью этого метода, так как можно показать, что любой LR(k)-язык является также LR(1)-языком (т.е. может генерироваться LR(1)-грамматикой) и даже LR(0) - языком, если допустить, что за каждым предложением следует знак окончания ([27], с. 185). Поэтому, хотя и существуют LR(2)-грамматики (но не LR(1))-грамматики, например

(1) SF, S

(2) SF

(3) Fa L

(4) Lt

(5) Lt, L

LR (2)-языков (но не LR (1)-языков) не существует. Этот вариант совершенно не похож на вариант с LL, где, увеличивая значение к, всегда можно (хотя и не всегда практически оправданно) разбирать большее число языков. Грамматика с перечисленными выше порождающими правилами не является LR(1)-грамматикой, так - как после считывания "ведущей" подстроки предложения at, при наличии предварительно просматриваемого символа ",", анализатор не может определить, что выполнять приведение с помощью правила (4) - или сдвиг. Для разрешения конфликта можно воспользоваться двумя предварительно просматриваемыми символами. Например, пара, символов ",t" покажут сдвиг, а пара ",а" - приведение.

Однако по теории должна существовать LR(1)-грамматика, генерирующая тот же язык. Возможно, ею окажется такая грамматика:

Sa t F

F, ITEM F

ITEM t at

Приняв, что "," в грамматике должна появляться только один раз, можно снять признак непринадлежности этой грамматики к классу LR(1). Однако вышеприведенная грамматика показывает, что одних только предварительно

просматриваемых символов не всегда достаточно, чтобы разрешить конфликты. В некоторых случаях нужно также принять во внимание левый контекст. Например, решение о том, нужно ли последовательность

at с предварительно просматриваемым символом ", "

приводить к ITEM или нет, зависит от того, первая это реализация данной последовательности или нет. К счастью, как мы увидим далее, решение о выполнении приведения в LR-разборе, в общем, не требует полного просмотра левого контекста или содержимого стека.

Выше уже упоминалось о том, что LR-метод применим ко всем языкам, которые можно разбирать детерминированно. В частности, все LL(1)-грамматики и языки обладают признаком LR(1). Это объясняется тем, что решение о применении конкретного правила во время LL(l) - разбора базируется на замене нетерминала в сентенциальной форме и одном предварительно просматриваемом символе, в то время как для решения о выполнении приведения в случае LR(l) требуется поместить в стек всю правую часть правила и считать следующий предварительно просматриваемый символ. Таким образом, в случае LR(1) имеется по меньшей мере столько же информации, на которой можно основывать решение о применении конкретного правила, сколько ее имеется в случае LL(1). Это можно показать схематически:

LL(l) точка принятия решения LR(1) точка принятия решения Y аа ip

уаа1р представляет сентенциальную форму, непосредственно после которой в случае LL(1) и непосредственно перед которой в случае LR(1) применяется (допустим)

правило А-аа.

Существуют также грамматики и языки, которые обладают признаком LR(1), но не обладают признаком LL(1). Например, в разд. 5.1 была приведена LR(1)-грамматика, которая не являлась LL(l)-грамматикой. Того, что она содержит левую рекурсию, оказалось достаточно, чтобы она не была LL(1). В LR-разборе левая рекурсия не создает проблем.

Поскольку все языки, которые можно разобрать детерминированно, имеют LR(0)-грамматику, можно было бы, ожидать, что остальную часть главы мы посвятим LR(0)-грамматикам. Однако многие типичные свойства грамматик языков программирования относятся не к LR(0)-свойствам, а скорее к LR(1)-свойствам; так что, рассматривая LR(1)-грамматики, мы, как правило, можем избежать затруднений, связанных с преобразованиями грамматик, которые требуются почти всегда при использовании LL-метода.

Это - положительное качество LR-разбора, особенно если вспомнить о неразрешимости проблемы преобразования грамматик. В отношении же LR-грамматик справедливо следующее:

1. Можно решить, обладает ли грамматика признаком LR(k) для заданного k. В частности, можно решить, является ли грамматика LR(0)- или LR(1)-грамматикой.

2. Нельзя решить, существует ли такое значение k, для которого заданная грамматика будет LR(k)-грамматикой. Этот результат не имеет особого