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

6.1. ПРЕОБРАЗОВАНИЯ ДЛЯ ИСКЛЮЧЕНИЯ ЛЕВОЙ РЕКУРСИИ

Грейбах показал, что для любой заданной грамматики всегда найдется эквивалентная грамматика без левой рекурсии. В литературе описаны различные преобразования, обеспечивающие удаление левой рекурсии [14, 19, 26, 35]. Ниже излагается такое преобразование, опубликованное ранее в работе [14].

Будем обозначать пустую фразу через 0, а недопустимую фразу через е. Если в предложении встречается символ 0, он может быть исключен; если же встречается символ , то предложение некорректно. Разумеется, можно установить соответствие между символами 0 и , с одной стороны, и символами 0 и 1, с другой. Мы будем использовать символ вместо 0, если r = s, и вместо , если . Рассмотрим сначала очень простое рекурсивное слева описание

определяющее предложения, которые начинаются с символа а и далее содержат любое количество символов b. Грамматика

определяет те же предложения. Здесь Y — вспомогательный класс, введенный при преобразовании. В общем случае производится аналогичное построение.

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

которое означает

Собираем вместе все правила подстановки для и по мере необходимости определяем новые вспомогательные классы, чтобы привести правила подстановки в вид

где не может начинаться с какого-либо класса и не существует вывода . Может потребоваться, чтобы правила подстановки для или содержали 0 или .

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

где — вспомогательные классы, число которых равно

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

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

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

Во-вторых, не существуют выводы

так как такой вывод смог бы возникнуть, только если бы существовал вывод

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

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

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

существует терминальный вывод.

Поэтому для любого класса найдется вывод

а поскольку , то для существует корректный терминальный вывод.

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

преобразуется в

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

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