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

(1) 6(9, а, ) = {((?, а)} для всех а 2. (На этих тактах входные символы переносятся в магазин.)

(2) Если Л->а принадлежит Р, то 6{q, е, а) содержит (д, Л).

(3) 6(q, е, $S) = {(r. е)}.

Покажем, что процесс вычисления в автомате R заключается в построении правовыводилшх цепочек грамматики G, начиная с терминальной цепочки (на входе R) и кончая цепочкой 5. Индукцией по п докажем, что

(2.5.3) S*aAyrXy влечет {q, ху, $)-*(9. $)

Базис, п = 0, тривиален: R не делает ни одного такта. Предположим, что (2.5.3) верно для всех значений параметра, меньших п. Можно написать aЛr/=:>.ap r""л;y. Допустим, что цепочка ар состоит только из терминалов. Тогда ар -л: и {д, ху, $)Н*(9, у, $а)\-{д. У, $аЛ).

Если ар2*, то можно писать a=yBz, где В - самыйпра-вый нетерминал. По (2.5.3) из S =гуВгу г~ху следует {д,ху,$)\-* [д. zy, $уВ). Кроме того, (д, zy, %yB)Y-*{q, у, %уВг)\-(q, у, $аЛ) - тоже возможная последовательность тактов.

Мы заключаем, что (2.5.3) верно для всех п. Так как (д, е, $5)1-(г, е, е), то L{G)L(R).

Для того чтобы доказать обратное включение L{R)L{G) и, следовательно, равенство L {G)L{R), докажем, что

(2.5.4) [д, ху, $)Н"(9, у. $аЛ) влечет аЛу*ху

Базис, п = 0, выполняется автоматически. Для проверки шага индукции предположим, что (2.5.4) верно для всех /г<т. Если верхний символ магазина автомата R нетерминальный, то последний такт был сделан по правилу (2) определения функции 6. Поэтому можно писать

[д, ху, $)Ь"~Ч9. У $аР)1-(?, У, $аЛ)

где Л-vp принадлежит Р. Если цепочка ар содержит нетерминал, то по предположению индукции ajy=*xy. Отсюда аЛ;/ ар1/г*х(/, что И утверждалось.

В качестве частного случая утверждения (2.5.4) получаем, что [q, W, $)!-*((?, е, $5) влечет 5г*йУ. Так какдопускает W только тогда, когда (9, w, $)H*(?» $)\-~{г, е, е), то отсюда следует, что L (R) (G). Таким образом, L {R) = L(G).\J

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

Тогда R может сделать следующую свертку. Синтаксический анализ этого типа называют „восходящим анализом" („анализом снизу вверх") или „анализом сверткой".

Пример 2.36. Построим восходящий анализатор ) R для грамматики G. Пусть i? -расширенный МП-автомат ({q, г}, 2, Г, б, q, $, {г}), где б определяется так:

(1) 6(9, Ь,е) ={(9, Ь)} для всех Ь{а, +, *, (,)};

(2) 6(9, е, £ + Г) = {(9, Е)} б(?. е. Т) {{д, Е)] 6(9, е, TF) ={(9, Г)} 6(9, е, F) ==.((9, Т)} 6(9, е, [Е)) 1(9, F)} b(q,e,a) -{(9, £)};

(3) 6(9, е, %Е) =.((г, в)}.

Для входа a + a*fl распознаватель R может сделать следующую последовательность тактов:

(9, a4-a*Q, $)[-(9, +Q*a, %а) \-{q, %F)

h-(9, $Г)

\-(q, $£")

1-(9, а»а, $£ + ) \-{q, *а, %Е-а) \-(q, $£ + £) \~q, *д, $£ + Г)

$£Ч-Г-) 1-(9, е, %ЕТа)

%ETF)

\-{д, е, %Е) h- (г. е, е)

Заметим, что для входа ааа распознаватель R может сделать много различных последовательностей тактов. Однако выписанная последовательность - единственная, которая переводит начальную конфигурацию в заключительную. □

Покажем теперь, что язык, определяемый МП-автоматом, контекстно-свободен.

Лемма 2.26. Пусть R = {Q, S, Г, 6, 9,,, Z, Р)-МП-аетомат, Можно построить такую КС-грамматику G, что L(G) = L{R).

) Автомат, который строится в этом примере (а также и в примере 2.34),- это еще не анализатор, а только распознаватель, но его легко превратить S анализатор (см. гл. 4 и 5). -Прим, перев.



Доказательство. Построим G так, чтобы левый вывод цепочки W в грамматике G прямо соответствовал последовательности тактов, которую делает R при обработке цепочки w. Нетерминальные символы будут иметь вид [qZr], где rQ и Zr. Потом мы покажем, что [gZrJw тогда и только тогда, когда {д, w, Z) [-+ (г, е, е).

Формально пусть G = (N; 2, Я, 5), где

(1) N = {[Zr], r€Q,Z€r}U{5};

(2) правила множества Р строятся так:

(а) если д{д, а, Z) содержит (г, Х.. .XfY) (ft> 1), добавим к Р все правила вида

№a]-«[/-X,sJ[SiX,S2]. .

для каждой последовательности s, Sg, ..., состояний из Q,

(б) если &{g,a,Z) содержит (г, е), добавим к Р правило [gZrJ-a,

(в) добавим к Р правила S~[q(Zf,g] для каждого gQ.

Индукцией по т я п легко доказать, что для любых grQ и 2€Г

[qZrlw тогда и только тогда, когда (д, w, Z)\-" {г, е, е).

Доказательство оставляем в качестве упражнения. Из этого утверждения следует, что S [gZg] w тогда и только тогда, когда {д, w, Z)!-е, е) для gQ. Таким образом, L,{R) = L{G). □

Результаты двух последних разделов можно сформулировать в виде следующей теоремы:

Теорема 2.21. Утверждения

(1) LL(G) для КС-грамматики G,

(2) LL(Pi) для МП-автомата Р,

(3) L = L{P.) для МП-автомата Я,

(4) L = L (Ps) для расширенного МП-автомата Р

эквивалентны.

Доказательство. Из (3) следует (1) по лемме 2.26. Из (1) следует (3) по лемме 2.24. Из (4) следует (2) по лемме 2.21, а (4) тривиально следует из (2). Из (2) следует (3) по лемме 2.22, и нз (3) следует (2) по лемме 2.23. □

) Верхний символ магазина R расположен слева, так как мы не оговаривали противное.

2.5.4. Детерминированные МП-автоматы

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

Язык, определяемый детерминированным МП-автоматом, называется детерминированным КС-языком. В гл. 5 мы введем подкласс КС-грамматик, называемых ЬН(/г)-грамматиками, а в гл. 8 покажем, что каждая ЬН(/г)-грамматика порождает детерминированный КС-язык и каждый детерминированный КС-язык определяется ЬК(1)-грамматикой.

Определение. МП-автомат P = (Q, 2, Г, б, Z, F) называется детерминированным (сокращенно ДМП-автоматом), если для каждых д £Q и Z € Г либо

(1) b(g,a,Z) содержит не более одного элемента для каждого а€2 и Ь(д,е, Z) = 0, либо

(2) б((7, а, Z) -0 для всех 02 и b(g,e,Z) содержит ие более одного элемента.

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

Соглашение. Так как для ДМП-автомата б (д, а, Z) содержит не более одного элемента, мы будем писать б (9, а, Z) (г, у) вместо Ь(д, а, Z)-{(r, у)].

Пример 2.37. Построим ДМП-автомат, распознающий язык L = {wcwR\w£ {fi, Пусть Я = ({9о. Яг) 4»

о, Z, {(?з}), где б определяется так;

б X, К) = (0, ХУ) для всех Х£{а,Ь] и К € {Z, а, Ь}

б (q, с. У) = (д, У) для всех У 6 {а, Ь] б ((?1, X, X) - (9, е) для всех X {а, Ь}

6(qi,e,Z) = (q„e)



До тех пор пока Р не увидит маркер с, отмечающий середину, он запасает в. магазине символы входной цепочки. Когда Р достигает с, он переходит в состояние и далее сравнивает оставшуюся часть входной цепочки с содержимым магазина. Доказательство того, 4toL(P)--L, оставляем в качестве упражнения. П

Определение детерминированного МП-автомата можно естественным образом расширить, чтобы включить в него те расширенные МП-автоматы, которые естественно считать детерминированными.

Определение. Расширенный МП-автомат P{Q, S, Г, б, Zq, F) называется детерминированным, если выполнены следующие условия:

(1) #6(9, а, у)<1 для всех 9€Q, Q€2u{e} и у€Г*;

(2) если 6 (9, g, О1.)Ф0, б (9, а, р) 0 и аф, то ни одна из цепочек а и р пе является суффиксом другой

(3) если 6(9, д, а) 0 и 6(9, е, р)0, то ни одна из цепочек а и р не является суффиксом другой.

Легко видеть, что в том частном случае, когда расширенный МП-автомат является обычным ДМП-автоматом, это определение согласуется с прежним. Кроме того, если конструкция леммы 2.21 применяется к расширенному МП-автомату, результатом будет детерминированный МП-автомат тогда и только тогда, когда детерминированным был исходный расширенный МП-ав-томаг.

При моделировании синтаксического анализатора желательно иметь ДМП-автомат Р, считывающий всю входную цепочку, даже если она не принадлежит языку L{P). Покажем, что такой ДМП-автомат всегда можно найти.

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

Лемма 2.27. Пусть P = (Q, S, Г, 6, 9о, F) -ДМП-автомат. Можно построить такой эквивалентный ЦМП-автомат Р = = (Q, S, Г, 6, 9;,Zo, F), что

(1) для всех аТ., qQ и ZV либо

(а) 6 (9, а, Z) содержит точно один элемент и б (9, е, Z) -= 0, либо

Если верх магазина расшнреииого МП-автомата расположен слева, то здесь надо заменить „суффикс* на „префикс".

(б) 6 (9, а, Z) = 0 и б (9, е, Z) содержит точно один элемент;

(2) если Ь(q, а, Zq) = {г, у) для некоторого aItUle}, то Y = ctZo для некоторой цепочки аГ*.

Доказательство. Символ Zq будет действовать как маркер, указывающий конец (дно) магазина и предотвращающий полное опустошение магазина. Пусть Г Г U {Zq} и Q = = {?о. ?c}UQ, а б определяется так:

(1) 6(9;, е, Zo) = (9o, ад);

(2) для всех 9 € Q, « € S и {е}- и Z Г, таких, что б (9, а, Z) Ф 0, полагаем 6 (9, а, Z) б (9, а, Z);

(3) если 6(9, , Z) = 0 и d{q, а, Z}~ 0 для некоторых gS и Z € Г, полагаем б (9, а, Z) = [q, Z);

(4) для всех ZV и полагаем Ь (q, а, Z) = (q, Z).

Благодаря правилу (1) Р запишет в верхней части магазина ZqZo и, перейдя в состояние 90, начнет моделировать Р. Правила (2) позволяют Р моделировать Р, пока очередной такт станет невозможным. В этой ситуации Р- (по правилу 3) перейдет в незаклгочнтельное состояние q и останется в нем, не изменяя содержимого магазина, пока не будет прочитана оставшаяся часть входа. Доказательство того, что L[P) = L(P)t оставляем в качестве упражнения. □

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

Определение, Конфигурация (9, w, а) ДМП-автомата Р называется зацикливающей, если для каждого 11 найдется такая конфигурация [pitW, р,-), что pj>a и

(9, W, а) 1- {pi, W, Pi) Н (Ра. w,)\- ...

Таким образом, конфигурация зацикливающая, если Р может делать бесконечное число е-тактов, не укорачивая магазин; при этом магазин может либо бесконечно расти, либо циклически совпадать с несколькими различными цепочками.

Заметим, что существуют иезацикливающие конфигурации, Которые после ряда (?-тактов, укорачивающих магазин, переходят в зацикливающую конфигурацию. Мы покажем, что нельзя сделать бесконечное число е-тактов, исходя нз любой данной конфигурации, не попав через конечное и притом вычислимое ЧИСЛО тактов в зацикливающую конфигурацию.

Если Р попадает в зацикливающую конфигурацию в середине входной цепочки, то он больше не будет использовать





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