Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 48
Текст из файла (страница 48)
(Р,) г= 1. (Р,)? (г) Е(Р,)* — детермииироваггный КС-язык? *В2,6.19. Покажите, что для детерминированных МП-автоматов Р проблема, регуляреп ли язык 1. (Р), разрешима (в противоположность упр. 2.6.14 (б)). *"2.6.20. Пусть Š— детерминированный КС-язык и )? — регулярное множество. Покажите, что следующие языки являются детерминированными КС-языкамн; (а) ЕЯ; (б) Ег)?; (в) Е О )?; (г) МАХ (Е); (д) М1Ь((Е); (е) 1. П )?. В пунктах а б, д, е пусть Р— ДМП-автомат, распознающн й 1., а М вЂ” конечный автомат, распознающий 1?. Надо показать, что существует ДМП-автомат Р', который модели- Р, о прн этом в каждой ячейке магазина хранит такую М и иггг)юрмацию: г)ю: „Для каких состояний р распознавателя М д и ево я ая М из распознавателя Р существует цепочка нг, переводящая из ия в заключительное состояние и допускаемая распосостояния р в ии и анная знавател телем Р, если он начинает работу в состоян у д ь, что ложена наверху кгагазггна?" Надо показат, ем для каждой ячейки эта информация имеет лишь конечный объ, Р' ет следить за ее сохранением, когда магазин растет нли убывает.
Как только Р' построен, четыре упомянутые Д автомата строятся относительно легко. 2.6.21. Покажите, что для детерминированного К - . го КС-языка 1, и реу г лярного множества ?? следующие язык у и мог т не быть детерминированными КС-языками: (а) И.; (б) (х~х)? = Ц; (в) (х ~ ух ЕЕ для некоторого уб)?); (г) И(Е), где И вЂ” гоьюморфизьг. 2.6.22. Покажите, что если И вЂ” гомоморфизм н Š— детерминированный К -язьгк, то й КС-, то И ' (1) — тоже - детерминированный КС-язык. ""2.6.23.
Покажите, что если Язык (~~.ОРс не пУст, то он неоднозначный КС-язык. УПРАЖНЕНИЯ : *2,6.24. Докажите, что проблема, порождает лн КС-грамматика 6 неоднозначный язык, неразрешима. В2.6.26. Покажите, что грамматика из примера 2А6 однозначна. В*2.6,26. Докажите неоднозначность языка Е, ОЕ„где Е,=— (а Ь"а"'Ь'" ~ т, п)~ 1) и 1.,= (а"Ь"а"'Ь" ~ т, и 1). *Р2.6.27, Покажите, что КС-грамматика с правилами 5- а5Ь5с )- а5Ь | Ь5с ) й неоднозначна. Однозначен ли порогкдаемый ею язык? Р2.6.28. Покажите, что для ДМП-автомата Р проблема, обладает ли язык Е(Р) префиксным свойством, разрешима.
Разрешима ли эта проблема для произвольных КС-грамматик? Определение.,Чзыком Дика называется КС-язык Е, порождаемый грамматикой 6 = ((5), Х, Р, 5), где Х вЂ” (а„..., а„, Ь„..., Ь ) для некоторого И) 1 н Р состоит из правил 5- 55 ~ а,5Ь,) а,5Ь, 1... ( а,5Ь„1 с. **2.6.29. Покажите, что для данного алфавита Х можно найти такие алфавит Х', язык Дика Еоч= Х" и гомоморфнзм И нз В" в Х*, что для любого КС-языка Е ~ Х* существует регулярное множество )х, для которого И (Еп(1 )?) =1..
*2 6 30. Пусть 1.— КС язык и 5 (Е) = (г ) г =( иг( для некоторой цепочки гВЕЕ). Покажите, что 5(Е) можно представить в виде объединения конечного числа' арифметических прогрессий. Определение. Назовем и-вектором набор из и неотрицательных целых чисел. Еслгг с,=(а„..., а„) и о,— (Ь„..., Ь„)— и-векторы и с — неотрицательное целое число, то о, + о, = (а, + Ь„..., а„+ Ь„) н сс, — (са„..., са„). Множество 5 й-векторов пазываегся линейным„если существуют такие гг-векторьг о„..., ВА, что 5=(с ~ о=о,+с,с,+... +ср„для некоторых неотрицательных целых чисел с„..., сч).
Множество п-векторов называется полулипсйпым, если его можно представить в виде объединения конечного числа линейных множеств. *2.6.31, Пусть Х =(а„..., а„). Обозначим через 4ЬР(х) число вхождений символа Ь в цепочку х. Покажите, что для каждого КСязыка1:1* множество ((йЬ (гв) 4=' (ю) (ь (ш))) нгЕЕ) полулннейно. Определение. Индексом (или активной емкостью) вывода называется наибольшее нз чисел вхождений нетерминалов в цепочки, ~бр~~ующие эгот вывод. Индексом 1(иг) цепочки аг~Е(6) называется наименьший пз индексов всевозможных выводов этой цепочки в б. Индекс граиматики 6 это 1(6)=шах(1(нг)! гв ~ Е (6) ) .
Индекс КС-языка Š— это 1 (Е) = ш(п (1 (6) ~ Е =- Е (6) ) . 239 ГЛ. З. ЭЛЕМННТЫ ТЕОРИИ ЯЗЫКОВ ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ ее2.6 32. Покажите, что индекс грамматики О с правилами 5 55 ~ 05[]е бесконечен. Покажите, что индекс языка Е (6) бесконечен. "2.6.33. КС-грамматика О ==(гч, Х, Р, 5) называется грамматикой с самовставлением, если А р'ИАР для некоторых и и и из Х+ (обе цепочки и и и непустые). Покажите, что КС-языкЕ не регулярен тогда н только тогда, когда все порождающие его грамматики являются грамматиками с самовставлением.
Определение. Пусть .2' — класс языков и языки Е,с:-Х; и Ь,ыХ; принадлежат .У. Пусть а и [! — новые символы, ие входящие в Х,[)Х,. Говорят, что класс 2' замкнут относительно (1) маркированного объединения, если аЬг[) [7Езб.2' (2) маркированной конкатенации, если Е,аЕ с.йг; (3) маркированной итерации, если (аЕг)*Е 2'. 2.6.34. Покажите, что класс детерминированных КС-языков замкнут относительно маркированных объединения, конкатенации и итерации.
*2.6.36. Пусть 6=(г[, Х, Р, 5) — (не обязательно контекстно- свободная) грамматика, где каждое . правило из Р имеет вид хАу — хуу, причем х, уЕХ', А Егч[ и 76 (гч [) Х)". Покажите, что Е (О) — КС-язык. ""2.6.36. ПУсть бг=()Ц„Х„Р„5,) и О,=(~„, Х„Р„5) КС-грамматики.
Докажите неразрешимость проблем „(сс15;Рога)= (р! 5з-оо,]])р" и и(а(5,20!а) =(и!5з~о гр)?ь Открытая проблема 2.6.37. Разрешима ли для ДМП-автоматов Р, и Р,' проблема эквивалентности, т. е.,Е (Р,) =- Е (Р,)Р" дроблемы для исследования 2.6.38. Разработайте методы доказательства того, что некоторые грамматики однозначны. В силу теоремы 2.30 нельзя найти метод, который работал бы для произвольной однозначной грамматики. Однако хорошо было бы получить технику, применимую к широкому классу КС-грамматик. 2.6.39. Родственная область исследования — поиск больших классов однозначных КС-языков. Следует иметь-в виду, что, как будет показано в гл. 8, детерминированные КС-языки образуют один из таких классов.
2.6.40. Найдите преобразования, превращающие грамматики из некоторых классов неоднозначных грамматик в эквивалентные однозначные. 240 Замечания по литературе Мы ве будем пытаться ухазать здесь все многочисленные работы, касаю. шиеся контекстно-свободных языков. В книгах Хопкрофта я Ульмана [1969[, С Гинабурга [!9661 Гросса и Лантеиа [1970] г) н в работе Бука 11970[ привелены большие библиографии по теории КС-языков. Теорема 2.24 (лемма Огдена) взята из работы Огдена [! 9661. Бар-Хиллел „ др [19611 доказали несколько нз основных теорем о свойствах замкнутости н алгоритмических проблемах для КС-языков.
Гинзбург н Грейбах [1966] исследовали многие из основных свойств детерминированных КС-языков. Кантор [19621, Флойд [!962а], Хомский н Шютценберже 1!963] независима друг от друга обнаружили, что проблема однозначности для КС-грамматик неразрешима. Сушестеованне неоднозначных КС-языков было замечено Пари-, ком [19%].
Неоднозначные КС-языки подробно рассматриваются в книгах ' С. Гинзбурга П966] н Хопкрофта и Ульмана [1969]!). Многие нз результатов, сформулированныхвупражнениях, опубликованы. Упр. 2.6.!9 взято из работы Стнрнза [19671. Конструкции, ухазаниые в упр. 2.6.20, подробно описаны у Хопкрофта н Ульмаиа [1969]. Теорема из упр. 2.6.29 доказана С. Гинзбургом [!966!. Результат из упр. 2.6.31 известен как теорема Парика и впервые был получен Париком [!966]. Упр. 2.6.32' взято нз работы Саломаа [19696[, упр.
2.6.33 в нз статьи Хомского [1969а1, а результат из упр. 2.6.36 принадлежит Блатнеру [1972]з). ') А также в кинге Гладкого [!973]. — Прил. перев. ') Отметим также, что теорема аз упр. 2.6.24 впервые доказана Глад. кнм ]19661 н независимо Гинзбургом и Уллианом [!966].— Прим. перез. ам Формализмы. Использеемыа для Определения пеРРВОдА ТЕОРИЯ ПЕРЕВОДА Перевод (или трансляция) ') — это некоторое отношение между цепочками, или, другими словами, эго некоторое множество пар цепочек. Компилятор определяет перевод, образуемый парами вида (исходная программа, объектная программа).
Если компилятор состоит из трех фаз — лексического анализа, синтаксического анализа н генерации кода, то каждан из них сама является переводом. Как отмечалось в гл, 1, лексический анализ можно рассматривать как перевод, при котором цепочки, представляющие исходные программы, отображаются в цепочки лексем. Синтаксический анализатор отображает цепочки лексем в цепочки, представляющие деревья, Затем генератор кода переводит зти цепочки на машинный язык илн язык ассемблера. В этой главе мы изложим элементарные методы определения перевода. Кроме того, опишем устройства, с помощью которых можно реализовать эти переводы, и алгоритмы, позволяющие автоматически строить такие устройства по описанию перевода. Сначала мы исследуем переводы с абстрактной точки зрения, а затем рассмотрим применимость моделей перевода к лексическому и синтаксическому анализу. Пропесс генерации кода„который служит главным объектом приложения теории перевода, мы в основном наложим в гл.
9. Вообще, когда создаются большие системы, такие, иак номпилятор, следует разбить всю систему на части, своиства и поведение которых можно точно определить и понять. Тогда можно сравнивать алгоритмы, реализующие функцию, которую должна выполнять данная составная часть, и выбрать для нее наиболее подходящий алгоритм. Как только компоненты системы выделены и точно" описаны, можно устанавливать стандарты, которым должно удовлетворять функционирование компонент, и критерий ') В дальнейшем мы будем считать этн слова синонимами, отдавая предпочтение термнау „переаод".— Прим. рад.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
