Главная Промышленная автоматика. (а) неразрешимость проблемы „/, (Ga)/(G)?-" (б) разрешимость проблемы „L (G) L (GJ?" *2.6.I8. Пусть Pj и Р3 -ДМП-автоматы. Докажите неразрешимость следующих проблем: (а) L{Py)U LiP)-детерлпшированный КС-язык? - (б) L(Pi) 1(2)-детерминированный КС-язык? (в) L{P,)L{P,)-? (г) L(Pi)*-детерминированный КС-язык? **2.6.19. Покаясите, что для детерминированных МП-автоматов Р проблема, регулярен ли язык L{P), разрешима (в противоположность упр. 2.6.14(6)). **2.6.20. Пусть/.-детерминированный КС-язык и R - регулярное множество. Покажите, что следующие языки являются детерминированными КС-языками; (а) LR] (б) LIR; (в) L\jR: (г) MAX(L); (д) MIN(L); (е) LnR. Указание: В пунктах а, б, д, е пусть Р - ДМП-автомат, распознающий Д, а М -конечный автомат, распознающий R. Надо показать, что существует ДМП-автомат Р, который моделирует Р, ио при этом в каждой ячейке магазина хранит такую информацию: „Для каких состояний р распознавателя УИ и 9 распознавателя Р существует цепочка w, переводящая М из состояния р в заключительное состояние и допускаемая распознавателем Р, если он начинает работу в состояни1[ q и данная ячейка расположена наверху магазина?* Надо показать, что для каждой ячейки эта информация имеет лишь конечный объем и что Р может следить за ее сохранением, когда магазин растет нли убывает. Как только Рпостроен, четыре упомянутые ДМП-автомата строятся относительно легко. 2.6.21. Покажите, что для детерминированного КС-языка L и регулярного множества R следующие языки могут не быть детерминированными КС-языками: (а) RL; (б) {x\xRL}; (в) {x\t/x£L для некоторого y£R}\ (г) h{L), где h-гомоморфизм. 2.6.22. Покажите, что если h - гомоморфизм н L-детерминированный КС-язык, то Л" (Д)-~тоже - детерминированный КС-язык. **2.6.23. Покажите, что если язык QcPc луст, то он неоднозначный КС-язык. **2.6.24. Докажите, что проблема, порождает ли КС-грамматнка G неоднозначный язык, неразрешима. *2.6.25. Покажите, что грамматика из примера 2.46 однозначна. **2.6.26. Докажите неоднозначность языка U г- W /-i= {йба"/?" I m,/7> 1} и L = {abVb"\m,n\). **2.6.27. Покажите, что КС-грамматика с правилами S--aSbSc \ aSb I bSc \ d неоднозначна. Однозначен ли порождаемый ею язык? *2.6.28. Покажите, что для ДМП-автомата Р проблема, обладает ли ЯЗЫК L{P) префиксным свойством, разрешима. Разрешима ли эта проблема для произвольных КС-грамматик? Определение. Языком Дика называется КС-язык L, порождаемый грамматикой G ({S}, S, Я, S), где2 {а, ..., а, ?7, ..., i?} для некоторого \ и Р состоит из правил 5 ->5S tzSfoj a.Sb I UbSb, **2.6.29. Покажите, что для данного алфавита S можею найти такие алфавит 2, язык Дика LS* и гомоморфизм h из S* в 2*, что для любого КС-языка L 2* существует регулярное множество Р, для которого h (LdI] R) = L. *2.6,30. Пусть L -КС-язык и 5(Л) = {i I/ = для некоторой цепочки wL). Покажите, что S {L) можно представить в виде объединения конечного числа арифметических прогрессий. Определение. Назовем п-вектором набор из п неотрицательных целых чисел. Если у -(а, ..., а„) и (б, ,,., fj) /г-векторы и с-неотрицательное целое число, то 11 +12 = (i + foj, ...,а + Ь) Hcvy{cay, ...,са,). Множество 5 /г-векто-ров называется линейным, если существуют такие /г-векторы • •. й. что 5= {у I vvCyVy .. . -\CkV для некоторых неотрицательных целых чисел с, ...,cj. Множество д-векгоров называется полулинейным, если его можно представить в виде объединения конечного числа линейных множеств. **2.6.3i. Пусть 2 = {aj, Обозначим через 41=й () число вхождений символа b в цепочку х. Покажите, что для каждого КС-языка множество {(# (i). {w), ..., {w))\ wL} полулинейью. Определение. Индексом (или активной емкостью) вывода называется наибольшее из чисел вхождений нетерминалов в цепочки, образующ[[е этот вывод. Индексом I (w) цепочки w£L{G) называется наименьший нз индексов всевозможных выводов этой цепочки в G. Индекс грамматики G--это / (G) max {/(tc) €L(G)}. Индекс КС-языка L -это ] {L) = mm {I (G) \ L = L{G)}. гл. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ **2.6.32. Покажите, что индекс грамматики G с правилами S-SS 1051 \ е бесконечен. Покажите, что индекс языка L(G) бесконечен. *2.6.33. КС-грамматика C==(N, X, Р, 5) называется грамма-такой с самовставлением, если А * uAv для некоторых и и и из 2 (обе цепочки и.н v непустые). Покажите, что КС-язык!, не регулярен тогда и только тогда, когда все порождающие его грамматики являются грамматиками с самовставлением. Определение. Пусть S - класс языков и языки LSJ и LaSa принадлежат Пусть а и b - новые символы, ие входящие в SjUg. Говорят, что класс S замкнут относительно (1) маркированного объединения, если аЬЬ bL .Sf; (2) маркированной конкатенации, если LaL ё -Sf; (3) маркированной итерации, если {aL)* 2.6.34. Покажите, что класс детерминированных КС-языков замкнут относительно маркированных объединения, конкатенации и итерации. *2.6.35. Пусть G(N, S, Р, S) - (не обязательно контекстно-свободная) грамматика, где каждое правило из Р имеет вид хАу-хуу, причем х,у*, Л € N и у С (N U 2)*. Покажите, что L(G) -КС-язык. **2.6.36, Пусть Gi-(N„ 2„ Р,, S,) и G, = (N„ 1„ P,,S,) КС-грамматики. Докажите неразрешимость проблем „{a\S-=*af}= Открытая проблема 2.6.37. Разрешима ли для ДМП-автоматов Pj и Р проблема эквивалентности, т. е. ,X(Pi)i(2)?" Проблемы для исследования * 2.6.38. Разработайте методы доказательства того, что некоторые грамматики однозначны. В силу теоремы 2.30 нельзя найти метод, который работал бы для произвольной однозначной грамматики. Однако хорошо было бы получить технику, применимую к широкому классу КС-грамматик. 2.6.39. Родственная область исследования--поиск больших классов однозначных КС-языков. Следует иметь в виду, что, как будет показано в гл. 8, детерминированные КС-языки образуют один из таких классов. 2.6.40. Найдите преобразования, превращающие грамматики из некоторых классов неоднозначных грамматик в эквивалентные однозначные. ЗАМЕЧАНИЯ по ЛИТЕРАТУРЕ Замечания по литературе Мы не будем пытаться указать здесь все многочисленные работы, касающиеся коитекстно-свободных языков. В Книгах Хонкрофта я Ульмана [1969], С. Гинзбурга [1966], Гросса и Лантеиа [1970] ) и в работе Бука [1970] приведены большие библиографии по теории КС-языков. Теорема 2.24 (лемма Огдена) взята из работы Огдена [19б8]. Бар-Хиллел и др. [1961] доказали несколько из основных теорем.о свойствах замкнутости и алгоритмических проблемах для КС-языков. Гинзбург и Грейбах [1966] исследовали многие из основных свойств детерминированных КС-языков. Кантор [1962], Флойд [1962а], Хомский и Шютценберже [) 963] независимо друг от друга обнаружили, что проблема однозначности для КС-грамматик неразрешима. Существование неоднозначных КС-языков было замечено Париком [199Б]. Неоднозначные КС-языки подробно рассматриваются в книгах С. Гинзбурга [1966] и Хопкрофта и Ульмана [1969]). Многие из результатов, сформулированных в упражнениях, опубликованы. Упр. 2.6.19 взято из работы Стнрнза [1967]. Конструкции, указанные в упр. 2.6.20, подробно описаны у Хопкрофта и Ульмаиа [1969]. Теорема из упр.. 2.6.29 доказана С, Гинзбургом [1966. Результат из упр. 2.6.31 известен . как теорема Парика и впервые был получен Париком [1966]. Упр. 2.6.32 взято из работы Саломаа [1969б[, упр. 2.6.33 -из статьи Хомского [1959а], а результат из упр. 2.6.36 принадлежит Блатнеру [1972]3). 1) А также в книге Гладкого [\973].-Прим. перев. 2) Отметим также, что теорема Из упр. 2.6.24 впервые доказана Гладким [1965] и независимо Гинзбургом и Уллианом [1966].-Яр«л. перев. ТЕОРИЯ ПЕРЕВОДА Перевод (или трансляция) i) -это некоторое отношение между цепочками, или, другими словами, это некоторое множество пар цепочек. Компилятор определяет перевод, образуемый парами вида (исходная программа, объектная программа). Если компилятор состоит из трех фаз-лексического анализа, синтаксического анализа и генерации кода, то каждая из них сама является переводом. Как отмечалось в гл. I, лексический анализ можно рассматривать как перевод, при котором цепочки, представляющие исходные программы, отображаются в цепочки лексем. Синтаксический анализатор отображает цепочки лексем в цепочки, представляющие деревья. Затем генератор кода переводит эти цепочки на машинный язык или язык ассемблера. В этой главе мы изложим элементарные методы определения перевода. Кроме того, опишем устройства, с помощью которых можно реализовать эти переводы, и алгоритмы, позволяющие автоматически строить такие устройства по описанию перевода. Сначала мы исследуем переводы с абстрактной точки зрения, а затем рассмотрим применимость моделей перевода к лексическому и синтаксическому анализу. Процесс генерации кода, который служит главным объектом приложения теории перевода, мы в основном изложим в гл. 9. Вообще, когда создаются большие системы, такие, как компилятор, следует разбить всю систему на части, свойства и поведение которых можно точно определить и понять. Тогда можно сравнивать алгоритмы, реализующие функцию, которую должна выполнять данная составная часть, и выбрать для нее наиболее подходящий алгоритм. Как только компоненты системы выделены и точно описаны, можно устанавливать стандарты, которым должно удовлетворять функционирование компонент, и критерий ) В дальнейшем мы будем считать эти слова синонимами, отдавая предпочтение термину „перевод". -Ярад. ред. для их оценки. Поэтому надо понять способы задания и реализации перевода, прежде чем применять к компиляторам критерии инженерного проектирования. 3.1. ФОРМАЛИЗМЫ, ИСПОЛЬЗУЕМЫЕ ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕВОДА В этом разделе мы изложим два фундаментальных метода определения перевода. Один из них-„схема перевода", которая представляет собой грамматику, снабженную механизмом, обеспечивающим выход для каждой порождаемой цепочки. В другом методе основную роль играет „преобразователь", т. е. распознаватель с выходом, который на каждом такте может выдавать цепочку выходных символов ограниченной длины. Сначала мы рассмотрим схемы перевода, основанные на коитекстио-свободных грамматиках, а потом займемся конечными преобразователями и преобразователями с магазинной памятью. 3.1.1. Перевод и семантика В гл. 2 изучались только синтаксические аспекты языков. Там мы познакомились с несколькими методами определения правильно посгроенных цепочек, или предложений, языка. Теперь мы хотим исследовать механизмы, связывающие с каждым предложением (цепочкой) языка другую цепочку, которая должна быть выходом, или результатом перевода, этого предложения. Для обозначения этого отношения между предложениями и соответствующими выходными цепочками, определяющими их „смыслы", или „значения", иногда употребляют термин „семантика". Определение. Пусть S -входной алфавит и Д- выходной алфавит. Переводом с языка 2* на язык LrA* назовем отношение Г из S* в Д*, для которого Lj -область определения, а Lg-множество значений. Если (х, у) Т, то цепочка у называется выходом для цепочки х. Заметим, что в общем -случае в переводе Т для данной входной цепочки может быть более одной выходной цепочки. Однако перевод, предназначенный для описания Языка программирования, должен быть функцией, т. е. для каждого входа должно быть не более одного выхода. Можно привести много примеров переводов. По-видимому, самый примитивный тип перевода - перевод, задаваемый гомоморфизмом. Пример 3.1. Допустим, что мы хотим перевести каждую греческую букву цепочки из мнолества S* в ее английское название. Это можно сделать с помощью такого гомоморфизма /г, что 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 [39] 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 0.0018 |