Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 40
Текст из файла (страница 40)
с: — Е (Р). Несколько труднее доказать, что если (д„а2,Е)( — '(д„е,а) для некоторого аЕ Г', то а2=ххй для некоторого хЕ(а+Ь)+ и а=е. Оставляем доказательство в качестве упражнения и, считая это утверждение истинным, заключаем, что Е(Р)= — Т,. Е1 В примере 2.32 ясно видна недетерминнрованная природа МП-азтОМата Р. ДЛя ЛЮбОй КОНфИГурацИИ ВИда (до,а2е,аа) азтомат Р может сделать один нз двух тактов: либо поместить в магазин еще один символ а, либо устранить из магазина верхний символ а. Подчеркнем, что хотя иедетермииированный МП-автомат может обеспечивать удобное абстрактное определение языка, для реализации на практике нужно промоделировать его детермииированно.
В гл, 4 мы рассмотрим методы моделирования не- детерминированных МП-автоматов. 197„ ним (и единственным) символом магазина, то по правилу (9) Р стирает 3 и попадает в состояние д,. Итак, Р допускает цепочку тогда и только тогда, когда все сравнения обнаружили совпадение символов. Например, для входной цепочки аЬЬа автомат Р может среди прочих сделать следующие последовательности тактов: ГЛ, 2.
ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ (в,зс, А) )- л~ (ды гпм Хг... Х ) (д„гп„Хз... Хл) лв (у 1с Х сз) и (~', в) 19В 199 2.5.2. Варианты МП-автоматов В этом разделе мы Определим некоторые варианты понятия МП-автомата и установим связь между определяемыми ими языками и языками, определяемыми МП-автоматами в смысле первоначального определения. Но сначала нам хотелось бы выявить один фундаментальный аспект поведения МП-автомата, который интуитивно представляется совершенно ясным. Вго можно сформулировать так: „То, что происходят с верхним символом магазина, не зависит от того, что находится в магазине под ним".
Лемма 2.20. Пусть Р=(1~,2, Г, б, д„ХЫ Р) — МП-автолзат. Если (и, гс, А)( — "(в',е,е), то (в,2п, Асс) ) — "(с)',в, сс) для всек А ЕГ и ссЕГ'. Д о к а з а т е л ь с т в о. Доказательство индукцией по и довольно элементарно. Для и=-1 лемма, очевидно. верна. Допустим, что она верна для всех 1 ='п<п', и пусть (д,гс,А)) — "'(д',е,в). Тогда соответствующая последовательность тактов должна иметь вид ( — "з-г(в», геа, Ха) — (д', в, в) где Й) 1 и и, < и' для 1<1<6 2). Тогда для любых аЕ Г' также возможна последовательность (д, гп, Асс) ) — (д„ы>„Х,...ХАО) (Чз! Ша~ Хз 'ХАСС) ') Зто еще один пример „очевидного" утверждения, которое молсет но- требовать некоторого размышлення.
Представьте себе й1П-автомат, проходящий указанную последовательность яонфнгурацнй. Рано нлн поздно длнна мага- Х...Х н винной цепочки впервые станет равной л — !. Так как нн од А не был верхним символам магазина, онн так н останутся в нем, так что лз — число сделанных к атому моменту тактов. Затем ждем, ко магазина впервые станет равной й — 2, н берем в качестве л, чнсло дополнидем, когда длина тельно потребовавшихся тактов. Продолжаем в том же духе станет пустым, 2.З, АВТОМАТЫ С МЛГАЗИННОН ПАМЯТЬЮ Всюду, кроме первого такта, мы пользовались здесь предположением индукции, () Теперь мы слегка расширим определение МП-автомата, позволив ему заменять за один такт цепочку символов ограничениой длины, расположенную в верхней части магазина, другой цепочкой конечной длины.
Напомним, что МП-автомат в первоначальной версии мог на данном такте заменять лишь один верхний символ магазина. Определение. Расширенныл МП-автоматом назовем семерку Р=-(1с, Х, Г, б, дз, Х„Р), где б — отображение конечного подмножества множества 1~к(Х 0(е))х Г" в множество конечных подмножеств множества ОхГ*, а все другие символы имеют тот же смысл, что и раньше.
Конфигурация определяется так же, как прежде, и мы пишем (в,азс,ау) ( — (и', ге,()у), если 6(в, а,а) содержит (и',6), где д6(), а бХП(е) и се ~ Г'. В этом такте цепочка сз, расположенная в верхней части магазина, заменяется цепочкой 6. Как и прежде, языком Е(Р), определяемым автоматом Р, называется множество (2с ~(д„гп, Х,) ) — '(в, в, сс) для некоторых и ~Р и сс ЕГ') Заметим, что в отличие от обычного МП-автомата расширенный МП-автомат обладает способностью продолжать работу и тогда, когда магазин пуст.
Пример 2.33. Определим расширенный МП-звтомат Р, распознающий язык Е =-(гпгпа) 2ЭЕ (а, Ь)'). Пусть Р=((д, р), (а, Ь), (а, Ь, 5, Х), б, и, Х, (р)), где (1) б (у, а, в) = ((у, а)) (2) б (у, Ь, е) = ((д, Ь)) (3) б (д, в, е) = ((д, 5)) (4) б (у, в, аЕа) = ((д, Е)) (5) б (д, е, ЬЕЬ) .= ((4, О)) (6) б (у, е, ЕХ) = ((р, е)) На входе ааЬЬаи автомат Р может сделать следующую последовательность тактов: (д, ааЬЬаа, Х) ',— (и, аЬЬаа, аХ) (у, ЬЬаа, ааХ) )- (д, Ьаи, ЬааХ) (- (д, Ьаи, ЕЬааХ) ) — (д, аа, ЬЕЬааХ) гл. к элвмвнты твогии языков » — (д, аа, 5ааЕ) »- (д, а, а5ааХ) »- (д, а, 5аХ) » — (д, е, а5аЯ) » — (д, е, 5А) » — (р, е,е) Работа автомата Р состоит в том, что вначале он запасает в магазине некоторый префикс входной цепочки.
Затеи верхним символом магазина делается маркер 5, указывающий предполагаемую середину входной цепочки. Далее Р помещает в магазин очередной входной символ и заменяет в магазине а5а илн Ь5Ь на 5. Автомат Р работает до тех пор, пока не исчерпается вся входная пепочка. Если после этого в магазине останется 57, то Р сотрет 5Х и попадет в заключительное состояние. Покажем, что язык Т.
определяется МП-автоматом тогда и только тогда, когда оп определяется расширенным МП-автоматом. Необходимость условия очевидна; докажем достаточность. Лемма 2.21. Пусть Р = Я, Х, Г, 6, у„Х„Р) — растиренныб МП-автомат. Тогда существует такой МП-автомат Р„что 7-(Р1) =Т (Р). Доказательство. Положим т=-шах(~я~~6(о,а,я)чьй для некоторых цЕЯ, а ЕГО(е»». Построим МП-автомат Р„который будет моделировать автомат Р, храня верхние т символов его магазина в „буфере" длины гп, занимающем часть конечной памяти управляющего устройства автомата Р,.
Тогда Р, сможет сказать в начале каждого такта, каковы т верхних символов магазина автомата Р. Если в некотором такте Р заменяет й верхних символов магазина цепочкой из ( символов, то Р, заменит й первых символов в буфере этой цепочкой длины (. Если ( < й, то Р, сделает й — 1 вспомогательных е-тактов, в течение которых й — ( символов перейдут из верхней части магазина в буфер управляющего устройства.
После этого буфер окажется заполненным, и Р, готов моделировать очередной такт автомата Р. Если () й, то символы передаются из буфера в магазин. Итак, положим Р,=Я„Х, Г„б„ог,7.„Р,) где ()) Ю,=([у,я1»ЧЕЯ, яЕГ,", 0<»я»<т»; (2) Г, = Г 0 (7, »; (3) 6, определяется так: (а) Допустим, что 6(у, а, Х,...Х„) содержит (г, )'...У). (() Если (= й, то для всех ЛЕГ, и яЕГ;,»я»=т — й, 6, ([у, Х,... Хья|, а, 7) содержит ([г, Я, у2) 2.В. АВТОМАТЫ С МАГАЗИНГЮЙ ПАМЯТЬГС где»)у = У,... У,я н» р» = т. я»=т — й, (В) Если ( < й, то для всех 7 Е Г, и я Е Г;, » я» =т — ° 6,([у, ХТ...ХАя1,а, Я) содержит ([г, Уг УР71 е) (б) для всех ЧЕЙ, ЛЕГ, и яЕГг, »я» <т, 6, ([у, я1, е, 7) = (([д, я71, е)» Эти правила осуществляют заполнение буфера управляющего устройства, которой содержит т символов.
(4) д =-[д„7,Е,"-'». В начальный момент буфер содержит 7, наверху и т — символов 1 ов 7 пониже. Символы 7~ испольй зуются как специальные маркеры, отмечающие,дно', т, е. ниж- ний конец магазина (5) Р,=([о, я1»а бр, яЕГЦ. Нетрудно показать, что тогда и только тогда, когда ([д, я], аш, р)» — р,([, '1,, й', (П ()=Х,...Х„2„-, (2) я'))'=У,...У,Хь,., Х„Щ (3) (я)=)я' (=т, (4) между двумя указанными конфигур ц а иями МП-автомата Р, иет нн одной конфигурации, состояние которой имело ы вторую компоненту (буфер) длины т. Для этого достаточно непосредственно применить правила, Таким образом, (д„ш, 7„) ~ — р (д, е, я) для некоторых д С о ых бри яЕГ' тогда и только тогда, когда Ф„7,7Г- 1, ~,7,)»-',([у, И, е, у) где )Д»=т и Ду=я7,, Отсюда Т.(Рг)=Т.(Р).
П Теперь исследуем входные цепочки, заставляющие МП-авто- мат опустошать магазин. Определение. Пусть Р = — Я, Г, Г, 6, д„„)— Я Р) — МП-автомат или расширенный - в " МП-автомат, Будем говорить, что Р допускает цепочку и Е г,' опустошением магазина, если (д„ш,,),— (д,, для некоторого у ЕЯ.
Пусть г. (Р) — множество цепочек, допус- каемых автоматом Р опустошением магазина, Лемма 2.22. Пусть 6=1,(Р) для некоторого МП-автомата Р=( г, Е, Г, 6, о„Я„Р). Можно построить такой МП-автомагп Р, что Е.,(Р')=Е„ Д о к а з а т е л ь с т в о. Пусть Р' моделирует Р. Всякий раз, Когда Р переходит в заключительное состояние, ' решает, про- 201 ГЛ. 2.
ЗЛРМПНТЫ ТВОРИИ ЯЗЫКОВ 2.2. АВтомАты с мАГАзш|ной пАмятью должать ли моделирование Р или перейти в специальное состояние д„которое опустошит магазин. Но есть одно осложнение. Для некоторой входной цепочки ш автомат Р может сделать последовательность тактов, приводящую к опустошению магазина, а управляющее устройство окажется при этом не в заключительном состоянии. Тогда для того, чтобы помешать Р' допустить в этом случае цепочку ш, добавим к Р' специалы|ый маркер, отмечающий дно магазина, который автомат Р' может устранить только в состоянии 4,. формально положим Р'=- (ась(аю а'), л„Г()(2'), 6', а', 2', 0)'), где 6' определяется так: (1) если 6(а, а, 2) содержит (г, у), то 6'(а, а, 2) содержит (г, у) для всех у Е |е, а ЕХ 0(е) и ЛЕГ; (2) 6'(д', е, 2')=((а„2»7')), т.
е. иа первом такте автомат Р' записывает в магазин 2»2' и переходит в начальное состоянне автомата Р(Т играет роль маркера, отмечающего дно магазина); (3) для всех дЕР и ЛЕГО(7') множество 6'(д, е, 2) содер. жит (д„е); (4) 6'(|4, е, 2) = — -((д„е)) для всех ЛЕГ(?(2'). Легко видеть, что (у' м 2'))-р (уа, ш,2е2') '| р,(а, е, ?;...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
