Оба множества направляющих символов для двух вариантов Р содержат s, и, пытаясь «вынести s за скобки», мы замещаем Q и R в правых частях правил 1 и 2:

P->sQmx P->qx P->sRny P->ry

Эти правила можно заменить следующими:

P->qx

P->ry

P->sP1

P1->Qmx

P1->Rny

Правила для Р1 аналогичны первоначальным правилам для Р и имеют пересекающиеся множества направляющих символов. Мы можем преобразовать эти правила так же, как и правила для Р:

P1->sQmmx

P1->qmx

P1->sRnny

P1->rny

Факторизуя, получаем

P1->qmx P1->rny P2->Qmmx P2->Rnny

Правило для Р2 аналогично правилам для P1 и Р, но длиннее их, и теперь нам уже очевидно, что этот процесс бесконечный. Все попытки преобразовать грамматику в Ы(1)-форму с помощью какого-либо алгоритма при некоторых входах обречены на неудачу (или зацикливание). Чем замысловатее (и сложнее) алгоритм, тем больше случаев он может охватить, однако всегда найдутся какие-либо входы, с которыми он потерпит поражение. Как же тогда разработчик компилятора найдет Ы(1)-грамматику, на которой он будет базировать свой синтаксический анализатор для компилируемого языка? Вероятно, ему придется воспользоваться каким-нибудь (несовершенным) средством преобразования имеющейся у него грамматики. Примером такого средства служит SID (схема улучшения синтаксиса) Фостера [19]. Хотя SID и «несовершенен», он стал неоценимым для многих разработчиков компиляторов (включая автора) в Великобритании и других странах благодаря своей способности преобразовывать множество грамматик в LL(l)-фopмy.

Возникает вопрос, что же делать разработчику компиляторов, если его преобразователь грамматики не может выдать Ы(1)-грамматику? В этом случае он должен попытаться определить на основании выхода преобразователя, какая часть грамматики не поддается преобразованию, и либо преобразовать эту часть вручную в Ы(1)-форму, либо переписать ее так, чтобы преобразователь грамматики смог с ней совладать. Это возможно при условии, что используется ЬЬ(1)-язык. Если данное условие не выполняется, то синтаксический анализатор LL(1) нельзя получить, не изменив реализуемый язык. Выход преобразователя может указать, почему язык не является LL(1)-языком.

С точки зрения пользователя, применение типичного преобразователя грамматики может привести к ччетырем ситуациям в зависимости от того, является ли язык LL(1)-языком или нет и достаточно ли «умен» преобразователь, чтобы выполнить «правильное» действие для заданного входа, т. е. преобразовать грамматику в LL(1)-форму,если это возможно, или выдать соответствующее диагностическое сообщение в противном случае. Эти ситуации схематически представлены в табл. 4.11.

Таблица 4.11

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

Что касается такого языка, как Алгол 68, то его синтаксис не должен представлять особых трудностей для хорошего преобразователя. Так, у одного преобразователя вызвал затруднение следующий случай, показанный на примере части синтаксиса для фактического описателя структуры: STRAD->struct orb LIST crb LIST->EL

LIST->EL comma LIST EL->ad FIELDS FIELDS->tag

FIELDS->tag comma FIELDS где ad может быть real или int, tag служит идентификатором, a orb и crb обозначают литеры «(» и «)» соответственно. Типичная генерируемая строка: struct (int a, b, real x, у) Проблема заключается в двойном употреблении запятой (для разделения двух ЕL. и двух tag). Этот синтаксис можно переписать таким образом, чтобы генерировался тот же язык, а запятая появлялась в правилах только один раз:

STRAD->struct orb LIST crb LIST->ad tag TAIL TAIL->comma ITEM TAIL ->e

ITEM->-ad tag ->tag

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

открывающих круглых скобок и некоторые аспекты форматов (см. разд. 5.5). Если контекстно-свободная грамматика для Алгола 68 (или, по меньшей мере, ее контекстно-свободные варианты) берется из пересмотренного сообщения, то с помощью нескольких простых преобразований вручную, подобных вышеописанному, хороший преобразователь грамматики выдаст LL(1)-грамматику для языка, на котором можно базировать синтаксический анализатор. Следует отметить, что почти все проблемы по разбору Алгола 68 (какой бы метод ни применялся) возникают в результате перегрузки символов, в основном открывающей круглой скобкой и запятой. 4.5. LL(1)-ТАБЛИЦЫ РАЗБОРА

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

Опишем сначала возможный вид таблицы разбора, довольно простой и понятный, а затем рассмотрим способы ее оптимизации относительно объема и т. д.

Таблица разбора представляется как одномерный массив структур: mode parsel = struct (list terminals, int jump, bool accept, stack, return, error)

mode list = struct (string term, ref list next) Сама таблица описывается как [1 : ptsize] parsel pt Нам также нужен стек для адресов возврата и указатель стека:

flex [0: 25] int stack int Sptr := 0;

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

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

2. Проверка терминала, появляющегося в правой части порождающего правила.

3. Проверка нетерминала. Она заключается в проверке нахождения предварительно просматриваемого символа в одном из множеств направляющих символов для данного нетерминала, помещении в стек