находится в L.

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

{aaae{0,1}*)

({0,1}* есть замыкание {0,1}, как определено в разд. 2.2). Из леммы следует, что любую строку г длиной >k можно записать как в виде uvwxy, где vwx<=k, vx0 и uvwxy(i>=0) находится в языке.

Пусть а состоит из k нулей и последующих k единиц, так что z имеет вид

000 01111 1000 01111 1 Эту строку можно записать следующим образом:

uvwxy,

но так как vwx <=k, то или 1) v и х находятся либо в первой половине z, либо во второй, или

2) их содержит единицы из первой половины строки и нули из вто рой половины строки.

В первом случае uwy образуется путем исключения нулей и единиц из первой или второй половины z (но не из обеих). Таким образом, uwy не находится в языке.

Во втором случае uwy образуется из z путем исключения единиц из ее первой половины и нулей из второй. Полученная в результате строка опять не будет находиться в языке.

Таким образом, мы показали, что данная строка не может быть выражена в виде uvwxy, чтобы uwy тоже находилась в языке. Это противоречит лемме подкачки, и поэтому данный язык не относится к контекстно-свободным. Аналогично можно показать, что языки

{anbncnn>=0} {aii есть простое число}

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

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

(K,Z,r,5,q0,Z0)

где К - конечное множество состояний, Z- входной алфавит, Г - алфавит магазинный, 5- множество переходов, q0 - начальное состояние, Zo - символ магазина, который первоначально находится в стеке.

Рассмотрим, например, автомат магазинного типа М, определенный следующим образом:

K={A},

!={(,)}, Г={0,1}, q0={A}, Z0=I.

5 задается как

5(A,I,C)=(A,I0)

(что означает: в состоянии А с I в вершине стека при чтении ( перейти к состоянию А и заменить I на Ю).

5(A,0,C)=A(A,00)

5(A,0,C)=(A,e)

5(A,I,e)=(A,e)

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

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

{ааrа в {0,1}* } Здесь а обозначает строку, обратную а.

Этот язык принимается следующим недетерминированным автоматом магазинного типа

M=({A,B}, {0,1}, {I,0,1),5,А,I),

где переходы заданы посредством

5(A,I,0)={(A,I0)},

5=(A,I,1)={(A,I1)},

5(A,0,0)={(A,00},(B,e)},

5(A,1,1)={(A,11),(B,e)},

5(A,0,1)={(A,01)},

5(A,1,0)={(A,10)},

5(B,0,0)={(B,e)},

5(B,1,1)={(B,e)},

5(B,I,e)={(B,e)},

5(A,I,e)={(A,e)}.

Состояние A соответствует прочтению менее половины строки, а состояние B - прочтению более половины строки. При чтении первой половины строки символы помещаются в стек (состояние А), а при чтении второй - каждый символ сверяется с верхним символом в стеке, и из стека удаляется один

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

01011011011010

Можно подумать, что две единицы, занимающие позиции 4 и 5, отмечают середину строки. Однако, не заглянув вперед (в целом) на какое-либо произвольное расстояние, нельзя с уверенностью сказать, середина ли это. Отсюда - попеременные переходы в состоянии А, когда входной символ и вершина стека являются идентичными. Это делает автомат магазинного типа недетерминированным, и трудно представить себе иную ситуацию. Действительно, как известно из теории, существует недетерминированный автомат магазинного типа, принимающий контекстно-свободные языки, которые не принимаются никакими детерминированными автоматами магазинного типа. Следовательно, мы всегда можем найти детерминированный автомат, принимающий регулярный язык. Для контекстно-свободнтх же языков это положение не выдерживается. Если вспомнить, что детерминированные конечные автоматы получают из недетерминированных путем соединения состояний, где два или более переходов приводят к различным состояниям, вряд ли покажется странным, что такой же метод не срабатывает в отношении автоматов магазинного типа, когда альтернативные переходы могут по-разному влиять на стек.

При разборе происходит эффективное моделирование соответствующего автомата магазинного типа. А из изложенного выше вытекает, что некоторые контекстно-свободные языки не могут анализироваться детерминированным образом (т.е. без возврата). Насколько это важно, с точки зрения создателя компилятора, зависит от того, можно ли типичные языки программирования анализировать детерминированно или нет. Язык, который допускает детерминированный анализ, мы называем детерминированным; оказывается, что большинство языков программирования являются детерминированными или по крайней мере почти таковыми.

Между контекстно-свободными грамматиками и автоматами магазинного типа существует полное соответствие, и детерминированность автомата может зависеть от того, какая грамматика используется для генерирования языка. Мы говорим, что метод разбора является детерминированным (для конкретной грамматики), если при разборе данной грамматики не требуется делать возврат. Некоторые языки можно разбирать детерминированно с помощью только одного из методов грамматического разбора. В частности, ряд языков можно разбирать детерминированно снизу вверх, но не сверху вниз. В этой книге мы будем иметь дело почти исключительно с детерминированными методами разбора. Недетерминированные методы могут применяться к таким строчно-ориентированным языкам, как Бейсик или Фортран. Для языков же крайне рекурсивных (Алгол 68, Паскаль), где компилятор может быть вынужден возвращаться назад не только в текущей строке, но и в большой части программы, издержки просто неприемлемы. Другой недостаток возврата заключается в том, что он может вызвать отмену действий компилятора, которые осуществляются параллельно с синтаксическим анализом.

4.2. МЕТОД РЕКУРСИВНОГО СПУСКА

Метод рекурсивного спуска - хорошо известный и легко реализуемый детерминированный метод разбора сверху вниз. С его помощью на основании