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

2.2. ПРИМЕРЫ ГРАММАТИК И ИХ СВОЙСТВ

В этом параграфе мы рассмотрим некоторые типичные грамматики и опишем их свойства, имеющие отношение к грамматическому разбору.

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

В этой грамматике типичный грамматический разбор предложения имеет вид

Класс X, для которого существует вывод

где а — непустая последовательность элементов, называется рекурсивным слева; в рассмотренном примере оба класса S и Т являются рекурсивными слева. Аналогично класс X, для которого существует вывод

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

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

Здесь все классы S, Т и Р являются рекурсивными. Типичный грамматический разбор предложения выглядит так:

Класс X, для которого существует вывод

где — непустые последовательности элементов, называется самовставляемым. Классы S, Т и Р являются самовставляемыми и, кроме того, классы S и Т — рекурсивные слева.

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

Однако при использовании этой грамматики типичный грамматический разбор выглядит несколько иначе:

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

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

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

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