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

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

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

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

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

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

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

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

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

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

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

Рассмотрим грамматику

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

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

Произведем теперь разбор предложения

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

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

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

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

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

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

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

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

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

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

Информацию об отношениях между словами можно хранить в виде матрицы, но часто оказывается возможным определить для каждого слова два веса, f u g, таким образом, чтобы

Для предыдущего примера мы можем выбрать

В таком случае выражение

в нашем алгоритме может быть заменено на

Флойд [11] предложил алгоритм исследования грамматики с целью выяснения, является ли она грамматикой с операторным предшествованием, алгоритмы построения матрицы отношений, а также вычисления f u g, если это возможно. Он также доказал теоремы, обосновывающие эти алгоритмы.

Чтобы показать, что для грамматики с операторным предшествованием не всегда можно подобрать f и g, рассмотрим грамматику

для которой, в частности, справедливы следующие отношения

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

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

потому что в описаниях массивов «:» разделяет арифметические выражения. Однако в то же время

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

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