Главная > Разное > Автоматический синтаксический анализ
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

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

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

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

предложения

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

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

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

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

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

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

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

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

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

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление