Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 43
Текст из файла (страница 43)
Легко видеть, что в том частном случае, когда расширенный МП-автомат является обычным ДМП-автоматом, это определение согласуется с прежним. Кроме того, если конструкция леммы 2.2! применяется к расширенному МП-автомату, результатом будет детерминированный МП-автомат тогда и только тогда, когда детерминированным был исходный расширенный МП-автомат.
При моделировании синтаксического анализатора желательно иметь ДМП-автомат Р, считывающий всю входную цепочку, даже если она не принадлежит языку Е(Р). Покажем, что такой ДМП-автомат всегда можно найти. Сначала модифицируем ДМП-автомат так, чтобы для любой конфигурации, В которой часть входа осталась непрочитанной, был всегда возможен очередной такт. Следующая лемма показывает, как это сделать.
Лемма 2.27. Пусть Р= (!е, Х, Г, 6, д„7е, Р) — ДМП-автомат. Можно построить такой зквивалентный ДМП-автомшп Р' = = ф', Х, Г, 6', д;, 7;, Р), что (1) для всех а ЕХ, ЗАЕЦ' и 7. Е Г' либо (а) 6' (д, а, 7) содержит точно один элемент и 6' (д, е, Я) —— Я, либо ') Если верх магазина пасшнренного МП-аззомата расположен слеза, то здесь надо заменнть „суффикс" на „префикс", (б) 6 (г), а, 7) = и и 6' (д, е, У) содержит точно один злемент; (2) если 6'(д, а, 7е)=(г, Т) для некоторого аЕХ(!(е), то у=а7; для некоторой цепочки сзЕГз.
Доказательство. Символ 7; будет действовать как маркер, указывающий конец (дно) магазина и предотвращающий полное опустошение магазина. Пусть Г' == Г 0 (У;) и !е' =- =- (о,', о,) 0 9, а 6' определяется так: (1) 6' (дз', е, 7;) = (д„лзХ,) (2) для всех оЕ!',1, аЕХ 0(е) и 7 Е Г, таких, чтоб(о, а, 2) чь О, полагаем 6'(о, а, 2) = 6(д, а, 7); (3) если 6(д,е, Я) =1~ и 6(ц, а, 7) =-)3! для некоторых а ЕЕ и 2 б Г, полагаем 6' (д, а, 7) = (д„У); (4) для всех ЛЕГ' и аЕХ полагаем 6'(д„а, Е) =-(а„7). Благодаря правилу (!) Р' запишет в верхней части магазина 7з7; и, перейдя в состояние с1„начнет моделировать Р. Правила (2) позволяют Р' моделировать Р, пока очередной такт станет невозможным. В этой ситуации Р' (по правилу 3) перейдет в незаключительпое сосгояние д, и останется в нем, не изменяя содержимого ьшгазина, пока не будет прочитана оставшаяся часть входа.
Доказательство того, что 1.(Р') =- 1.(Р), оставляем в качестве упражнения. П ДМП-автомат может, исходя из некоторой конфигурации, проделать бесконечное число е-тактов, не прочитав больше пи Одного входного символа. Такую конфигурацию мы называем зацикливающей.
Определение, Конфигурацвя (д, ш, и) ДМП-автомата Р называется заз(икливиои!ей, если для каждого 1~! найдется такая конфигурация (ро гп, бг), что )й;(~ ~)сс) и И, ш) !-( (! ))-(р. Р ))- "° Таким образом, конфигурация зациклявающая, если Р может делать бесконечное число е-тактов, не укорачивая магазин; при этом магазин может либо бесконечно расти, либо циклически совпадать с несколькими различными цепочками. Заметим, что существуют иезацикливающне конфигурации, которые после ряда е-тактов, укорачивающих магазин, переходят в зацикливающую конфигурацию. Мы покажем, что нельзя сделать бесконечное число е-тактов, исходя нз любой данной конфигурации, не попав через конечное и притом вычислимое число тактов в зацикливающую конфигурацию.
Если Р попадает в зацикливающую конфигурацию в середине входной цепочки, то он больше не будет использовать Гл. 2. алименты теОРии языков м ь лвтомлты с млглзиииой плмятью входную цепочку, даже если удовлетворяет лемме 2.27. Мы хо- тим преобразовать данный ДМП-автомат Р в эквивалентный ДМП-автомат Р', который никогда не попадает в зацикливаю- щую конфигурацию.
Алгоритм 2,16, Обнаружение за цикливающих конфигураций. Вход. ДМП-автомат Р = (1,'~, Х, Г, 6, д„2м Р). Вьпсд. (!) С,= ((д, А) !(у, е, А) — зацикливающая конфигурация и ие существует такого гЕР, что (а, е, А)', *(г, е, я) для некоторой цепочки я Е Гл) и (2) С,=((д, А)1(у, е, А) — зацикливающая конфигурация и (д, е, А) « — '(г, е, я) для некоторых г ЕР и яЕГ*). Метод. Пусть ЧГ 11==и„Фà — п, н 1 — длина самой длинной цепочки, которую Р может записать в магазин за один такт, Пусть п,=п,(п",'"а+ — п,)Яп,— 1), если и,. 1, и п,=-п,, если и,=1. Число и„— это максимальное число е-тактов, которое может сделать Р, не зацикливаясь.
(1) Для всех у Е Я и Л Е Г выяснить, выполняется ли (д, е, Л) « — "з(г, е, я) для каких-нибудь г Е11 н яЕ Г+. При этом используется прямое моделирование Р. Если да, то (а, е, А) — зацикливающая конфигурация, так как в этом случае — мы это покажем — должна быть такая пара (д', А'), где д'ЕД и А' Е Г, что (а, е, А)«-* (а', е, А'р) (д', е, Л'у«1) « — ""l о(д', е, А'Т»6) где т > 0 и 1 > О. Заметим, что у может быть е. (2) Если (д, е, А) — зацикливающая конфигурация, выяснить, существует ли такое г ЕР, что (у, е, А) « — 1(г, е, я) для некоторого 0(!'(п,.
При этом снова используется прямое модели. рование. Если да, то включить (а, А) в С, В противном случае включить (а, А) в С,. Мы утверждаем, что если Р может достичь заключительная конфигурации, исходя из (д, е, А), то это должно произойти за и, или меньшее число тактов. Е) Теорема 2.22.
Алгоритм 2.16 правильно находит множества и С,. Доказательство. Сначала докажем, что шаг (1) правильно определяет множество С,()С,. Если (д, А)ЕС,()См то очевидно, что (а, е, А) «-"з (г, е, я). Обратно, допустим, что (д, е, А) «-"з(г, е, я). Случай 1: Существует такая цепочка )! Е Г*, что 1)з)> и,п,1 и (д, е, А) « — "(р, е, Р) « — ч (г, е, я) для некоторого рЕ 11. Еслй в 214 последовательности тактов (а, е, А) « — *(р, е, 6) для каждого 1==1, 2, ..., п,и,1+1 выделить конфигурацию, в которой оказывается Р, когда длина его магазина и последний раз становится равной 1, то можно заметить, что в выделенной последовательности конфигураций некоторое состояние а' и символ А' должны дважды встречаться в качестве текущего состояния и верхнего символа магазина; другими словами, можно писать (д, е, А) «-*(д', е, А'6) « — '(у', е, Л'уб)1 "(р, е, Р). Таким образом, по лемме 2.20 (д, е.
А) ~ — * (д', е, А'6) 'г — » (у', е, Л'у»6) для всех 1'~ )О. Здесь т ) О, поэтому, исходя из конфигурации (д, е„А), можно сделать бесконечна много е-тактов и, следовательно, (д, А) Е С, 11 С,. Случай 2: Допустим, что в противоположность случаю 1 1«1)(и и! для всех таких 6, что (в, е, Л)« —" (р, е, ()) «-ч (», е, я), Так как в этой последовательности конфигураций имеется и, + 1 различных )1, число возможных состояний равно и, и число возможных магазинных цепочек длины, не большей и,п,1, равно и,+и, '1-и.",+ ... +и',""и=(п",'"''' — п,)1(п,— 1), то некоторая конфигурация должна повторяться.
Отсюда непосредственно следует, что (д, А) ЕС, ОС,. Доказательство того, что шаг (2) правильно разбивает множество С, (1С, иа С, и С„оставляем в качестве упражнения. [~ Определение. ДМП-автомат Р Я, Х, Г, 6, д„2„Р) назовем дочитывающим, если для каждой цепочки и Е Х" существуют такие рЕ11 и аЕГ'", что (д„ш, 2,) « — '(р, е, я). Интуитивно, дочитывающим называется ДМП-автомат, способный дочитывать до конца каждую входную цепочку. Лемма 2,28, Пусть Р = Я, Х, Г, 6, д„Х„Р) — ДМП-автомат. Тогда существует эквивалентна»й ему дочитывающий ДМП-автола»п Р'. Д о к а з а т е л ь с т в о. В силу леммы 2.27 можно считать, что для Р всегда возможен очередной такт.
Пусть Р' = Я 1) (р, г), Х, Г, 6', 4„2„Р 0(р)), где р и г — новые состояния, а 6' определяется так: (1) для всех а Е Я, а Е Х и 2 Е Г положим 6' (а, а, 2) = 6 (а, а, 2); (2) для всех ОЕАР и ЛЕГ, таких, что, (д,е,2) не является зацикливающей конфигурацией, положим 6'(а, е, 2) =6(в, е, 2); (3) для всех (д, 2) ЕС„где С,— множество, построенное алгоритмом 2.16, положим 6' (у, е, 2) (г, У); (4) для всех (д, с) ЕС,„где С,— множество, построенное алгоритмом 2.16, положим 6' (у, е, 2) = (р х)' (5) для всех аЕХ и ЛЕГ положим 6'(р, а, 2):=-(»,2) и 6'(г, а, г) =- (, 2). 215 ГЛ.
2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ УПРАЖНЕНИЯ Таким образом, Р' моделирует Р, на если Р попадает в зацикливающую конфигурацию, то Р' в очередном такте перейдет в состояние р или г в зависимости от того, встречается нли нет в циклической последовательности конфигураций заключительное состояние, Затем, какова бы ни была входная цепочка, Р' переходит в состояние г и остается в нем, ничего не меняя в магазине. Отсюда 1. (Р') ==7,(Р), Надо показать, что Р' — дочитывающий ДМП-автомат. Правила (3) — (б) гарантируют, что условие,дочитываиия" для Р' выполняется, если Р попадает в зацикливающую копфигураци!о. Остается только заметить, что если Р находится в незацпкливающей конфигурации, то через конечное число тактов он должен либо (1) сделать не е-такт, либо (2) попасть в конфигурацию, укорачнвающую магазин. Кроме того, ситуация (2) не может повторяться бесконечно, так как в исходной конфигурации магазин имеет конечную длину.
Таким образом, либо в канне концов произойдет (1), либо после нескольких повторений (2) Р попадет в зацикливающую конфигурацию. Итак, можно заключить, что ДМП-автомат Р' дочитывающий. Г) Теперь докажем одно важное свойство ДМП-автоматов, а именно, что класс распознаваемых ими языков замкнут относительно дополнения. В следующем разделе мы увидим, что для класса всех КС-языков это пе так. Теорема 2.23. Если 7.=Ь(Р) для некоторого ДМП-аотолтата Р, то Е=Е(Р') для некоторого ДМПаетомата Р'.
Док аз а тел ьство. По лемме 2.28 можно считать, что Р— дочитывающий. Построим Р' так, чтобы он моделировал Р н между сдвигами входной головки выяснял, попал ли Р в допускающее состояние. Так как Р' должен допускать дополнение языка А(Р), то Р' допускает входную цепочку, если Р не допускает ее и собирается сдвинуть свою входную головку ,'и, следовательно, уже не допустит ее и позже). Формально пусть Р= — Я, Х, Г, 6, а„Я„Р) и Р'=.(Я', Х, Г, 6', д;, Я„Р'), где (!) ()'=-([Е, 1П1ЕЯ, 1~(0 1 2)) (2) г!',=-[а„, 0], если д,(Р, и д',=[!)„!], если Е„ЕР, (3) Р' — ([д, 2](о~!е). Состояния вида [а, 0] предназначены для обозначения того, гго Р нс был в заключительном состоянии после паследнега не .-такта.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
