Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 39
Текст из файла (страница 39)
Алгорятм 2.!5 н результат, сформулнронанный я упр. 2.4.30, прянлдлежлз Розенкрлнпу [19671, Алгоритм 2.14 прнпнсывают М. Паулу. Представление КС-языков с помощью систем уранненнй нспользовллось в рлботэх Хомского [!963[, Хомского н Шютпепберже [!9631, Гинзбурга н Рлйса [1962!. Операторные грамчатнкн впервые рессмотрены Флойдом [1963[. Пормальныс формы, прнпеденные в упр. 2.4.26 — 2.4.26, были получены Грейбех [1965!. 2.5. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ Теперь мы введем понятие автомата с магазинной памятью— тип распознавателя, представляющий собой естественную модель синтаксических анализаторов контекстно-свободных языков.
Автомат с магазинной памятью — это односторонний недетерминированный распознаватель, в потенциально бесконечной памяти которого элементы информации хранятся н используются так же, как патроны в магазине автоматического оружия, т. е. в каждый момент доступен только верхний элемент магазина. Распознаватель этого типа изображен па рис. 2.13, щщ лвтомлты с млглзиннон плмягью Мы докажем адин фундаментальный результат, относящийся к автоматам с магазинной памятью, а именно: язык контекстно- свободен тогда и толька тогда, когда он допускается недетерминированпым автоматом с магазинной памятью. Рассмотрим также Рнс.
2.15. Автомат с магазинной памятью. один подкласс КС-языков, особенно важный с точки зрения ана- лизируемости языков. Он состоит из детерминированных КС-язы- ков, т. е. языков, распознаваемых детерминированными автома- тами с магазинной памятью, 2.5.1. Основное опреАепение Будем представлять магазин (или магазинный список, илн магазинную ленту) в виде цепочки символов, причем верхним элементом магазина будем считать самый левый или самый правый символ цепочки в зависимости от того, чтб удобнее в данной ситуации, Пока будем считать верхним самый левый символ цепочки, представляющей магазинный список. Определение.
Авгпомпт с мпгпзияной ппмяпгью (сокращенно [)ТП-автомат) †э семерка Р = (О, Х, Г, б, 4„ г„ Р) где (1) Я вЂ конечн множество символов соспзояний, представляющих всевозможные состояния управляющего устройства; (2) Š— конечный входной плфпвит; (3) à — конечный алфавит магазинных символов; А. Ахо, дж, Ульыаы. е, ! 193 ГЛ, 2 ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ (4) 6 — отображение множества»ум(Х(у(е))мГ в множество конечных подмножеств множества»УКГ*; (5) Ч,Е (у — н чальное состояние управляющего устройства; (6) Я, Šà — символ, находящийся в магазине в начальный момент !начальный символ); (У) Р с=»е — множество зпключительных состояний.
Конфигурацией МП-автомата Р называется тройка (Ч, и», а) Е !чхХ*мГг, где (!) Ч вЂ” текущее состояние управляющего устройства; (2) т — неиспользованная часть входной цепочки; первый символ цепочки и» находится под входной головкой; если и»= е, то считается, что вся входная лента прочитана; (3) а — содержимое магазина; самый левый символ цепочки и считается верхним символом магазина; если а=е, то магазин считается пустым. У)тнт работы МП-автомата Р будем представлять в виде бинарного отношения ',— (или )-, когда Р подразумевается), определенного на конфигурациях.
Будем писать (2.5.1) (Ч, аш, 2и)) — (Ч', т, уа) если множество 6 (Ч, а, 2) содержит (Ч', у), где Ч, Ч' Е !ч', а Е л' (у (е), и» Е 2'*, 2 Е Г и а, у Е Г'. Если а~ *, то (2.5.!) говорит о том, что МП-автомат Р, находясь в состоянии Ч н имея а в качестве текущего входного символа, расположенного под входной головкой, а Š— в качестве верхнего символа магазина, может перейти в новое состояние Ч', сдвинуть входную головку на одну ячейку вправо и заменить верхний символ магазина цепочкой у магазинных символов.
Если у=е, то верхний символ удаляется из магазина, и тем самым магазинный список сскршцаетсж Если а=е, будем называть этот такт е-таюполи В е-такте текущий входной символ не принимается во внимание и входная головка не сдвигается. Однако состояние управляющего устройства и содержимое памяти могут измениться. Заметим, что е-такт может происходить и тогда, когда вся входная цепочка прочитана.
Следующий такт невозможен, если магазин пуст. Можно обычным образом определить отношения ) — 'для 1~0, 1 — ' и ) —, а именно: ) — ' и ) — ' — это соответственно рефлексивно-транзитивное и транзитивное замыкания отношения ' Начальной конфигурацией МП-автомата Р называется конфиГурацня ВИда (Ч„Ш, 2,), ГдЕ и»Е Хг, т.
Е. унраВЛявщЕЕ уетрОЙ- ство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в магазине есть только ым 2Л. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ начальный символ Е,. Заключительная конфигурация — это конфигурация вида (Ч,е,а), где ЧЕ Р н 55ЕГ*.
Говорят, что цепочка и» допускается МП-автоматом Р, если (Ч„, нц с,))-*(Ч, е, а) для некоторых ЧЕР и аЕГ'. уузыкол2, определяемым (или дон ускаемьси ) автоиатом Р (обозначается У. (Р)), называют множество цепочек, допускаемых автоматом Р. Пример 2.31. Построим МП-автомат, определяющий язык У, = (О" 1" (п 2»0). Пусть Р =-((Ч„Ч„Ч,), (О, 1), (Е» 0), 6, Чг» 2» (Чг))» где 6(Ч„О, 2') =-((Ч ОХ)) 6(ч,', о, о) =-((ч„оо)) 6(Ч„1, О) ((Чм ь) 6 (чг» 1» 0) =((чг» е) 6 ( у„е, 2) = ((Ч е)) Работа МП-автомата Р состоит в том, что он копирует в магазине начальную часть входной цепочки, состоящую нз нулей, тем устраняет из магазина по одному нулю на каждую единицу, которую он видит иа входе. Кроме того, переходы саста яний гарантируют, что все нули предшествуют единицам.
Например, для входной цепочки 0011 автомат Р проделает такую последовательность тактов: (ч„ооп, х);-(ч„о11, и) ')- (Ч„11, 002) )- (Ч„1, ок) ) — (ч„е, Х) )-(Чг, е,' е) Вообще можно показать, что (у„О, Е) ! — (Ч„е, ОЕ) (ч„'о', 'ол) ) — '(ч," .', о'-Х) (Ч„1, 0'г'Е) )- (Ч„е, 0'л.) (Ч„, 1', 0'Е) )-' (Ч„е, Е) (Ч„е, ь) )- (Ч„е, е) Объединял все это, получаем для п) 1 (Чм 0"1", Е)! — 2"+2(Ч„е, е) и (ч„, е, Е) ! — '(Ч„е, Е) Таким образом, у. с= у(Р), Покажем, что у, ~ у,(Р), т. е. что Р допускает только цепочки вида 0'1". Эта часть доказательства труднее. Обычно легче доказать, что такие-то цепочки распознаватель допускает, и так Тг 199 ГЛ.
2. ЭЛЕМЕНТЫ ТЕОРИЙ ЯЗЫКОВ 2.5. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ же, как для грамматик, гораздо труднее доказать, что он допускает цепочки только определенного вида. В данном случае заметим, что если Р допускает непустую цепочку, то ои должен пройти через состояния д„ д„ д„ д, именно в этом порядке. Далее, если (д„ю, е)1 — '(д„е, а) для () 1, то 2с= 0' и а=023. Аналогично, если (д„щ,а),' — '(д„е, р), то Н2=12 н а=Ор. К тому же (д„а2, а) (-(д„е, ()) только тогда, когда а2=1 и а=-Ор, а (д„а2, с) 1 — *(д„е, е) только тогда, когда 2с=-е. Таким образом, если (д„ш,2)) — '(д„е, а) для некоторого 1~0, то либо а2=е и 4=0, лйбоа2=0о1",1== 2п+1, па — е. Следовательно, 7 л7(Р).
(2 Подчеркнем еще раз, что МП-автомат, как мы его определили, может продолжать работу (делать е-такты), даже если он прочел уже всю входную цепочку. Но он не может сделать следующий такт, если его магазин пуст. Пример 2.32. Построим МП-автомат, допускающий язык Т.=(ахеи(а2Е (а, Ь)+) Пусть Р=-((д„д,„д,), (а, Ь), (с,а, Ь), 6, д„3, (до)), где (1) 6(до а*3) =((до,а~)) (2) 6(д„Ь,г)=((д„ЬА)) (3) 6(д.,а,а)=((д..
),(дмеН (4) 6(д„го, Ь) =(д„аь)) (5) 6 (д„Ь, а) = ((д„Ьа) ) (6) 6 (д„Ь, Ь) = ((д„ЬЬ), (д,, е)) (7) 6 (д„а, а) =((д„е)) (8) 6(д„, Ь, Ь)=((д, еН (9) 6 (д„е, 3) = ((д„е)) МП-автомат Р вначале копирует в магазине какую-то часть входной цепочки по правилам (1), (2), (4) и (5) и первым альтернативам правил (3) и (6). Однако Р— недетерминированный распознаватель. В любой момент, когда ему захочется, лишь бы текущий входпон символ совпадал с верхним символом магазина, он может перейти в состояние д, и начать сравнивать цепочку в магазине с оставшейся частью входной цепочки. Этот выбор осуществляют вторые альтернативы правил (3) и (Б), а по правилам (7) и (8) происходит сравнение.
Если Р обнаруживает несовпадение очередных символов, то этот экземпляр МП- автомата Р „умирает", т. е. перестает работать. Однако, так как автомат Р— недетсрмииироваииый, то разные его экземпляры могут делать все возможные для него такты. Если какой-то выбор тактов приводит к тому, что 2 снова оказывается верх- гэо (!) (д„аЬЬа, 2) )- (д„ЬЬа, а2) ( — (д„Ьа, Ьа_#_) ( — (до, а, ЬЬас) ( — (д„ е, аЬЬаЦ (2) (д„аЬЬа, Е) (-(д„ЬЬа, аЕ) ( — (д„Ьа, ЬОЕ) ( — (д„а, ас) 1 — (д,, е, Х) ( — (д„е, е) Так как последовательность (2) оканчивается заключительным состояняем д„то МП-автомат Р допускает входную цепочку аЬЬа. Как и райьше, относительно легко показать, что если и=. с,с,...с„с„с„2...см где с,Е(а,Ь) для 1:.2 .и, то (дОо оео С) 'Г и-А (д„с„с„,...см с„с„,...с,Е) (д,, с„2...с;, с„т...с„х) (д„е, Е) (д„е, е) Таким образом, Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
