Главная Промышленная автоматика.

Определение. КС-грамматика G = {N, 2, Р, S) называется LL(k)8paMMamuKou для некоторого фиксированного k, если из существования двух левых выводов

(1) S=:lwAaiWa=*wx

(2) S:=lwAaz=iWya,:=*wy,

для которых FIRST(x) = FIRSTft(y), вытекает, что ?i = y.

Говоря менее формально, G будет ГГ()-грамматикой, если для данной цепочки Eiya£(Nu2)* и первых k символов (если они есть), выводящихся из Ла, существует не более одного правила, которое можно применить к Л, чтобы получить вывод какой-нибудь терминальной цепочки, начинающейся с w п продолжающейся упомянутыми к терминалами.

Грамматика называется hh-г рамматикой, если она LL(fe)-rpaM-матика для некоторого к.

Пример 5.2. Пусть G состоит из правил S-пЛ5Ь, Л-* аI bSA. Интуитивно является ЬЬ(1)-грамматикой, потому что, коль скоро дан самый левый нетерминал С в левовыводимой цепочке и следующий входной символ с, существует не более одного правила, применимого к С и приводящего к терминальной цепочке, начинающейся символом с. Переходя к определению ЬЬ(1)-грамматики, мы видном, что если S=]wSawa]wx и 8*1 wSa=iWya*iwy и цепочки хну начинаются одними тем же символом, то должно быть р = у. В данном случае если хиу начинаются символом а, то в выводе участвовало правило S-*-aAS и \/> - y = aAS. Альтернатива 5-здесь невозможна. С другой стороны, если хиу начинаются с &, то должно применяться правило S ->Ь п =у = Ь. Заметим, что случай х = у-е невозможен, так как из S-b грамматике не выводится е.

Когда рассматриваются два вывода S->*iwAa==>iWpa=yiWX и S:=±>lwAa=iWya=lwy, рассуждение аналогично. □

Грамматика G служит примером так называемой простой ЬЬ(1)-грамматики (или разделенной грамматики).

Определение. КС-грамматика G-(N, 2, Р, 5) без е-правил называется простой ЬЬ(1)-грамматикой (или разелтнуй грамматикой), если для каждого Л 6 N все его альтернативы начинаются различными терминальными символами.

Таким образом, в простой ЬЬ(1)-грамматике для данной пары (А, а), где ЛN и aI., существует не более одного правила вида Л ->-аа.

Пример 5.3. Рассмотрим более сложный случай -грамматику G определяемую правилами 5-е\аЬА, ASaa\b. Покажем, Q -это ЬЬ(2)-грамматика. Для этого докажем, что если любая левовыводимая цепочка грамматики GhwxL{G), то в Ga найдется не более одного правила В-для которого рШ5Тз(ра)содержитРШ8Та(:). Допустим,что5=; wSawa и 5=»J wSaiWyoL] wy, где первые два символа цепочки х (если они есть) совпадают с первыми двумя символами цепочки у. Так как G - линейная грамматика, то а (а + Ь)*. На самом деле можно сказать больше; либо w=cc = e, либо последним участвовало в выводе 3*1 wSa правило Л-Saa. (Другим способом 5 в левовыводимой цепочке появиться не может.) Таким образом, либо а = е, либо а начинается с аа.

Допустим, что при переходе от wSoc к wa применялось правило 5->е. Тогда и л:-либо е, либо начинается с аа. Аналогично, если при переходе от wSoc к wya применялось правило 5-е, то а-е и у-либо е, либо начинается с аа. Если при переходе от wScc к wftcc применялось SabA, то = аЬА и X начинается с аЬ. Аналогично, если при переходе от wSa к wya применялось S-abA, то у---аЬА и у начинается с аЬ. Итак, пет иных возможностей, кроме x - - л: иначинаются с аа, X и у начинаются с аЬ. Из любого другого условия, которое можно наложить на первые два символа цепочек х и у, следует, что либо один, либо оба вывода невозможны. В первых двух из рассмотренных выше случаев в обоих выводах применяется правило 5-и p = yt. В третьем случае должно применяться SabA и - у = аЬВ.

В качестве упражнения докажите, что ситуация, при которой справа от рубежа рассматриваемой левовыводимой цепочки стоит символ Л, не противоречит определению ЕЕ(2)-грамматики. Проверьте также, что G не является ЕЬ(1)-грамматикой. □

Пример 5.4. Рассмотрим грамматику G = ({S, Л, В), {О, \,а,Ь}, 8. 5), где состоит из правил S-A\B,A~aAb\, ВаВЬЬ\\. Здесь L (Сз) = {а"Ой" д > 0} U 1 > о}

не является

ЕЕ(й)-грамматикой ни для какого к. Интуитивно, если мы начинаем с чтения достаточно длинной цепочки, состоящей из символов а, то не знаем, какое из правил 5-Л и 5-6 было применено первым, пока не встретим О или 1.

Обращаясь к точному определению ЕЬ(й)-грамматики, положим w = a = e, = А, у = В, хаОЬ и yalb-. Тогда выводы

соответствуют выводам (1) и (2) определения. Первые k симво-ов цепочек хиу совпадают. Однако заключение f> = y ложно.



входнйй лента

входная еалоЗт.

праблйющая та.&7ица

я"

вшодяая лента

Рис. 5.2. Предсказывающий алгоритм разбора.

выходную ленту (рис. 5.2). Этот алгоритм пытается проследить левый вывод цепочки, записанной на его входной ленте.

При чтении анализируемой цепочки, находящейся на входной ленте, входная головка может „заглядывать вперед" на k очередных символов (отсюда число k в названии -предсказывающего алгоритма). Эту цепочку из Ь, символов, увиденную впереди входной головкой, будем называть аванцепочкой). На рис. 5.2 аванцепочкой служит подцепочка и входной цепочки mix.

Магазин содержит цепочку Ха$, где Ха -цепочка магазинных символов, $ - специальный символ, применяемый в качестве маркера дна магазина, и X - верхний символ магазина. Алфавит магазинных символов (без $) будем обозначать Г.

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

Конфигурацию предсказывающего алгоритма разбора будем представлять в виде тройки (х, Ха, л), где

(1) X-неиспользованная часть первоначальной входной цепочки,

) Термин образован по аналогии со словами „авансцена", „авангард" и т. п. (в оригинале lookahead string).-Прим. перев.

Ха -цепочка в магазине (X - верхний символ),

lgj л -цепочка на выходной ленте.

Например, на рис. 5.2 изображена конфигурация [их, Ха$, я).

Работой -предсказывающего алгоритма J руководит упрае-/7za6yiuijaM, задающая отображениемножества(Г U {$))х2* в множество, в которое входят

(1) (р1 0. РГ*, а (" - номер правила (предполагается, что р будет либо правой частью ("-го правила, либо некоторым его представлением),

(2) выброс 1),

(3) допуск,

(4) ошибка.

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

FIRST ,,(л-).

(1) [х, Ха, л)1-(х, ра, ni), если М(Х, w)--(p, 0. Здесь верхний символ магазина X заменяется цепочкой рГ* и к выходу добавляется номер правила i. Входная головка не сдвигается.

(2)(x, са, П)\-[х, а, л), если М(д, и)выброс и ах. Когда верхний символ магазина совпадает с текущим входным символом (первым, символом аванцепочки), он выбрасывается из магазина и входная головка сдвигается на один символ вправо.

(3) Если алгоритм достигает конфигурации {е, $, л), работа прекращается и выходная цепочка л называется разбором первоначальной входной цепочки. Будем предполагать, что всегда ($. е) = допуск, и конфигурацию {е, $, л) будем называть допускающей.

(4) Если алгоритм достигает конфигурации [х, Ха, л) иМ (X, w) = ошибка, то разбор прекращается и выдается сообщение об ошибке. Эту конфигурацию (х, Ха, л) назовем ошибочной.

Конфигурация [w, Хо$, е), где ау g S* -анализируемая цепочка, а Х-выделенный начальный символ, называется начальной. Если (, Хп$, е) -*((?,$, л), то будем писать d{w)n и назы-.ь л выходом алгоритма Л для входа w. Если из конфигурации

Х$, е) допускающая конфигурация не достигается, то будем говорить, что значение d{w) не определено. Переводом, опреде-

) В оригинале pop.-Прим. перев*

Так как k здесь выбрано произвольно, то Gg не является LL-грам-матикой. В гл. 8 мы увидим, что для языка Л(Сд) не существует ЪЬ()-грамматики.

5.1.2. Предсказывающие алгоритмы разбора

Покажем, что разбор для ЕЬ(/г)-грамматики очень удобно осуществить с помощью так называемого к-предсказывающего алгоритма разбора, /г-предсказывающий алгоритм .4 для КС-грамматики G = (N, 2, Р, S) использует входную ленту, магазин н



ляемым алгоритмом Л, называется множество %{MUm тгм

Будем называть -предсказывающий алгоритм разбора Л для КС-грамматики G корректным в том случае, когда

(1) L(G) = {w\A{w) определено},

(2) если Л{1ю)п, то л; -левый разбор цепочки w.

Если работой -предсказывающего алгоритма Л руководит управляющая таблица М и он корректен для КС-грамматики G то М будем называть корректной управляющей таблицей для G

Аданце/tot/m

Верхний.

символ

магазина

aAS,}

ошибка

bSAA

ошибка

выброс

ошибка

ошибка

ошибка

выброс

ошибка

ошибка

ошибка

ЛОПУСК

Рис. 5.3. Управляющая таблица алгоритма .

Пример 5.5. Построим 1-предсказывающий алгоритм разбора для лростой ЕЕ(1)-грамматикн Gj из примера 5.2. Прежде всего занумеруем правила грамматики G:

(1) SaAS

(2) Sb

(3) А~а

(4) AbSA

Управляющая таблица алгоритма Л показана на рис. 5.3.

С помощью этой таблицы алгоритм Л так проанализирует входную цепочку аЬЬаЬ:

(abbaby S%,e)\-(abbab, aAS%, 1) V~-ibbab, I)

-(bbab, bSAS%, 14) \-(bab, SAS%, 14) \~-{bab, bAS%, 142) \-(ab, AS%, 142) НИ. «55, 1423) \-(Ь, Ss, 1423) \-{b, 6$, 14232) \-(e, 14232)

Ha первом такте M{S,a) = {aAS, 1), так что верхний символ магазина S заменяется на aAS и номер правила 1 записывается на выходной лепте. На следующем такте М.(а, й)--выброс, так что а выбрасывается из магазина и входная головка сдвигается на одну позицию вправо.

Продолжая в том же духе, получаем допускающую конфигурацию (е, $, 14232). Очевидно, что 14232 -левый разбор цепочки abbab и, более того, Л - корректный 1-предсказывающий алгоритм разбора для грамматики Gj. □

-предсказывающий алгоритм разбора для КС-грамматики G можно моделировать на детерминированном МП-нреобразователс с концевым маркером на входной ленте. Так как входная головка МП-преобразователя может обозревать только один входной символ, аванцепочка должна храниться в конечной памяти управляющего устройства. Остальные детали моделирования очевидны.

Теорема 5.1. Пусть Л - к-предсказывающий алгоритм разбора для КС-грамматики G. Тогда сущствует такой детерминированный ШЛпреобразователь Т, что t:{T){{w$, n)\Л{w) = n}.

Доказательство. Упражнение. □

Следствие. Пусть Л-корректный к-предсказывающий алгоритм разбора для КС-грамматики G. Тогда для G существует детерминированный левый анализатор.

Пример 5.6. Построим детерминированный левый анализатор для 1-предсказывающего алгоритма из примера 5.5. Так как грамматика простая, получится небольшой ДМП-преобразователь, на каждом такте сдвигающий входную головку вправо. Левый анализатор будет использовать $ в качестве маркера правого конца входной ленты, а также маркера дна магазина.

Пусть Р = ({9о, д, допуск}, {а, Ь, $}, {5, Л, а, Ь, $}, б, q,, $, {допуск}), где б определяется равенствами

б(9о S) = (9. 5$, е) 6{q, а, S){q, AS, 1) 6(q,b,S)={q, е, 2) 6(9, а, A) = (q, е, 3) b{q,b,A) = (q, SA,4) б {q, $) = (допуск, е, е)

Легко видеть, что (te$, л)т(Р,) тогда и только тогда, когда





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 [62] 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.003