5.3. анализ предложений

Задача трансляторов, или языковых процессоров , - в первую очередь не порождение, а распознавание предлоЖ^ НИН и их структуры. Это означает, что шаги порождения, к^ торые формируют предложение, должны реконструироватьс

скольку XZ е Т*, то xz есть предложение языка, т. е. хг Отметим, что нетерминальные символы /1 и В появля только на промежуточных шагах, а окончательный шаг л жен дать последовательность, состоящую только из геп нальных символов. Грамматические пра[вила называются рождающими, потому что они определяют, как новые послед вательности могут формироваться, или порождаться.

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

А::==1 {AN.liNliT)),

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

аЛР::=а|р,

то оно называется контекстно-зависимым, так как замена А на I может иметь место только в контекстах аир. Далее мы ограничим рассмотрение только контекстно-свободными языками.

Из примера 2 видно, как при помощи рекурсии конечное множество порождающих правил может задавать бесконечное множество предложений.

Пример 2:

(5 4)

А::=г\уА.

Начальный символ S может порождать следующие предложения:

xyyz

xyyyz

РЛ чтении предложения, т. е. проходиться в обратном по-ядке. В принципе это очень трудная, а иногда и невыполни-задача. Ее сложность сильно зависит от правил порождения, которые определяют язык. Разработка алгоритмов распознавания для языков с достаточно сложной структурой - задана теории синтаксического анализа. Здесь же наша цель - разработать метод построения алгоритмов распозна-0тя, достаточно простых и эффективных для практического применения. Это значит, что вычислительные затраты на анализ предложения должны находиться в линейной зависимости fft длины предложения, в самом худшем случае функция зависимости может быть /г-log/г, где п - длина предложения, разумеется, мы не можем ставить задачу поиска алгоритма распознавания для любого заданного языка, будем реалистами и поступим наоборот: построим некоторый эффектив-,яый алгоритм, а затем определим, с каким классом языков он может работать [5.3].

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

Основной метод, который мы здесь разберем, называется ходящим грамматическим разбором, поскольку, применяя ют метод, мы будем пытаться реконструировать этапы порождения (которые в принципе образуют дерево) от начального символа к конечному предложению, т. е. сверху вниз [5.5, 5.6]. Вернемся к примеру 1: нам дано предложение *.Собаки едят , и мы должны определить, принадлежит ли оно языку. По определению предложение принадлежит языку, только если оно может порождаться из начального символа (предложение). Из грамматических правил следует, что предложение должно состоять из подлежащего, за которым следует сказуемое. Теперь мы можем разделить задачу на две Подзадачи: вначале нужно определить, может ли какая-либо Начальная часть предложения порождаться из символа <под-Лежащее). Действительно, собаки может непосредственно порождаться из этого символа, поэтому мы убираем символ £обаки из входного предложения (т. е. сдвигйемся на один par) и переходим к следующей подзадаче: определить, может н оставшаяся часть предложения порождаться из символа <сказуемое>. Поскольку ответ вновь положительный, результат анализа положительный. Процесс работы можно изобразить такой схемой, где слева показаны стоящие задачи.

(предложение) (подлежащее) (сказуемое) собаки (сказуемое) (сказуемое) едят

собаки едят собаки едят собаки едят едят едят

Вторая схема демонстрирует процесс анализа предложения xyyz в соответствии с порождающими правилами примера о.

S xyyz

хА xyyz

А yyz

- ---уА----yyz

Z . Z

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

S::=A\B

А::=хА\у (5.5)

B::=--xB\z

Мы пытаемс проанализировать предложение хххг

H попадаем впросак. Трудность возникает на самом перво'* шаге, когда решение о замене S на А или В нельзя принять ка основе лишь первого символа. Можно прослеживать оДИ

а справа -еще не прочитанная часть входного предложен^