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

Е-Е-Т-Т-F-

-T-i-E

Пусть служит F.:T, г,-для F

(2) (3) (4) (5)

индексом для Г + -для

F-для а. Для входа а + л вычисляет такую последовательность конфигураций:

(7, 1,,£$)-(9, l,£i, Г+£$)

\-{q, l,EiT, /*r + £$) h-(9, hE.TF,, й*Г + £$) \-{q,2,E,T,F,a, *Г + £$) h-(b,2, *r+£$)

\~{Ь, l,E,T,Fi, a*T-{-E$) \-{b, l,£,r„f*r + £$) h-(7, l,EiT,, f+£$) \-{q, UEiT.Fi, a + £$) [-{q,2,E,T,F,a, +£$) -(9. 3,£,r,F,a+, £$) \-{q, 3, EJ,F,a + E,,T

r, Ti-для алгоритм 4.1

-E$)

\-(q.3,EiT,F,a + EiTi, f*r + £$)

(q 3,

EiTFa + EyrFi, а*Г + £$)

(q, 4,

E.TFa-EJiFa, *Г + Я$)

(b, 4,

EjTFia + EJiFa, *Г + £$)

. \-

(b,3,

EyrFaEiTF, а*Г + £$)

(&, 3,

E,T,Fa + EiTi, F*r + £$)

(9» 3,

EiT,F,a + E,T,, F + £$)

[q, 3,

EiT.F.a-EJ.Fi, a + £$)

(9. 4,

Ej,F,a + EiT,F,a, +£$)

(b, 4,

E,T,Fa-\-EJ,F,a, +£$)

(b, 3,

E,T,FaEJ,Fi, a + E$)

(i, 3.

EiT.F.a-iEJ,, F + E$)

(fc. 3

EJ,F,a-\-E,, r + £$)

(«у.з.

E,T,F,a + E„ r$)

(9,3

Ej,F,a + EJ,, f *r$)

(9, 3,

EiT,F,a + E,T,Fi, aT$)

(9.4

E,T,F,a+EJ,F,a, *Г$)

(&. 4,

E,T,F,a + EJ,F,a, *Г$)

(&,3

E,T,F,a + EJ,Fi, а*Г$)

(i?, 3,

EiT,F,aE,T,, F*T$)

(9,3.

Ej\F,a + EJ,, f S)

(9, 3,

EiT,F,a + EJ,F,, a$)

(9,4,

Ej\F,a}-EJ,F,aZ$)

(t, 4,

EjFa-\-EJ,F,a, e)

В результате получается левый разбор h[E-yrja-{ET2Fa) = = 145245. □

Теперь покажем, что алгоритм 4Л действительно дает левый разбор цепочки лу в соответствии с грамматикой G, если он существует.

Определение. Частичным левым разбором назовем последовательность правил, использованных при левом выводе левовы-водимой цепочки. Будем говорить, что частичный левый разбор совместим с входной цепочкой если соответствующая лево-выводимая цепочка совместима с т. е. ее терминальный префикс до первого нетерминала является префиксом цепочки w.

Пусть G(N, S, Р, S)-не леворекурсивная грамматика и ... -входная цепочка. Определим последовательность

0, п

о, -14»

совместимых с w частичных левых разборов.

(О 0 = представляет вывод нетерминала S из 5 (строго

говоря, л, -не разбор).

ПОЧКИ, совместимые с входной цепочкой w, уже исчерпаны, а ее разбор не найден.)

(iii) {b, i, а, Лр) в оставшихся случаях. (Здесь исчерпаны все альтернативы нетерминала Л и дальнейший возврат происходит путем удаления Aj из Ы и замены в L2 цепочки уу на Л.)

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

Шаг I. Исходя из начальной конфигурации, вычислять последующие конфигурации 1- [-... [~ С,- j-..., пока их можно вычислить.

Шаг 2. Если последняя вычисленная конфигурация - (t, /г+1, Y, е), выдать h{y) и остановиться. В противном случае выдать сигнал об ошибке. □

Алгоритм 4.1-это по существу описанный ранее неформально алгоритм, к которому для выполнения возвратов добавлена некоторая „бухгалтерия".

Пример 4.1. Рассмотрим работу алгоритма 4.1 на грамматике G с правилами



могут быть В Ll, то эти две последовательности совпадают, за исключением того, что Ll может содержать последовательности, не совместимые со входом. Когда в L1 появляется такая последовательность, сразу происходит возврат. □

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

Лемма 4.1. Пусть G = (N, S, Р, 3) - не леворекурсивная грамматика. Тогда найдется такая константа с, что если А =ф-\ wBa

и \ w\ = n, то I-

пП + 2 1

Доказательство. Пусть #N = fe. Рассмотрим дерево D левого вывода A:=wBa, Допустим, что существует путь от корня к листу длины, большей, чем fe(« + 2). Пусть п-вершина, помеченная нетерминалом В, явно указанным в цепочке wBa. Если


Рис. 4.5. Дерево вывода D.

этот путь оканчивается листом, расположенным справа от п, то путь к Hq должен быть не менее длинным. Это следует из того, что в левом выводе правило всегда применяется к самому левому нетерминалу. Поэтому прямой предок каждой вершины, расположенной справа от п, является предком вершины «о- Дерево D показано на рис. 4.5.

Таким образом, если в D есть путь длины, большей, чем (/г + 2), то можно найти один такой путь, достигающий /г или вершины, расположенной слева от п. Тогда на этом пути можно найти 4-1 последовательных вершин /г, каждая нз

Которых порождает один и тот же кусок цепочки wB. Все пря-

На самом деле можно доказать более сильное утверждение: t линейно зависит от п. Однако пока нам достаточно и этого результата, а потом мы его Помощью докажем более сильное утверждение.

(2) Пу - номер правила 5-у а, где а-первая альтернатива нетерминала S.

(3) я,- определяется так. Допустим, что S;. =хЛу. Пустьр - такая альтернатива нетерминала Л с наименьшим номером, если она существует, что xfjy =хуЬ, где б либо е, либо начинается нетерминалом, и х/ -префикс цепочки w. Тогда n = n yAi, где k - номер альтернативы р. В этом случае будем называть л,-продолжением разбора л, 1. Если, с другой стороны, такой альтернативы р нет или Зл. =Фх для некоторой терминальной

цепочки X, то пусть / - наибольшее из чисел, меньших i - 1, для которых выполняется следующее условие:

Пусть Sji.=xBy и Uji - продолжение разбора Яу, причем на последнем шаге разбора ЛJ y нетерминал В заменяется альтернативой а. Пусть - первая из альтернатив нетерминала В, которая следует за в упорядочении альтернатив этого нетерминала, и если записать хаухуЬ, где б либо е, либо начинается нетерминалом, то ху - префикс цепочки w.

Тогда Л1 = ЛуВ, где В - номер правила В-а. В этом случае назовем л модификацией разбора Я; 1.

Если сформулированное условие не выполняется, то разбор не определен.

Пример 4.2. Для грамматики G из примера 4.1 и входной цепочки а-\-а получается такая последовательность совместимых частичных левых разборов:

I45I

14513

14514

1452

14523

14524

145245

Заметим, что последовательность совместимых частичных левых разборов вплоть до первого корректного разбора тесно связана с последовательностью цепочек, появляющихся в магазине Ll. Если отвлечься от терминальных символов, которые



мые ПОТОМКИ вершины tii расположенные слева от

tiix, порождают е. Следовательно, можно найти две вершины из /II, ..., tif+i с одной и той же меткой, и легко видеть, что эта метка - леворекурсивный нетерминал.

Отсюда заключаем, что в D нет путей, длина которых больше ft (/г + 2). Пусть /-длина самой длинной из правых частей правил грамматики G. Тогда D имеет не более внутренних вершин. Поэтому если AwBa, то Возьмем с-=1\ лемма доказана. □

Следствие. Пусть G = (N, S, Р, 5)-не- леворекурсивная грамматика. Тогда найдется такая константа с, что если S\wB(x и тфе, то \а\с \ w\.

Доказательство. Мы показали (см. рис. 4.5), что длина пути от корня к вершине Пд не превосходит й(е(у + 2). Поэтому la<fe/(lt(y + 2). Возьмем с= SkL □

Лемма 4.2. Пусть G = Р, S) -КС-грамматика, не содержащая бесполезных нетерминалов, и w~aa. ... a„S*. Последовательность совместимых с w левых разборов конечна тогда и только тогда, когда G не леворекурсивна.

Доказательство. Если G леворекурсивна, то ясно, что для некоторой терминальной цепочки последовательность совместимых с нею левых разборов бесконечна. Допустим, что G не леворекурсивна. Тогда по лемме 4.1 длина каждого совместимого с W левого разбора не превосходит Таким образом, число совместимых с w левых разборов конечно. □

Определение. Пусть G(N, 2, Р, 5)- КС-грамматика и у - последовательность индексов альтернатив (т. е. нетерминалов с номерами) и терминалов. Пусть л -частичный левый разбор, совместимый с w. Будем говорить, что у описывает л, если выполняется следующее условие:

(1) Пустьл-Pi,... Ри и 5=-аор,=а рза ... p,=a. Пусть а=х1, где р/ -либо е, либо начинается нетерминалом. Тогда y = Ai,wAi,W2 ... Acw,, где Л г.- индекс правила (альтернативы), примененного при переходе от к «у, н &Уу -такой суффикс цепочки Xj, что Xj=Xj-i Wj,

Лемма 4.3. Пусть G=(N, 2, Р, 8)-~не леворекурсивная грамматика и По, rti, ..., Л/, ... -последовательность совместимых с W частичных левых разборов. Допустим, что ни один из разборов zi, ..., Til не является левым разбором цепочки w. Пуапь Sj.a и 5л.=Фр. Запишем а и в виде хщ и yt соответственно, где каждая из цепочек и pj-либо е, либо начинается

нетерминалом. Тогда в алгоритме 4.1

(q, 1, е, 5$) (q, j,, у,, а,) [-* {q, у,, Pi$)

где /i = I I + 1, /2 = I i 1 + 1, Vi " Тз описывают соответственно

я,- и 7ti + i.

Доказательство. Доказательство проводится индукцией по I. Базис, 1 - 0, тривиален. Для доказательства шага индукции рассмотрим отдельно два случая.

Случай 1: п. - продолжение разбора л. Пусть первый символ цепочки - это нетерминал А, а его альтернативы - 61, ..., 6yj. Если цепочка x6j- не совместима с входной цепочкой, то в случае замены алгоритмом 4.1 нетерминала А цепочкой бу правила (г), (д) и (е i) гарантируют, что следующей будет испытана альтернатива 6y j. Так как мы предположили, что п- - продолжение разбора п,-, то нужная альтернатива нетерминала А впоследствии будет испытана. После того как по правилу (б) произойдет сдвиг по входу, будет достигнута конфигурация {Я> 72. Pi$)-

Случай 2: n+j-модификация разбора л,-. Все неиспытанные альтернативы нетерминала А сразу приводят к возврату, и по правилам (д) и (е iii) содержимое магазина L1 в конце концов будет описывать частичный левый разбор Лу, упоминаемый в определении модификации. Тогда, как в случае 1, будет достигнута конфигурация (q, j.„ у, Pi$). □

Теорема 4.1. Алгоритм 4.1 дает левый разбор цепочки w, если он существует, а в противном случае выдает сообщение об ошибке.

Доказательство. Из леммы 4.3 видно, что алгоритм перебирает все совместимые частичные левые разборы до тех пор, пока не обнаружится левый разбор входной цепочки или не будут исчерпаны все совместимые частичные левые разборы. По лемме 4.2 число таких разборов конечно, так что алгоритм рано или поздно остановится. □

4.1.4, Временная и емкостная сложность нисходящего анализатора

Рассмотрим вычислительную машину, у которой емкость памяти, необходимая для хранения конфигураций алгоритма 4.1, пропорциональна сумме длин обоих магазинов; это предположение вполне разумно. Разумно также предположить, что время, затрачиваемое на вычисление конфигурации С по конфигура-нии С, если Cfh-Cg, не зависит от этих конфигураций. Покажем, что при этих предположениях алгоритм 4.1 требует линей-





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.0022