Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 55
Текст из файла (страница 55)
х, Ь,(иг) —..у. г1 Следствие. Перевод нагнется простым СУ-переводом тогда и в«олька тогда, когда он характеризуется КС-языком. Ю Для некоторых переводов можно показать с помощью теорем и 3 4, что они не регулярные нли же ие простые СУ-переводы. Легко показать, что область определения и множество значений любого Су-перевода принадлежат классу КС-языков. жако есть и такие СУ-переводы, что их область определения множество значений регулярны, но сами они не определяютс ются ни конечным преобразователем, ни даже МП-преобразователем, 271 Гл.
3. теоРия пВРГВОдА к2, СВОИСТВА СИИТАКСИЧЕСКИ УПРАВЛЯЕМЫХ ПЕРЕВОДОВ Пример 3.!6. Рассмотрим простую СУ-схему с правилами 5 — ОЯ, ЯО Я- 15, 51 Я- е, е Покажем, что т(Т) =((ш, а и)) ше (О, 1)*) не является регулярным переводом. Допустим, что перевод т(Т) регулярен. Тогда найдется регулярный язык 1., сильно характеризующий т(Т).
Без потери общности можно предположить, что 1, ы (О, 1, а, Ь)", а соответствующие гомоморфизмы удовлетворяют условиям Ь, (0) = О, Ь,(1) =- 1, Ь, (а) — Ь,(Ь):= е, Ь., (0) =- Ь, (1) =- е, Ь, (а) = О, Ь,(Ь) =-- 1. Вслн язык 1. регулярен, он допускается конечным автоматом М =(!1, (О, 1, а, Ь), 6, д„, г') с в состояниями для некоторого в)1. В 1. должна найтись такая цепочка г, что Ь,(г) =0'1' и Ь (г) =1'0', поскол ку Рябе (О 1, 1 0 ) Е т(Т). Все нули в г предшествуют всем единицам, а все символы Ь предшествуют всем символам а. Таким об а- разом, первые з символов цепочки г могут быть только нулями или символами Ь.
Состояния, которые пройдет автомат М, прочитав первые з символов цепочки г, не могут все быть разными, так что монсно писать г= ивы, причем (д„г) ! — *(д, Рш) (д„ш) ! — *(р, е), где ~ив|~в, ) в~ .»! и р ~Р. Тогда поит~1.. Но й,(иввш) =-0'''"!' н Ь,„(иввгв) = Р" "0', где т и п не равны одновременно нулю. Поэтому (О"'"1', 1' "0') ет(Т). Мы пришли к противоречию, так как предположили, что перевод т(Т) регуляреи. П Пример 3.!7. Рассмотрим СУ-схему Т с правилами Я вЂ” А"'сА ">, А'"сАВО А- ОА, ОА А- 1А, 1А А — е, е Здесь т(Т) =((исв, Оси) (и, В с(0,1)*). Покажем, что т(Т) не является простым СУ-переводом. Допустим, что 1.— КС-язык, сильно характеризующий перевод т(Т).
Можно считать, что Л' =(с', О', 1') 1.:-((О, 1 ) Л')* ,— соответствующие гомоморфнзмы. Для любых и, о ~ (О, 1)" найдется такая цепочка г,,~1., что Ь (г ) = — исо н Ь (г )== Рассмот м три отдельно два случая, связанные с расположением символов с и г' в цепочках г„,. Слчай1: Д у ": Для каждой цепочки и существует такая цепочка в, что с предшествует с' в г„. Пусть !т — регулярное мно- 772 (О 1 О, 1')'с (О, 1, О', 1')*с' (О, 1, О', 1')".
Тогда 1. П)7— КС язык, поскольку класс КС-языков замкнут относительно пересечения с регулярными множествами. Заметим, что множео 1, ПТС состоит из тех цепочек Языка 1., в котоРых с пРедшествует с'. Пусть М вЂ” конечный преобразователь, который до тех пор, пока не прочтет с, передает на выход нули и единицы пропуская символы со штрихами. После чтения символа с ои не выдает ничего, пока не достигнет с'. После этого М печатает на выходе О, прочитав на входе 0', и 1 вместо Г, пропуская нули н единицы.
Тогда язык М (1. () )7) должен быть КС.языком, так как класс КС-языков замкнут относительно конечных преобразований, но в данном случае М (1 и )7) = =. (ии!Иб(0, 1)*), а это, как показано в примере 2А1, не КС-язык. Случай рл Для некоторой цепочки и не существует ни одной цепочки в, в которой символ с предшествует с' в г„„. Тогда для каждой цепочки и можно найти такую цепочку и, что с' предшествует с в г„„.
Рассуждая, как в случае 1, можно показать, что если бы язык 1. был контекстно-свободным, то и язык (ю)об(0, 1)*) был бы тоже контекстно-свободным. Зто рассуждение мы оставляем в качестве упражнения. Итак, перевод т(Т) пе сильно характеризуется никаким КС-языком и, следовательно, ие является простым СУ-перево- ДОМ П Пусть Р, обозначает класс регулярных переводов,,9,— класс простйх СУ-переводов и" Т вЂ” класс СУ-переводов. Из приведенных выше примеров вытекает, что справедлива следующая теорема. Теорема 3.5. Я, ~~Я, ~~вт .
Доказательство. Т,: — Р' по определению, е,: —,'Г„ так как конечный преобразователь — частный случай МП-автомата. Из примеров 3.16 и 3.17 следует, что включения собственные. П 3 3.3. Свойства простых СУ-пврвводов С помощью понятия характеризующего языка можно доказать аналоги многих теорем о нормальных формах, приведеннь|х в равд, 2.6, Здесь мы докажем два из этих результатов, а остальные оставим в качестве упражнений.
Первый из пих— аналог теоремы о нормальной форме Хомского. где Теорема 3.6. 17усть Т вЂ” простой СУ-перевод. Тогда Т ==я(Т,), е 71=(Ы, Л, Л, Я, 3) — простая СУ-схема, у которой каждое пдавилс иэ )7 имеет один иэ следуюи(их видов: гл. з. тео~ия ~егеводл (1) А — ВС, ВС, где А,В и С вЂ” (не обязательно различные) нетерминолы из Х, (2) А — а, Ь, где один из символов а и Ь есть е, а другой принадлежипг Х или Л соответственно, ( ) . е, е, если (е, е) Е Т, причем В не встречается в пра- 3 В вых частях правил. До к а з а те л ь с т в о, Применить конструкцию теоремы 3.4 к грамматике в нормальной форме Хамского. гл Второй результат — аналог теоремы о нормальной фо ме Грейбах.
— о форме Теорема 3.7. 77усгпь Т вЂ” простой СУ-перевод. Тогда Т=т(Т,), где Т, =(Я, 2', Л, Я, В) — простая СУ-скелга, у которой каждое правило из 77 имеет вид А — аог, Ьа, где абХ", один из символов а и Ь есть е, а другой принадлежит В или Л (с тем же исключением, как в случае (3) предыдуи(ей теоремы). Дока за тельство. Применить конструкцию теоремы 3.4 к грамматике в нормальной форме Грейбах. Отметим, что в теоремах 3.6 и 3.7 нельзя сделать так, чтобы одновременно было аЕ В н ЬсЛ. Тогда перевод сохранял бы длину слова, а для простых СУ-переводов это не всегда так, 3 э.
сВОйстВА сиптАксически уггРАВляемых пеРеВОдОВ Лемма З.б. доказательство. Легко показать, что область определения ения СУ-перевода порядка 1 является линейным КС-языком. По теореме 3.6 каждый простой СУ-перевод имеет порядок 2 и к ждый КС-Язык слУжит областью опРеделениЯ пекотоРого пРостого СУ-перевода (хотя бы тождественного, для которого этот язык — область его определения). Так как линейные яаыки образуют собственный подкласс КС-языков (упр.
2.6.7), то включение Г, в Г, собственное. Для СУ-схем существугат разные нормальные формы. 7г4ы утверждаем, что из СУ-схемы, как и из КС-грамматики, можно устранить бесполезные нетермипалы. Кроме того, для СУ-схем существует нормальная форма, отчасти похожая на нормальную форму Хамского, а именно: все правила можно привести к такому виду, что каждая правая часть либо целиком состоит яз нетерминалов, либо не содержит ни одного нетермииала. Определение.
Нетерминал А в СУ-схеме Т=(М, Х, Л, Я, Я) называется бесполезным, если либо (1) нет таких хсзр' и ус Л', что (1 А) ~* (х у) (2) ни для каких гг,, сг,б(Мц ~)* и р~ ггг с()ч)11 Л)* не суще СтауЕт ВЫВОда (Я, Я) =>* (а Аа, Ргг'Чг). 3.2.3. Иерврхмв СУ-переводов 1'лавный результат этого раздела состоит в там, чта для произвольных СУ-перевадов нет аналога нормальной формы Хамского. За одним только исключением, всякий раз, когда мы увеличиваем число нетерминалов, допустимое для правых частей правил СУ-схем, соответствующни класс СУ-переводов становится более пгироким.
Попутно мы докажем и другие интересные свойства СУ-переводов. Определение. Пусть Т =-((ч, Х, Л, )7, Я) — СУ-схема. Б р ть, что Т имеет порядок й, если ни в одном правиле А — и, р из )7 цепочка и (а следовательно, и ()) не содержит более й вхождений нетерминалов. Будем также говорить, что перевод т(Т) имеет порядок й. Пусть à — класс всех СУ-переводов порядка й. Очевидно, что Г, с: — Г„т... ' .Гг с: —.... Мы покажем что каждое из этих включений собственное, за исключением того, чта ~,=Г,. Для этого нам понадобится ряд предварительных результатов. 274 Лемма 3.6. Каждый СУ-перевод порядка )г определяется СУ- схемой порядка й, не содержащей бесполезных нмперминалов. Д о к а з а т е л ь с т в а. Упражнение, аналогичное теореме 2.13.
Лемма 3.7. Каждый СУ-ггеревод порядка й=э 2 определяется такой СУ-схемой Т,=-(Ь1, Х, Л, )7, Я), что если А- а,(1 пРи надлежит )7, то либо (1) сг, ~~Ь(", либо (2) Й~*, И Кролге того, Т, не содержит бесполезных нетерминолов. Доказательство. Пусть Т, =-. (Ь1', Х, Л, Я',Я) — СУ-схема, ие содержащая бесполезных нетерминалов, и т (Т,) = Т. ПостРоим )7 по )с' следующим образом. Пусть А — ~- х„Вгх,... Вьк„УдСгУд...
С„УА — правило из )с', причем й ) О. Пусть и — такая перестановка ~исел 1, ..., п, что нетеРминал Вг соответствУет нетеРминалУ ГЛ 3. ТЕОРИЯ ПЕРЕВОДА 3 3 СВОЙСТВА СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫХ ПЕРРВОДОВ С,и(. Введем новые нетерминалы А', Р„..., Р» и Е„..., Е» и заменим это правило правилами А Е,А', Е,А' Ео ха уо А' — Р,...Р», Р»...Р», где Р;=Р.;,а для 1(1»й р; — В;Е«, В;Е« для 1(((й Е( — «.Х„упа] дЛя 1~»1»-й Например, если правило имеет вид А — 'хоВ1х1Взх,Вохз, УаВзу,В,У,В,Уз то п=(2,3, !) и оно заменяется правилами А — Е3.4, Еол Ео «ха«уо '1' †« Р1РЗР», РзР1Р3 Р,— В(ЕВ В;Е( длЯ 1=1, 2, 3 Е, х„уз Е,— х„у, Ео — хо, у, Так как Р( и Е; для каждого ( имеют только по одному правилу, легко видеть, что все новые правила в совокупности действуют так же, как правило, которое онн заменяют.
Правила из )7', не содержащие нетерминалов в правых частях, прямо (юмещаются в )7. Обозначим через 13 множество 14' вместе с новыми нетерминалами. Тогда т(Т,)=т(Т,) и Т, удовлетворяет условиям леммы. Лемма 3.8. Та=ага. Д о к а з а т е л ь с т в о. В силу леммы 3.7 достаточно показать, как заменить правило вида А — В,В,В3, С,С,С, двумя правилами, у которых каждан компонента правой части содержит два нетерминала. Пусть и †перестанов, при которой В, соответствует С а). Таких перестановок может быть шесть. В каждом случае можно ввести новый нетерминал Р и заменить интересующее нас правило двумя правилами, как показано на рнс. 3.6. Легко проверить, что в каждом случае новые правила в совокупности действуют так же, как старое.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
