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

2. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ

2.1. ТЕРМИНОЛОГИЯ

Мы будем пользоваться следующими терминами и обозначениями. Построенные надлежащим образом последовательности будут называться предложениями. Они будут состоять из упорядоченных объектов, называемых словами. Мы не будем касаться структуры слов, а предположим, что умеем как-то распознавать слова. В примере на стр. 7 символы а, b, с, d, е, f, были словами. Слова будут записываться строчными буквами или будут такими символами, как и . Для описательных целей мы будем пользоваться некоторыми отличными от слов символами, которые будем называть классами. Их называют также нетерминальными символами. В предыдущем примере Сложить, Умножить и Выражение были классами. Классы будут всегда обозначаться прописными буквами. Предложение — это особый класс, который обычно обозначается символом 5. Всякому классу будет соответствовать набор возможных структурных вариантов, каждый из которых состоит из упорядоченных элементов, являющихся либо словами, либо классами. Эти варианты называются правилами подстановки. Таким образом, вся грамматика состоит из набора слов (словаря), набора классов, названия особого класса, т.е. предложения, и из набора правил подстановки.

В качестве простейшего примера рассмотрим грамматику со словарем а, b, с, d, с классами S и Т, с символом предложения 5 и с правилами подстановки, записываемыми следующим образом:

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

Будем говорить, что эти предложения могут быть выведены из S; возможность вывода предложения babcd указывается так:

Часть предложения, которая выводится из какого-то класса, называется фразой. Таким образом, в предложении babcd имеется фраза а, выводимая из Т, и фраза также выводимая из T.

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

и заменяем его на один из соответствующих ему вариантов

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

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

Будем говорить также, что выводится из

и что а выводится из Т:

Заметим, что специфическое свойство таких правил подстановки состоит в том, что подстановки, применяемые для конкретных классов в конкретных местах, не зависят ни от окружающего контекста, ни от последовательности применявшихся ранее операций подстановки. Класс Т может быть заменен без всяких ограничений как на а, так и на bc. Этим объясняется название «контекстно-свободные», которое применяется к таким грамматикам. Точный смысл этого названия состоит в том, что один «сосед» в последовательности не может оказывать влияния на другого отдаленного «соседа»; это требование накладывает сильное ограничение на языки, которые могут быть описаны такими грамматиками.

В приведённом выше примере мы могли бы выполнять по следовательность операций подстановки двумя способами:

или

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

а не прослеживать последовательность операций подстановки.

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

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

и

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

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

идентификатор

идентификатор + идентификатор

идентификатор + идентификатор + идентификатор

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

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

где X — любой класс. Такие выводы ничего не добавляют к множеству описываемых предложений, но создают возможность бесконечных возвратов при грамматическом разборе (X является X, который является ). Каждый класс должен появляться при некотором выводе из S. Если какой-то класс никогда не появляется, то он не приносит пользы для описания предложений и поэтому может быть исключен.

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

и никогда не породит терминальную строку.

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