4.1. Разбор сверху вниз

Теперь продемонстрируем перебор всех вариантов с указанием для каждого этапа остатка предложения и остатка структуры, но без указания полученного разбора.

а-\-ЬХс

ЬХс ЬХс

ЬХс

S Т

T + S ид

ud + S ид XT udXT + S

-ibXc

+ S XT

XT + S

T + S ид

идХТ ид + S идХТ + S

XT + S

XT + S T

T + S ид

ид XT ud + S udXT + S

XT + S

XT + S

На последнем этапе оба остатка пусты, что соответствует представлению правильного разбора.

Алгоритм разбора сверху вниз приведен в приложении 2.

4.2. АПРИОРНЫЕ КРИТЕРИИ ДЛЯ ГРАММАТИЧЕСКОГО РАЗБОРА СВЕРХУ ВНИЗ

Метод разбора сверху вниз имеет один существенный недостаток. Рассмотрим грамматику

S->T\S+T

Т-*ид\ТХид

и попытаемся выполнить соответствующий ей разбор предложения, рассмотренного в разд. 4.1. Последовательные подстановки будут давать

т

т+т

S + T+T

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

Г->Га

Грейбах [35] показал, что всегда можно преобразовать любую грамматику в эквивалентную ей грамматику без рекурсии слева. Эквивалентной называется грамматика, которая определяет те же предложения, содержит такие же двусмысленности ), но порождает для данного предложения другой грамматический разбор. В гл. 6 обсуждаются такие эквивалентные преобразования грамматик, а также проблемы, связанные с получением для преобразованной грамматики правильного разбора.

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

) Если они есть. - Прим. перев.

4.2. Априорные критерии для грамматического разбора сверху вниз 27

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

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

Построить такую матрицу нетрудно. Предположим, что в начале мы имеем матрицу соответствия слов и классов классам; эта матрица указывает те слова и классы, с которых начинаются правила подстановки, соответствующие классам. Например, для грамматики

S-a\ ТЬ T->c\Td

получаем

S Т а b с d SO 1 10 0 0 ГО 10 0 10

Это означает, что S начинается с Т или а и что Т начинается с Т или с.

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

S Т а b с d 5 0 110 10 ГО 10 0 10

) Эта процедура представляет собой обобщение операции построения транзитивного замыкания. Если исключить из рассмотрения столбцы, соответствующие словам, 10 для оставшейся квадратной матрицы строится обычное транзитивное замыкание. - Прим. перев.

4. Универсальные методы грамматического разбора

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

S-*T\T + S Т-*ид\идХТ

порождает

S-*udludXT\ud + S\udXT + S Т-*ид\идХТ

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

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

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

4.4. Априорные критерии для анализа снизу вверх

Может оказаться также, что последовательность слов не соответствует остатку разбора. Не менее желательно, чтобы мы не занимались многократно установлением этого факта. Позволяющий избежать повторений при анализе метод, ориентированный на естественные языки, описан в статье [25].

4.3. ГРАММАТИЧЕСКИЙ РАЗБОР СНИЗУ ВВЕРХ

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

S-*T\T-\-S

Т-*ид\идХТ

мы можем анализировать предложение, выполняя следующие последовательные шаги:

а + ЬХс ид + идХ ид

ид + идХТ Т->ид

Т + идХТ Т->ид

Т+Т Т-*идХТ

T + S 5->Г

S S-*T + S

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

4.4. АПРИОРНЫЕ КРИТЕРИИ ДЛЯ АНАЛИЗА СНИЗУ ВВЕРХ

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

Г + 6 X с

Т + 1Уд X с

Т + ид X ид

Т + ид X Т

Т+Т

Т + S

Т

ид ид

в + 6 X с S

т

т

ид ид

Т

о + * X с

г

Г

Т

4.4. Априорные критерии для анализа снизу вверх. 31

Рассмотрим Предыдущий пример на этапе

а 4- 6 X с

Имеет смысл применять только те правила подстановки, которые начинаются с ид. Каждое такое правило подстановки является частью определения промежуточного класса. Если с этого класса не может начинаться предложение, то ни к чему применять соответствующее правило подстановки. В данном случае применимы два правила подстановки

Т-*ид Т~*идХТ

и, поскольку S может начинаться с Т, следует попытаться применить оба. Применение второго правила подстановки оказывается неудачным, остается конструкция

Т + ЬХс

Опять применимы два правила подстановки, на этот раз

S-*T S-*T + S

и следует испробовать оба. Применение первого приводит к неудаче. Теперь мы знаем, что разбор имеет следующий вид:

г

i

а + Ь X с

И поэтому остаток должен начинаться с 5. Следовательно, к началу фразы 6 X применимы только правила подстановки, описывающие такие классы, с которых может начинаться S.

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

а + b X с

Р Q R

1 b с d е f

ид + Ь X с

а + Ь X с

Т

а + Ь X с

Т

ид ид I I

а + b X с

Т

ид ид ид

I I I а + 6 X с

Г Г

ид ид ид

I I I а + Ь X с

Т

4. Универсальные методы грамматического разбора

и далее мы применяем только правила подстановки, описывающие такие классы, с которых может начинаться Q.

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

Рассмотрим работу этого алгоритма при разборе предложения а -{- Ь X с применительно к грамматике

T\S + T ид\ ТХид

и покажем, что рекурсия слева не вызывает осложнений. Приводятся все варианты, ио построение дерева разбора не рассматривается.

ПРЕДЛОЖЕНИЕ

а + ЬХс а + ЬХс

ЦЕЛЬ (S),S

{ид),Т (S),S

ПРАВИЛО ПОДСТАНОВКИ

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

ПРЕДЛОЖЕНИЕ ЦЕЛЬ ПРАВИЛО ПОДСТАНОВКИ

Л-ЬХс ПУСТО, Т (S),S -

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

ПРЕДЛОЖЕНИЕ + ЬХс

{х,ид),Т {S),S ПУСТО, S(S),S

ПРАВИЛО ПОДСТАНОВКИ Т-*ТХид

т->т

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

4.5. Общая программа грам.ттического разбора

дится. Развивая второй вариант, мы получаем

ПРЕДЛОЖЕНИЕ ЦЕЛЬ ПРАВИЛА ПОДСТАНОВКИ

-\-bXc

{+,T),S (S),S SS + T

Первый из этих вариантов означал бы завершение разбора и поэтому не пригоден.

ПРЕДЛОЖЕНИЕ ЦЕЛЬ

ЬХс ЬХс Хс Хс

ПРАВИЛА ПОДСТАНОВКИ

(S),S

{ид),Т {T},S (5),5 Т-ид

ПУСТО,г {T),S (S),S -

(-f, T),S {S),S S-*S+T

(X, ud),T (T),S (S),S T-TXud с {ud)J{T),S (S),S

- ПУСТО,/-(r),S (S),S -

- (+, r),S{S),S S-*S+T {X, ud),T{T),S S.{S) TTXud

Первая из трех последних подстановок приводит к правильному разбору, остальные оказываются непригодными.

4.5. ОБЩАЯ ПРОГРАММА ГРАММАТИЧЕСКОГО РАЗБОРА

Ангер [32] описал некоторый алгоритм грамматического разбора, основанный на методе анализа сверху вниз с применением ряда априорных критериев. Для работы этого алгоритма требуется, чтобы в памяти находилось все предложение.

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

Предположим, что последовательность слов

abcdefg

должна быть сопоставлена с правилом подстановки

р -* aQdeR

Согласование возможно, только если be выводимо из Q и fg выводимо из R. Алгоритм состоит в следующем. Нам задаются последовательность слов а и правило подстановки р, и мы хотим показать их совместимость. Правая часть правила подстановки может содержать некоторые слова. Проверяем последовательность а, чтобы убедиться, что эти слова встречаются в правильном порядке. Если это не так, то данный разбор не проходит. Если же это условие выполнено, то по очереди выделяем различные способы разбора (если все они должны быть перечислены). Фрагменты последовательности а, заключенные между опорными словами, должны быть выведены из тех классов, которые встречаются в р между соответствующими словами. При этом мы снова имеем дело с сегментами, которые должны быть выведены из конкретных классов, и можно рекурсивно обратиться к тому же алгоритму сопоставления. Два класса, расположенные рядом в записи правила подстановки, могут породить значительное число различных вариантов.

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

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

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

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

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

Можно добавлять и другие априорные критерии. Нет нужды проводить разбор фразы по общему алгоритму, если можно написать специальную программу разбора, предназначенную для рассматриваемого класса. Эта задача упрощается тем, что известны обе границы фразы.

4.6. Сравнения

4.6. СРАВНЕНИЯ

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

Гриффите и Петрик [18] провели сравнение различных алгоритмов разбора на базе гипотетической машины (основанной на машине Тьюринга) и определили число шагов, затрачиваемых этой машиной на разбор различными методами для различных грамматик. Они показали также, что для любой грамматики всегда найдется эквивалентная грамматика, для которой метод разбора сверху вниз оказывается не намного медленнее, чем метод разбора снизу вверх для исходной грамматики.

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

Если говорить о ранних системах, то компилятор компиляторов Брукера и Морриса основывался на разборе сверху вниз, а в системе PSYCHO Айронса проводился разбор снизу вверх.

СПЕЦИАЛЬНЫЕ МЕТОДЫ ГРАММАТИЧЕСКОГО РАЗБОРА

Маловероятно, чтобы методы разбора, порождающие все варианты анализа любого предложения в любой контекстно-свободной грамматике, оказались достаточно быстрыми для того, чтобы их можно было применять в компиляторах. Поэтому для быстрой компиляции обычно применяются алгоритмы разбора, которые порождают только один вариант анализа и пригодны только для ограниченного класса грамматик. Такие алгоритмы могут основываться на разборе сверху вниз или снизу вверх и обычно работают слева направо. Алгоритмы разбора и класс грамматик, к которым они применимы, обычно выбираются таким образом, чтобы существовали априорные критерии, согласно которым на каждом щагу оказывалось бы подходящим только одно правило подстановки, т. е. чтобы можно было получать разбор непосредственно, без возвращения назад. Последнее характерно не для всякого специального метода; в частности, система PSYCHO Айронса применима лищь к некоторым грамматикам, но допускает возвраты.

Первый метод, описываемый в этой главе, может основываться как на разборе сверху вниз, так и на разборе снизу вверх; остальные методы основаны на разборе снизу вверх.

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

SaX X->b:cX

предложения

ab acb

можно разобрать сразу, руководствуясь при сопоставлениях класса X тем, что, когда остаток предложения начинается с Ь, нужно применять первое правило подстановки, а когда остаток начинается с с - второе правило подстановки.

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

Если у грамматики есть это свойство, то алгоритм разбора, описанный в приложении 2, может быть существенно ускорен. Однако еще более быстрый вариант можно получить, если оттранслировать саму данную грамматику в программу соответствующего разбора. Основанный на этом принципе компилятор описан автором в статье [14].

Будем предполагать, как в программе из приложения 2, что переменная симв содержит очередное слово из последовательности. Каждый класс можно оттранслировать в рекурсивную процедуру распознавания фраз, выводимых из этого класса. Предыдущая грамматика транслируется в следующую проце-

procedure S;

begin if симв ф а' then отказ; симв: = следующий; X

end;

procedure X;

begin if симв==Ь' then завершение

else if симв =с' then begin симв: = следующий;

else отказ

end;

симв: = следующий; S

Первое слово заносится в симв и вызывается процедура S. Если это слово не есть а, то разбор не получится. Если же это а, то следующее слово заносится в симв и вызывается X. Процедура X работает аналогичным образом. Это быстрый процесс, и по такому принципу можно было бы написать

распознаватель, работающий методом подгонки, без знания грамматики.

До сих пор мы имели дело исключительно с грамматиками, в которых правила подстановки определяются только в терминах слов и классов. Иногда оказывается полезным введение пустой подстановки

Г->0

означающей, что класс Т может быть заменен на пустую последовательность.

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

S-*TX

Х-*0\+тх

T->udY

Y-*0\XudY

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

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

procedure S;

begin па: If not ид (симв) then отказ; симв: = следующий;

if симв = Х' then begin симв: = следующий;

go to па

end;

if смжв = -+- then begin симв: = следующий;

go to па

end;

симв: = следующий; 3

Этот метод обсуждается далее в гл. 6, где описывается способ построения разбора для исходной грамматики.

5.1. МЕТОДЫ РАЗБОРА СНИЗУ ВВЕРХ

Рассмотрим процесс грамматического разбора снизу вверх и слева направо, при котором всегда удается правильно выбрать правило подстановки для очередного применения. На промежуточном этапе этого процесса левая часть последовательности уже частично сведена в некую последовательность классов и слов, а правая часть исходной последовательности остается неизменной. Это состояние можно описать в виде

/Л ...

где /ft - либо слово, либо класс, а Wh - слово.

Если очередное применяемое правило подстановки определяется по интервалу от /i до / и от \Vj до и^-ь то принято говорить, что данный язык принадлежит классу LR{t). Флойд описал алгоритм разбора для языков из класса LR{1).

Если же очередное правило подстановки определяется по последним т элементам / и по первым s словам W, то говорят, что язык ограничен контекстом (т, s), или принадлежит классу ВС{т, s). Иногда ВС{т, s) определяется в терминах последних т слов из /. Описываемые ниже алгоритмы разбора предназначаются для языков из ВС{1, 1).

Если априорный критерий выбора очередной подстановки включает рассмотрение только двух элементов на стыке I и W, то следует ожидать, что он требует мало времени, и тогда такой метод должен обеспечивать быстрый грамматический разбор.

6.2. ГРАММАТИКИ С ОПЕРАТОРНЫМ ПРЕДШЕСТВОВАНИЕМ

Операторной грамматикой называется грамматика, среди правил подстановки которой нет правил вида

А -> aflCp

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

Определим следующие три возможных отношения между словами, принадлежащими словарю операторной грамматики,

5. Специальные методы грамматического разбора

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

или

apBqfi

где а и р -любые последовательности, возможно пустые, то мы будем говорить, что

p = q

Если существует подстановка

Л->авР

и вывод или

в -> трС

то будем говорить, что

Р>(1

Если существует подстановка

А apflp

B-*qx

и вывод или

то будем говорить, что

B-*Cqx P<q

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

Очевидно, что эту информацию полезно учитывать в процессе грамматического разбора. В самом деле, предположим, что упорядоченная пара (р, 9)-два соседних слова в частично сведенном предложении, т. е. предположим, что они разделяются только символами классов, но не терминальными символами. В таком случае они принадлежат одной и той же простой фразе тогда и только тогда, когда р = q. Простая фраза - это фраза, не содержащая никакой другой фразы Если р > q, то р принадлежит некой фразе, которой не принадлежит q, а классы

) Напоминаем, что фраза - это часть последовательности, которая выводится из какого-то класса. - Прим. перев.

5.2. Грамматики с операторньш предшествованием

между р W. q также принадлежат этой фразе. Аналогично если р < q, то q принадлежит некой фразе, которой не принадлежит р. Поэтому становится легко определять фразовую структуру предложения. Само по себе это не обеспечивает полного построения дерева разбора, так как используемые подстановки могут не быть непосредственно выводимыми, но обычно их совсем легко найти, когда структура известна. Правила подстановки вида

не обнаруживаются в такой фразовой структуре; рассматриваемая структура состоит из подстановок, каждая из которых содержит хотя бы одно слово. Рассмотрим грамматику

T\S + г

Р\тхр а 1(5)

Это грамматика для выражений со знаками X и с круглыми скобками.

Выполняются следующие отношения

Произведем теперь разбор предложения a + bX{c + d)

используя символ с для обозначения неизвестных классов и показывая построение дерева фраз:

а + b X ( с + d )

> < > <<> <>

а + b X (с + d)

С + b X ( с + d ) О < < > < >

а + b X {с + d)

С + С <

X ( с + d ) < < > < >

а + b X {с + di

Заметим, что первое отношение выполняется между + и Х; С игнорируется.

С + С X ( С + d ) \ I I

< << <> а + b X (с + d)

С + С X ( С + С ) а + b X (с + d) < < < >

I I ) а + b

С + С X ( С ) < < =

С + С X С <

, . . П

а + Ь X (с + d)

a + bx(c + d)

С + С

a + bx(c + d)

а + b X ( с + d )

Тот факт, что анализ в действительности имеет вид

г

р

г

р

г

т

+ b X ( с + d )

5.2. Гра.чматики с операторным предшествованием

следует установить, принимая во внимание эффект подстановок типа

и подыскивая подходящие классы для вершин дерева.

Это можно описать в форме разбора слева направо следующим образом. Формируется магазинный список / из слов и классов; в начале разбора этот список руст. Процесс начинается с занесения первого слова предложения в магазинный список. На каждом промежуточном этапе состояние определяется списком / и остатком предложения:

Рассматриваем последнее слово в /; пусть это слово р. Если р =1 Wj или р < WI, то добавляем Wj к магазинному списку и переходим к следующему слову. Если между р и не выполняется ни одно из отношений =, <, >, то предложение неправильно построено. Если р > Wf, то отыскиваем наибольшее множество слов из /, удовлетворяющих отношениям

Ia<h = lc =

Все слова и классы от / до конца магазинного списка, за исключением / , соответствуют некоторой подстановке и могут быть свернуты в какой-то класс. Слово Wj не удаляется из последовательности, и тот же процесс повторяется. Единственная трудность состоит в том, что конкретный класс не определяется этим процессом, а должен быть установлен другими средствами. Обычно это не представляет труда, так как фразы часто содержат некоторые отличительнке слова. Так, для предыдущей грамматики, если найдена фраза, содержащая +, то она может возникнуть только из правила подстановки

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

Если отвлечься от формирования дерева разбора, то можно легко записать этот алгоритм;