бы сразу опробовать алгоритм LR(1), но в подавляющем большинстве случаев на это ушло бы гораздо больше времени, чем на опробование сначала более просттх алгоритмов. Типичный генератор LR(1)-анализаторов действует, опробуя различные алгоритмы в порядке возрастания их сложности. Грамматики языков программирования часто имеют признак SLR(l) и почти всегда признак LALR(l).

Отдельный класс грамматик, не обладающих признаком LR(1), составляют неоднозначные грамматики (см. разд. 2.4). Задача определения, однозначна ли грамматика или нет, неразрешима. Тем не менее, поскольку ни одна из LR(1)-грамматик не является неоднозначной, LR(1)-алгоритм может показать нам, что данная грамматика однозначна. Однако отсюда не следует, что отказ LR(1)-алгоритма свидетельствует о неоднозначности грамматики. Иначе мы могли бы проверить неоднозначность грамматики, что противоречило бы неразрешимости проблемы.

Рассмотренные выше прямоугольные таблицы разбора позволяют осуществлять быструю выборку и обеспечивают широкие диагностические возможности (так как каждый элемент - пробел можно ассоциировать с различными сообщениями об ошибках). Однако эти таблицы занимают слишком большой объем памяти (до 50 К слов для синтаксиса Алгола 68). Существуют хорошо известные методы записи в память неплотных матриц, и многие из них можно применить к LR-таблицам разбора. Кроме того, есть и другие эффективные методы хранения таблиц, которые учитывают их конкретные свойства [28]. Однако, как и следовало ожидать, чем-то приходится поступиться ради более эффективного использования объема памяти. Это может быть время обращения к определенному элементу таблицы разбора или даже более позднее обнаружение синтаксических ошибок (в том смысле, что анализатор успеет выполнить больше действий, прежде чем обнаружится ошибка, а не в том, что будет считано большее число символов программы).

5.5 СРАВНЕНИЕ LL- и LR-МЕТОДОВ РАЗБОРА

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

Если кто-либо для преобразования контекстно-свободной грамматики для Алгола 68 по пересмотренному сообщению воспользуется хорошим преобразователем грамматики, то из опыта можем сказать, что только несколько частей грамматики окажутся трудными для преобразования и их придется преобразовывать вручную.

Приведем три примера тех средств грамматики, которые вызвали у нас затруднения (подробнее об этом см. в [31]).

1. Допустим, в грамматике G1 есть правила:

scoIcl

CO orb EC stick SC stick SC crb ECu semi EC\u CLorb SC crb SCPLU semi SC\PLU

PLUlab PLU\u

{CO - условное предложение, CL - замкнутое предложение, ЕС - вхясняющее предложение, SC - последовательное предложение, PLU - "возможно помеченный элемент", u - элемент, orb - открывающая круглая скобка и т. д.}

Проблема возникает в связи с тем, что элементы не могут иметь меток в вгясняющем предложении (появляющемся в условном предложении), но могут их иметь в последовательном предложении (появляющемся в замкнутом предложении), а преобразователь грамматики с этим не может справиться. Данный язык тем не менее обладает признаком LL(1), но нужно "слить воедино" правила для замкнуттх и условных предложений, чтобы получить LL(1)-грамматику G2 с правилами

Sоrb Т

Т1аЬ У\\. u W

Vlab У\\. uX

crb\ semi Т\ stick SC stick SC crb

Xsemi V\crb

SCPLU Y

Ysemi PLU У\е

PLU lab PLU\u Грамматика G2 будет LL(1)-грамматикой.

2. Предположим, что грамматика G3, которая, если придать ей несколько обобщеннтй характер, генерирует фактические описатели структур на Алголе 68, имеет правила:

STRAD struct FPACK

FPACK orb FIELDS crb

FIELDS FIELD comma FIELDS\FIELD

FIELDS ad LIST

LIST tag\tag comma LIST Здесь опять наш преобразователь грамматики не может выдать LL(1)-грамматику. Проблема заключается в двойном использовании запятой, а грамматика аналогична приведенной в начале разд. 5.2 (а также в разд. 4.4). Преобразование вручную, подобное вышеописанному, дает LL(1)-грамматику.

3. Другая часть грамматики Алгола 68, которая трудна для преобразования в LL(1)-форму, касается форматов. Например, включение определяется следующим образом (грамматика G4):

INSERT LIT ALIGNS\ALIGNS\LIT LITREPL denote LIT1\REPL denote REPLnerepl\e

LIT1 -> nerepl denote\nerepl denote LIT1 ALIGNS MALIGN ALIGNS\ALIGN ALIGN-REPL code LIT\REPL code {INSERT - вставка, ALIGN - размещение, LIT - литерал, REPL -

повторитель, nerepl - непустой повторитель, denote - обозначение и т.д.} G4 можно

вручную преобразовать в LL(1)-форму (G5):

INSERT- nerepl ANER\denote ADEN\code ACODE ANER- denote ADEN\code ACODE ADEN- nerepl ANER\code ACODE\e ACODE-INSERT\e.

Три грамматики G1, G3 и G4 представляют три принципиальнтх случая, где преобразователь грамматик не смог преобразовать нашу грамматику Алгола 68 в LL(1)-форму. Интересно поэтому выяснить, являются ли эти грамматики LR{1)-грамматиками.

Грамматика G1 не обладает признаком LR(I), так как при чтении СТРОКИ

с semi в качестве предварительно просматриваемого символа не известно, выполнять ли приведение к РLU с помощью второго варианта для PLU или сдвиг в соответствии с первым вариантом для ЕС. Так что здесь имеет место неразрешимый конфликт сдвиг/приведение.

Грамматика G3 не обладает признаком LR(1), потому что при чтении строки

struct (ad tag

с предварительно просматриваемым символом comma не известно, выполнять ли приведение к LIST, как в первом варианте для LIST, или сдвиг, как во втором варианте. Опять мы имеем дело с неразрешимым конфликтом сдвиг/приведение.

Грамматика G4 также не обладает признаком LR(1), поскольку при чтении строки

Code

с предварительно просматриваемым символом nerepl не известно, выполнять ли приведение с помощью второго варианта для ALIGN или сдвиг в соответствии с первым вариантом. Мы вновь сталкиваемся с конфликтом сдвиг/приведение.

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

Существуют серьезные причины, по которым мы хотим избежать преобразований вручную, если это возможно: во-первтх, трудно выбрать вид преобразования, во-втортх, мы не всегда можем гарантировать, что они не изменят генерируемый язык.

Эти два метода разбора можно также сравнивать в отношении размеров таблиц и времени разбора. Использование по одному слову на элемент таблицы LL-разбора позволяет свести размер типичной таблицы разбора для Алгола 68 примерно к 4К слов. Соответствующий размер таблицы LR-разбора, описаннтй в разд. 5.3, составляет примерно 50 К слов. Однако такое сравнение не совсем справедливо, поскольку применение методов оптимизации, упоминаемых в последнем разделе,