Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 113
Текст из файла (страница 113)
6.2.2. Постройте двухмагазинный анализатор, корректный для грамматики 6а. 6.2.3. Какие из следующих грамматик являются грамматнкамн Колмерауэра? (а) б, (б) Я вЂ” аА ) ЬВ А. ОА! ~01 В- ОВ11|011 (в) Я- аАВ!Ь А ЬЯВ !'а В- а " .2.. 6..4. Покажите, что если грамматика 6 †приведенн и обратимая и и () р*рв' = 8, р'р П )|Х'= хэ', то онз однозначная. 555 6.2.5. Покажите, что каждая обратимая регулярная грамма- тика является грамматикой Колмерауэра. 6.2.6. Покажите, что каждая обратимая грамматика в нор- мальной форме Грейбах, для которой р'|А П )А =.. 8, является грам- матикой Колмерауэра.
6.2.7. Покажите, что двухмагазинный анализатор нз при- мера 6.12 корректен для соответствующей грамматики. 6.2.8. С помощью теоремы 6.6 покажите, что каждая грам- матика простого предшествования является грамматикой Колме. рауэра. 6.2.9. Докажите лемму 6.9. 6.2.10. Докажите лемму 6.10. 6.2.11. Пусть б — грамматика Колмерауэра с отношенияме предшествования Колмерауэра, для которой индуцируемый ек двухмагазинный анализатор не только анализирует каждую це. почку из Е(6), на также корректно анализирует каждую вы.
водимую цепочку грамматики 6. Покажите, что (а) ры |), (б) РХ+ ы<, (в) р+р:-з, (г) Р+)АХ| ~ с () >. "6.2.12. Пусть 6 — грамматика Колмерауэра и ч — подмноже ство отношения р )А?.+ — р+р — )АХ+. Покажите„что отношени| = |А, ( =- рер),' — ч и > = Р'р 0 ч — это отношения предшество вання Колмерауэра, позволяющие анализировать любую выво димую цепочку грамматики 6. 6.2.13. Покажите, что каждый двухмагазинный анализато1 расходует на обработку цепочки длины и время 0(п). *6.2.!4. Покажите, что если язык Е определяется граммати кой Колмерауэра, то и ЕЯ определяется такой грамматикой.
*6.2.1о. Является ли каждан (1,!)-ОПК-грамматика грам матикой Колмерауэра? *6.2.!6. Покажите что существует такой язык Е, определя я емый грамматикой Колмерауэра, что ии Е, ни Е ие являет|и детерминированным КС-языком. Заметьте, что использававшийс. в качестве примера язык (|оЬач!(|о!=и) не детерминированный хотя его обращение — детерминированный язык. ') Это утверждение — частный случай леммы о.7; оно включено тольк Лля полноты. 55 ПРИЛОЖЕНИЕ 55' Гл. 6.
АлГОРитмы РАЗОРА с ОГРАниченными возвРАГАми е8.2.17. Говорят, что двухмагазинный анализатор Т распознает область определения отношения т(Т) независимо от того, связан ли как-нибудь выдаваемый им „разбор" с входной цепочкой. Покажите, что каждый рекурсивно перечислимый язык распознается некоторым детерминированным двухмагазинным анализатором. Укаааниег Полезно сделать исходную грамматику неоднозначной. Олтк«эьипая проблема 8.2.18. Дайте характеристику класса КС-грамматик, однозначных или нет, для которых существуют детерминированные двухмагазинные анализаторы, индуцируемые непересекающимися отношениями „предшествования".
Замечания по литературе Грвммвтннн Колмервуэрэ и теорема 66 вперные были опубликованы в работе Колмерзуэра «1976[. Грэй и Хэррнсои [1969[ связэлн эти идеи с понятием множества знаменательных символов. Коэн н Чулнн [19711 рассмэтризвли 1й (й).схему виэлизэ, эффеитивно прнмсняюпгую возвраты '). х) См.
также рабопя Лаврова и Ордяна «1976[ я Ордянэ 11976«.-Прим. перев. В приложении даются синтаксические описания четырех языков программирования, среди них (1) простой язык, служащий базой расширяемого языка; (2) Снобол 4, язык для обработки строк; (3) ПЛ 360, машинный язык высокого уровня для вычислительных машин ИБМ 360; (4) РА«., язык, объединяющий лямбда-исчисление с операторами присваивания Эти языки выбраны потому, чта ани не похожи друг на друга. Кроме того, их синтаксические описания достаточно малы, чтобы ими можно было пользоваться в некоторых упражнениях на программирование, приведенных в нашей книге, не расходуя слишком многа времени (как человека, так и машины). При атом выбранные языки довольно сложны, и в них представлен целый букет проблем, с которыми приходится сталкиваться при реализации более традиционных языков программирования, таких, как Алгол, Фортран, ПЛ/1.
Синтаксические описания последних можно найти в следуюших источниках: (1) Алгол 60 в «Наур, 1963), (2) Алгол 68 в [Ваи Вейнгаарден, !9691, (3) Фортран в [АНС, 1966) (см. также [АНС Подкомитет, 1971«), (4) ПЛ11 в отчете Венской лаборатории ИБМ, Тм 26.096"). Г«Л.
СИНТАКСИС РАСШИРЯЕМОГО ЯЗЫКА Опишем язык, предложенный Ливенвортом 119661 в качествс базового языка, который можно расширять с помощью синтак сических макросов. Синтаксис этого языка будет представлеь т) См. более доступную книгу; Универсальный язык прогрзммвровэии~ РЬ/1, изд-во „Мир", М., 1968.— Прим. перез. пгилащенин и ! СИНТАКТ.И 1'а в виде двух частей. Первая состоит из правил высокого уровня, определяющих базовый язык.
Этот базовый язык можно использовать сам по себе как алгебраический язык с блочной структурой. Вторая часть описания — множество правил, определяющих механизм расширения, который позволяет описывать новые виды операторов и функций с помощью оператора макроопределения, порождаемого правилом 37. Это правило говорит о том, что частным случаем <оператора> может быть <макроопределение>, а оно по правилам 39 и 40 может быть либо <макроопределением оператора), либо <макроопределением функции>.
Правила 41 и 42 показывают, что каждое из этих макроопределений включает <макроструктуру> и (определение>. <Макро- структура) определяет форму павой синтаксической конструкции, а <определение) дает ассоциируемый с ней перевод. <Макро- структура> и <определенне> могут быть любыми цепочками, состоящими из терминальных и иетерминальных символов, но при условии, что каждый нетерминал, встречающийся в <определении>, должен также встречаться в <макроструктуре). (Это похоже на правило СУ-схемы, но здесь не налагается ограничений на то, сколько раз можно брать один иетермииал в транслирующем элементе,) Мы не даем явных правил для <макроструктуры> н (определения>.
На самом деле определение, говорящее о том, что каждый нетерминал из <определення) должен встречаться в (макроструктуре), нельзя выразить с помощью контекстно.свободных правил. Правило 37 указывает, что вместо <оператора> в выводимую цепочку можно подставить любой частный случай <макроструктуры), определенный в некотором макроопределении оператора. Аналогично, правило 43 позволяет любой частный случай <макроструктуры>, определенный в некотором макроопределении функции, подставлять в выводимую цепочку вместо (первичного). Например, оператор суммирования можно определить с помощью вывода (оператор) =Ф (макроопределение) => <макроопределение оператора> =о згласго <макроструктура> ЙеИпе <определение) епйпасго Возьмем в качестве <макроструктуры) цепочку зшп (выражение)ел вИЬ <переменная> -<выражение>ьч 1о (выражение>аа Перевод этой макраструктуры можно определить, взяв в качестве ее определения цепочку Ьей1п 1оса1 1; !оса! з; 1аса1 г; 1 — 0; <переменная> — <выражение>"', г: И <переменная) > <выражение>гв 1Ьеп Яо1о з; 1 -1+ <выражение>"', <переменная> <переменная>+ 1; да1а г; з: гезвИ 1 епб Тогда, если написан оператор япп а а'ИЬ Ь вЂ” с 1о д то до того, каи он будет проанализирован в соответствии с пра вилами высокого уровня, его надо перевести в цепочку Ьей)п !оса! 1; !оса! з; 1оса1 г; 1 -0; Ь -с; г: И Ь> д 1Ьеп да1о з; 1 -1+а; Ь -Ь+1; йо1а г; гк гезцИ 1 елей И, наконец, нетерминалы <идентификатор>, (метка> и (ко станта> †э лексические единицы (лексемы), которые мы оста ляем неопределенными, а читателя просим либо рассматрнва их как терминальные символы, либо определить нх, как еь нравится, и добавить эти определения.
Правила высокого уровня 1 <программа>— <блок> 2 <блок>— Ьей1п <необязат лакал идентифры> <список операторов> е 3 <необязат лакал идентифры> <необязат лакал идентифры> !оса! (идентификатор); ~ е 5 <список операторов>— (оператор>~<список операторов>; (оператор) 7 <оператор> <переменная> <выражение>!йо1о <идентификатор>[ И <выражение> 1Ьеп <оператор> ~ <блок> ~ гезвИ <выражени <метка>; <оператор> ПРИЛОЖБНИБ А 13 <выражение>- <арифмет выражение> <операция отнбшения> <арифмет выражение) ! (арифмет выражение) 15 <арифмет выражение>- (арифмет выражение) (опер типа слож) (терм) ! (терм) 17 <терм>- (терм) <опер типа умнож) <первичное>! <первичное) 19 (первичное> <переменная)!<константа>!!<выражение>1!<блок) 23 <переменная>- (идентификатор>!(идентификатор> !<Список выражений>) 25 <список выражений>— (список выражений), <выражение)!(выражение> 27 (операция отношения>- <!<!=!~!>!> 33 (опер типа слож)- +!— 35 <опер типа умнож>— Р!7 Механизм расширения 37 <оператор)— <макроопределение)!(макроструктура) 39 <макроопределение>- <макроопределение оператора)!<макроопределение функции) 41 <макроопределение оператора> япасго (макроструктура> деПпе <определение> епбп2асго 42 <макроопределение функции> 1гпасго (макроструктура> бейле <определение> епйпасго 43 <первичное)— <макроструктура> Замечания еп к !.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
