Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 56
Текст из файла (страница 56)
Лемма 3.9. Каждый СУ-перевод порядка йЪ2 определяется СУ-схемой Т =-(1(, 2„Л, )7, 3), удовлел(воряюи(ей лемме 3.7 и следу(ои(им условиям: 276 (П )7 нет правила вида А — В, В, (2) в )7 нет правил вида А — е, е (за исключением случая А В, но тогда символ 3 не должен встречатася в правых частях правил). до к а з а т е л ь с т в о. Упражнение, аналогичное теоремам 2.14 и 2.15. ) и (3) я (2) Правила я(!) Л -«В1П, В,П л в,п, в,'и л пв,,пв, л-'пво Взп л в,п', пв, л вп', пв, и — в,в„ в,в, и вова В3В3 и в,в„ в,в, и в,в,, 'в,в, и -« ВЗВ3, В,В, П - В,В,', В,В, Рис. З.б. Новые правила. а а',а» в а( та(па«, .а(ам« 13 '» и (Ц п(3! ' ' ' и(»! а"ример, если а„а„а„а,— это а, Ь, с, (1, то Т,=-)((а(Ь!с»((1, с»а'й'Ь1) ~ (, 1, й, 1~0) Теперь определим такое семейство переводов Т, для йЪ4, что Т, имеет порядок й, но не й — 1, а затем докажем ряд лемм, из которых это будет следовать.
Определение. Пусть й' -4. Пусть Х» обозначает — только до конца этого раздела — множество (а„..., а ). Определим перестановку я» для четного й равенствами »+1+ ! если ! нечетно я»(!) =- если ( четно 2 В~пример, п,=(3, 1, 4, 2) и п,=(4, 1, 5, 2, 6, 3), Определим и» для нечетного й равенствами »+! — если (=1 2 п,(1)= й — — )-1 если !' четно 2 1 — ! — если ! нечетно и )Ф1 2 Например, и, = (3, 5, 1, 4, 2) и и, =(4, 7, 1, 6, 2, 5, 3). Пусть Т» — взаимно однозначное отображение, которое пере- Водит ГЛ. 3. ТЕОРИЯ ПЕРЕВОДА В дальнейшем будем предполагать, что й) 4 — фиксирован.
ное целое число и существует СУ-схема Т=-(Х, Тм ХА, 1, 3) порядка й — 1, определяющая Т,. Без потери общности можно считать, что Т удовлетворяет лемме 3.9 и, значит, леммам 3,6 и 3.7. Мы докажем, получив противоречие, что Т не может су. ществовать, Определение. Пусть Хя г:А н А Е Х. (Напомним, что имеется в виду СУ-схема Т, определяющая по предположению перевод Т, ) Множество Х будем называть (А, й)-ограниченным в области определения (соответственно в множестве значений), если для каждой пары (х, у), для которой (А, А)=РГ(х, у), существуе! символ и Е Х, содержащийся не более й раз в х (соответственно и у).
Если множество Х пе является (А, д)-ограниченным в области определения (множестве значений) ни для какого й, то будем говорить, что А покрываеп! В в обласп!и определения (мне. жестве значений). Лемма 3.10. Если нетерминал А покрывает Х в области. определения, то он покрывает Х в множестве значений, и обратно.
Д о к а з а т е л ь с т в о. Допустим, что А покрывает множество г, в области определения, но оно (А, й)-ограничено в мяо. жестве значений. По лемме 3.6 найдутся такие и!„и!„и!„и!! Е г.А, что (В, 5) ==;>" (и!!Аи!„и!,Аи!!). Пусть т = ) и!,ю, ). Так как А покрывает Х в области определения, то найдутся такие и!А, гв,бг„, что (А, А)=о'(и!„Гв,) и любой символ аЕХ содержится более т +и раз в и!,. Но так как г (А, й)-ограничено в множестве значений, то найдется символ (! Е Х, содержащийся не более д раз в и!!. !1ри этих условиях пара (и!!!В,и!„Гвчи!,и!!) должна принадлежать Т,, хотя Ь входит в и!Аи!„Гве более т+й раз, а в и!,и!,и!,— Ве более т+й раз.
Полученное противоречие показывает, что если нетерминал А покрывает Х в области определения, то он покрывает г, также и в множестве значений. Обратное утверждение доказывается по симметрии. П Лемма 3.!О дает право говорить, что А покрывает Х, не упоминая области определения и множества значений. Лемма 3.1!. Пусть А покрывает ХА. Тогда существуют правило А — В, ... В, С,... С из П и такие множества 6„..., !д, объединенис которйх совпадает с ХА, что В,.
покрывает 8! (1< ! <.'.т). До к а з а т е л ь с т в о. Пусть й,— наибольшее из таких конечных чисел, что для некоторых Х~Х и В,. (1<!' "т) множество Х (Во д„)-ограничено, но не(В„й,— 1)-ограничено, Ясно, что такое а', существует. Положим й! = й, (й — 1) + 1. Тогда должны эл. св СВОЙСТВА СИНТАКС! !'!ВСКИ УПРАВЛЯЕМЫХ ПЕРЕВОДОВ к В", что (А, А) =!А" (х, у) и каждыи найтись та . каждую из ннх по крайней ь р ! Р КВЕ ЦЕПОЧКИ Х, У 'А ге е й аз символ аЕ А е т было бы (А, с(,)-ограниченным).
у входит в ка (' " о вый шаг вывода )' отивяоы САУ " " (А А) — > (х у) был (А, А)=!> Усть ПВР ', ! ак по предположению Т имеет С„), ак как и (В! ' В ' ' '' '"<ь--1. Можно записать х в виде х, ... х, поряд В )-О*(хт У!) длЯ некотоРой цепочки У!" Р ля п онзпрнче"! ( " ' на найтись хотя бы одна цепочка х,, содерВольпо'О " о противном случае цепочка х " Х должйа а , ее й аз, потому что В т жащая а боле А Р 1 й — 1) — 1,— 1 раз. Пусть ГА!~ТА '" з символов, которые входят' в х! более А Р 3.
В О... !.!О = — ЕА. Тогда В! для кажпредыдущ * ак в противном случае какое -то (В, й)-ог аниченным для некоторОГО к ывает „так к множест ! тво В), было ы О - Р лу нашего выбора числа й,. () д Это невозможно в силу ) А. , П, н а — различные элементы множенаходится между а; и а„если е елеиие. усть ао а, н а,— ства ВА Будем говорить, что ау либо (П ! <1 <1, либо (2) ЙА(!) < пА (1) < ПА (1). Таким о разом и гвол формально находится между двумя слн он действительно расположен между д угими снмволамн, есл он оп е еними в како -нн удь й- б ь цепочке, принадлежащей области р двоа Т. ления или множеству значений перевода Л 3.12. Пусть А покрывает ХА и — В ...
В, емма емме 3.11. Если В, по- С .. С вЂ” правило, удовлетворяюи)ее лемме крывает (а,) и (а,), и а, нахсдитсн меж у д а иа то В покрывает (а!) и В ни для какого !'чь! не покрывает (а!). Доказательство. Допустим, что г < ! з и В пок ывает (а!), причем !'=Уз!. Рассмотрим отдельно случаи 1 < ! и ! > !'. С.
" 1: ' '. Так как во входной грамматике схемы Т луной ! !'<!. ак к к а а из В выводится из В! выводится цепочка, содержащая а„, а из "'"очка, содержащая а„то (А, А)~*(х, у), где х содержит ВХО»!двине а п едшествующее вхождению а,. д в области определения перевода Т„ есть цепоч Р елочка, кото ой там "е должно быть. выво нтся цепочка, 1Р !Положим что из В! Выводит содержащая а,.
Можно аналогично найти в о ласт р, . ласти оп еделения пеРевода Т цепочку, в которой а, пред ествует а,. е о ключить возможность Почученное противоречие позволяет исключит в что г < ! < з. Единственная оставшаяся возможность— гл. 3. ТВОРИЯ лгРРВодл РЛР»жнвния л» (т) < и» (1) < и» (в) — рассматривается аналогично с привлече. пнем множества значений перевода Т». Таким образом, В, ни дли какого 1~1 не покрывает (ав). Если Вт покрывает Х, содержащее а„то Взь разумеется, покрывает (ав). Следовательно, по лемме 3.11 В; йокрывает некоторое множество, содержащее а„и, значит, покрывает (а,). П Лемма 3.13.
Если А покрывает Х» (я>4), то суи1ествует такое правило А — В, ... В„, С, ... С„и такой индекс 1, 1(1 ..т, что В» покрывает Х,. Д о к а з а т е л ь с т в о. Рассмотрим случай, когда й четно, Случай нечетного й рассматривается аналогично и оставляется в качестве упражнения.
Пусть А — В, ... В„, С, ... ф— пра. вило, удовлетворякицее лемме 3.11. Так как по предположению т(й — 1, то некоторый нетерминал В, должен покрывать два элемента множества Х», скажем (а„а,), где т Ф в. Следовательно, В, покрывает (а,) и (а,), а если а, находится между а, и ав, то по лемме 3.12 В; покрывает (ав) и Вг ни для какого )Ф» не покрывает (а,). Рассмотрим множество значений перевода Т .
Если нетерми. иал Ве покрывает (а»м) и (а»ИЯ,), то он покрывает (а) для всех аЕ Х» и никакой другой иетерминал В, не покрывает никакого (а). В силу леммы 3.11 В, покрывает Х». Далее, если Вв покрывает (ам) и (а,), где т(й/2 и п > й!2, то, исследуя область определения, убеждаемся, что В, покрывает (а»»,) и (а»»,+,). Таким образом, если одно нз чисел т и в не превосходит й)2, а другое превосходит й/2, то нужный результат получается сразу.
Остались случаи т(йу2, э~у(2 и т > йу2, в > й(2. Но в множестве значений для л~обых различных т и з, не превосходящих йу2, между а„и а, найдется символ ал для которого 1>й/2. Аналогично, если т > й/2 и в > й!2, то между ними найдется символ а„для которого 1(й~2. В любом случае лемма доказана. 1л Лемма 3.14. Т»ЕЮ» — ~"» г для )е= 4. Д о к а з а т е л ь с т в о, Ясно„что Т, Е,К». Остается показать, что вопреки предположению для Т„не существует СУ-схемы Т порядка й — 1. Так как 5, разумеется, покрывает Х„то по лемме 3,13 в )Ь) найдется такая последовательность нетермииалов Л,„АИ, Аен, что Л,=5 и для каждого 0(вк..4~)Ь существует правило А; — ивА;0131, у»ЛР,16Л причем Л; покры.
вает Х». Так как все Л; не могут быть различными, найдутся такие 1(1, что ЛЯ= Аг. По лемме 3.6 можно найти такпв' , что для всех рР0 ° 9 ВЕ10' (5 5) =ББ (св Аввгв, иБЯАвевв) ~Б (Ш,ШБЛ Баввив„ШЯШБА1вгвсгв) =.1' (иввиБРЛ;и9»и999 иввшв Л 1ивв'"Б) (И1нвБ пав и10 1 1 7 10 Я Р и то же число вхождений а, потому что иначе в переводе т Х то ла бы пара, кот орой нет в Т . Так как А; покрывает бы одержали какой-нибудь символ, кром ». е б бы подобрать ив так, чтобы получить бы ив, иБ„и91 и и99 с или а, можно ыло ы и 9 па у, не пр» виадлежащую Т . Следовательно, в ив, или ивв вхо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
