Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 54
Текст из файла (страница 54)
*3.1.13. Пусть )7 †регулярн множество. Постройте такой конечный преобразователь 7г1, что М (!.) = )77!. для любого языка !.. 3.!.14. СУ.схема Т =-((Аг, Х, Л, Тс, В) называется араеолггнейной, если каждое правило из )7 имеет вид А- хВ, уВ или А — х,у где А, ВЕ г», хЕЕ" и уЕ Л", Покажите, что если Т вЂ” праволинейная СУ-схема, то т(Т) — регулярный перевод (конечное преобразование). "*3.1.15. Покажите, что если Т ы а*х Ь* — СУ-перевод, то Т определяется конечным преобразователем. 3.1.! 6 Рассмотрим класс префиксиых выражении в ачф П И- вигах опера ций О и операндов у. Если цепочка а,...а„р- надлежит г > (В(1 л)* то степень з ее г'-й позиции (О.-г -л) вычис- ляется так: (2) если а, — т-местная операция, то з, = ,, .= з +ггг — 1 (3) если а, Е Х, то з; =- з;,— — — 1.
докажите, что а,... „— а ...а — префиксное выражение тогда и только тогДа, когДа Е„=О и зг > О ДлЯ всех г ~ги *3,1.17. Пусть а,...а„— префиксиое выражение, в котором а — -т-местная операция. Покажите, что единственный способ а>†-~-местная запасать а,...а„ как агшг...нг,„, где ге, ..., ге — п иксные выражения, — зто выбрать выражение в, (1 ( ! ( т) гак, чтобы оио оканчивалось первым из символов аь, у которого ЕА — — т — !. *3.1,18.
Покажите, что камгдое прсфиксное выражение с бинар- ными операциями получается из единственного инфиксного выра- жения, не содержащего избыточных скобок. 3.1.19. Переформулируйте и выполните упр. 3.1.16 — 3.1.18 для постфиксйых выражений. 3.1.20. Дополните доказательство теоремы 3.1. "3.1.21.
Докажите, что порядок, в котором шаг (2) алго- ритма 3,1 применяется к вершинам, не влияет иа результирую- щее дерево. 3.1.22. Докажите лемму 3.1. 3.1.23. Постройте МП-преобразователи, реализующие простые СУ.переводы, определенные схемами трансляции из примеров 3.5 и 3.7.
3.1.24, Постройте грамматику для операций языка Снобол 4, отражающую ассоциативность и приоритет операций, указанные в приложении П2. 3.1.25. Найдите СУ-схему, определяющую перевод, который определяет (опустошением магазина) МП-преобразователь ((д, р), (а, Ь), (2„А, В), (а, Ь), б, д, 2„8) где б задается равенствами б(а, а, Х) =(а, АХ, е) для всех ХЕ(2,, А, В) б(д, Ь, Х) =(г), ВХ, е) для всех Х 8(Л„А, В) б(д, е, А) =(р, А, а) б (р, а, А) = (р, е, Ь) б(р, Ь, В)=(р, е, Ь) б (Р, е, 2,) = (р, е, а) 262 Гл.а.
ТеоРия пеРеВОдА е"3.1.28. Рассмотрим два МП-преобразователя, соединенных последовательно, так что выход первого служит входом второго. Покажите, что для такого «тандемаа МП-преобразователей множеством всевозможных выходов второго МП-преобразователя может быть любое рекурсивно перечислимое множество. 3.1.27. Покажите, что Т вЂ” регулярный перевод тогда и только тогда, когда существует такой линейный КС-язык Е, что Т = =-((х, у) [хсуя Ец, где с — новый символ.
"3.1.28. Докажите, что проблема равенства Т,=. Т, для регулярных переводов Т, н Т, неразрешима. Открытые проблемы 3.!.29. Разрешима ли проблема эквивалентности для детерминированных конечных преобразователейр 3.1.30. Разрешима ли проблема эквивалентности для детерминированных МП-преобразователейр Проблема для исследования 3.1.31. Известно, что проблема эквивалентности для не- детерминированных конечных преобразователей неразрешима (упр.
3.1.28), Поэтому нх нельзя ачинимизироватьа в том смысле, в котором мы в равд. 3.3.1 минимизировалк конечные автоматы. Однако с помощью некоторых приемов можно уменьшить число состояний. Попробуйте найти полезный набор таких приемов. То же самое попытайтесь сделать для МП-преобразователей. Замечания по литературе Идея скнтакснческн управляемой трансляции возникла у многих ~рнмерно а одно н то же время.
Среди тех, кто первыми стали пропаганднровать ее орнменепнс, были Айронс [1961) н Барнет я Фу«рель [1962]. Конечные преобразователи апалогнчны обобщенным последоаательностным машинам, введенным С. Гннзбурпгы [ !962). Наши определенна СУ.схемы н А[11-преобразоаатекя н результат об нх зкянаалснтностк (теорема 3.2) подобны тому, что прнаедсно а работе Льюиса н Стнрнза [!9681'). Гряффнтс [1968[ показал, что проблема зканаалентностк для нсдетермнннроаанных конечных преобразователей без с-аыходоа тоже неразрешима, 3.2.
СВОЙСТВА СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫХ ПЕРЕВОДОВ В этом разделе мы исследуем несколько теоретических свойств синтаксически управляемых переводов и дадим характеристику простых СУ-переводов. ') Следует также упомянуть работы Чувяка [1966[ н Па«роне [1966[.— Прим. верее. ч з свойстВА гИ синткксичесгси упРАВлясмык пРРРВодоВ 3.
° ° 2 Ф Характеризующие яз ии Оп еделеиие, удем говорить, что язык г характеризует перевод Т, если сущест п,, е тву!от такие два гомоморфизма й, и йго что Т = — ((й, (и:), й, (го)) ~ гв Е 7 ). Пример 3.14. Перевод Т=((и", а") [гг) 1) характеризуется языком О', так как Т=((йг(ш), йз(иг))[игсО«), где й,(О) = Будем говорить, что я , что язык В (л П Л')* сильно характеризует перевод Т с= 2:* х Л*, если (1) Т [[ Л' = ггз; (2) Т = [(й, (иг), й, (иг)) ! иг Е /), где (а) й,(а)=а для всех аЕХ и й,(Ь)=е для всех ЬЕЛ, (б) й,(а)=е для всех аЕХ и й, взаимно однозначно ото ражает н б Л' на Л (т.
е. й — биективпое отображез иие Л' в Л). Пример 3.15. Перевод Т=((а", а")[пЪ1) сильно характеризуется языком 7.,= ((а"Ьк)[п) 1). Он также сильно характеизу тся языком !., = [иг[иг состоит из одинакового числа сгм- Ь). Гокгоморфизмы в обоих случаях определяю:ся равенствами й,(а) ==.а, й,(Ь)=-е и йа(а) — е, йе( ) а.
Язык йе сильно характеризует перевод Т. [з С помощью понятия характеризующего языка можно исследовать классы переводов, определяемых конечными преобразоВателямн и МП-преобразователями. Лемма 3.4. Пусть Т =-([Ч, к, Л, )7, Я) — СУ-схема, в котороб каждое правило имеет вид А — аВ, ЬВ или А — а, Ь, где ггчоц(е), ЬЕЛ[[(е) и Ва[Ч. Тогда г(Т) — регулярный перевод. Доказательство. Пусть М=([Ч[[()), ~, Л 8 Я Й)— конечный преобразователь, причем [" — новый символ. Пусть 6(А, а) содержит (В, Ь), если правило А- аВ, ЬВ принадлежит 1«, и содержит (1, Ь), если правило А а, Ь принадлежит )7 Индукпией по п можно показать, что (Я,х,е) )-"(А,е,у) тогда и только тогда, когда (Я, Я) =>" (хА,уА) Отсюда следует, что (я, х, е) ) — *(), е, у) тогда и только тогда, когда (Я, Я)=->*(х, у).
Детали доказательства оставляем в качестве упражнения. Таким образом, т(Т)=т(М). Г) Теорема 3,3. Т вЂ” регулярный перевод тогда и только тогда, когда Т сильно характеризуется регулярным языком. 269 ГЛ. 3. ТЕОРИЯ ПЕРЕВОДА Е=Х Л'' Доказательство. Достаточноапь. Допуст ( (/ ') — регулярный язык и 6, н 6« — гомоморфнзмы, причем Ьг(а) =-а для а~2, 6,(а) =: е для аЕЛ', 6,(а)=-е для аЕХ и Ь, взаимно однозначно отображает Л' на Л. Пусть Т=((йг(иг), 6«(иг))(игбЕ), а 6=(Х, Х(/Л', Р, 3) — регулярная грамматика, для которой Е (6) =- Е. Рассмотрим СУ.схему 0=(Н, Х, Л, /т, 3), где /с определяется так: (1) если А-+.ПВ принадлежит Р, то А-Рйг (а) В, Ь (а) В принадлежит /г; «( ) (2) если А- а принадлежит Р, то А-г-й, (а), 6,(а) принадлежит В. Легко доказать с помощью индукции, что (А, А)~о(х, и) тогда и только тогда, когда А =.ь3»о, 6,(иг) = х и 6,(иг) = и.
Отсюда можно заключить, что (3, 5) =::>о(х, у) тогда н только тогда, когда (х, и) б Т. Следовательно„т(Ег) = Т. По лемме 3.4 существует конечный преобразователь М, для которого т(М)=Т. Необходимость. Допустим, что Т с= Х' х Л* — регул ярпыи перевод и =(б, Х, Л, б, г/«, Р) — конечный преобразователь, для Л« Пусть Л =~а'(абЛ) — алфавит, состоящий из новых символов, а 6=(6 г'гдЛ', Р )— =(б, 2; О Л', Р, г/«) — праволинейная грамматика, в которой Р определяется так: (1) если б(г/, а) содержит (», у), то г/ — ~.ай(у)» принадлежит Р, где Ь вЂ” такой гомоморфизм, что 6(а)=-а' для всех ааЛ; (2) ЕСЛИ г/ЕР, тΠΠ— РЕ ПрИНадЛЕжИт Р.
Определим гомоморфнзмы 6, и Ь, равенствами 6,(а) = — а для всех а~1 Ь, (6) = е для всех /г Е Л' 6„(а) =-е для всех а и Х 6,(й')=й для всех 6'ЕЛ' Индукцией пот и по и можно показать, что (,. ) '1 — "(,, ) для некоторого т тогда и только тогда, когда г/=>" иг» для некоторого и, где Ь, (иг) = х и Ь, (т) = у.
Таким образом, (г/„х, е) 1 — '(г/, е, и) для г/бр тогда и только тогда, когда г/, =ь' игг/=> щ, где Ь, (иг) = х и Ь, (иг) —. и. Следовательно, Т вЂ” -- ((Ь, (иг), й, (иг)) (иг б Е(б)) и, значит, Е (6) сильно характеризует Т. () Следствие. Т вЂ” регулярный перевод тогда и только тогда, ковда Т характеризуепгся регулярным языком.
Д о к а з а т ел ь с т в о. Сильная характернзация — частный случай характеризации. Поэтому в одну сторону («только тогда») 270 3 2. СВОЙСТВА СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫХ ПЕРЕВОДОВ евидно В другую сторону («то~да~) показатель ство Во получается простым обобщением доказательства соответ- ствчюшей части теоремы. Похоже доказывается аналогичный результат для простых Су-переводов.
Теорема 3.4. Т вЂ прост СУ-перевод тогда и только тогда, огда он сильно характеризуется КС-языком. до к а з а т ел ь ство. Достаточность. Пусть Т сильно характе- ризуется языком, порождаемым грамматикой 6,=-(Х, Х (/Л, Р, 3), „де й, и Ь, — соответствугощие гомоморфизмы. Построим про- стую СУ-схему Тг=()Ч, Х, Л, /г, 3), где /гг определяется так: для каждого правила А-+.т„В,»В,...ВАиг из Р правило А — ~- Ь, (иго) В,Ь, (игг)...
ВА/г, (игь), Ь«(ич) В«6«(тг)...ВАЬ«(игь) принадлежит П. Индукцией по п легко доказать, что (1) если А=ос иг, то (А, А) =гт (6, (го), 6,(иг)), (2) если (А, А)ггг (х, у), то существует такая цепочка иг, что А =>й иг и Ь, (иг) =-х, 6,(иг) =у. Таким образом, т (Т,) = Т. Необходимость. Пусть Т=т(Т,), где Т,=(М, Х, Л, /с, В), и Л' =- (а' ( а Е Л) — алфавит, состоящий из новых символов.
Построим КС-грамматику 6«=(Х, ХИЛ', Р, 5), где Р содержит пРавило А — х,У',Вгх,рг... Вьх«УА ДлЯ кажДого пРавила А — х„В,х,...В х„и,В,й...Вьу« принадлежащего П, причем у; получается из уг замейой каждого символа ПЕЛ на а'бЛ', Пусть й, и й,— очевидные гомоморфизмы: 6, (а) =а для або, 6,(а) =е для аб Л', 6,(а) =-е для або и 6,(а') — '=а для а бЛ. Снова можно злементарио доказать индукцией, что (1) если А= >о ич то (А, А)ьг (/г,(иг), 6,(иг)), (2) если (А, А.) гг (х, и), то существует такая цепочка иг, что А=ьо иг и Ь (иг).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
