Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 64
Текст из файла (страница 64)
Удовлетворяет лп грамматнка упр. 5.! ограннченням ! и 2 ддя нясходяшего грамматнческого разбора с просмотром вперед на один символе Еслн нет, найдите зкеназлентный синтаксис, который удовлетворяет этим огранкченням, Изобразите этот синтаксис в виде сннтакснческого графа н структуры данных, нспольз>смой в програмлге 5,3 Упражнения оэг 6.3. Выполните упр, 5.2 для следующего синтаксиса: В и=А А к= В) И С Енеп А! И С (Ьеп А е!зе А В к=В=С Си= И С (Ьеп С е(зе С) В Примечание. Если это необходимо, вы можете удалить илн заменить какую-либо конструкцию, чтобы сделать применимым односимвольиый ипсходящпй грамматический разбор. 5А. Рассиотрите нисходящий грамматический разбор для следующего синтаксиса: 3 к=А Ап=В+А)РС Вп=0)0*В В и= х((С) Си=+к(-х На сколько символов вперед нунсио смотреть, чтобы анализировать предложения согласно этому сннгаксису? 5.5.
Преобразукте описание ПЛ/О (рис. 5А) в эквивалентное множество порождающих правил БНФ. 5.6. Напишите программу, которая определяет множества начальных и внешних симоволов (.(5) и р(5) для каждого иетерминатьного символа Я в заданном множестве порождающих правил. Примечание. Используйте часть программы оВ для построения внутреннего представлениь синтаксиса з виде структуры данных. Затем работайте с этой связанной струнтурой. 5.7.
Рагширьте язык ПЛ/О и его транслятор, включив в него следующие операторы: (в) Условный оператор вида (оператор) и = И (условие) (Ьеп (оператор ) е!зе (оператор) (Ь) Оператор цикла вида (оператор ) и = гереа! (оператор) (; (оператор) ) ппбй (условие) Есть ли какие-либо особые трудности, которыс могли бы привести к изменению формы нли ~гптсрпретапин указанных г пграгороа? Вводить кзкие-то дополятыельные команды в систему машины ПЛ/О вы не должны. 5.5. Расшврьте язык ПЛ?О и сто транслятор, добавив в него параметры процедур.
Рассмотрите два возможных решения и выберите одно из них для реализации: (а) Параметры-зпаченид Фактические параметры обращения являются выражениями, значения которых присваиваются вокальным всременным, представляющим формальные параметры, заданные а заголовке процедуры. (Ь) Паралетрьрперемепные. Фактические параметры являются переменнымв. Прн вызове они подставлнются нз место формальных э, мгруктура языков И грпнглягоры параметров, Параметры-переменные реализую~ся с помощью передачи адресов фактических параметров в места, выделеннме для формальных параметров Доступ к фактическим параметрам осуществляется косвенно через переданный адрес. Следовагельно, параметры-переменные обеспечивают доступ к переменным, определенным эне пропедур, и поэтому правила области определения можно изменить следующим образом: в каждой процедуре непосредственно доступны только локальные переменные; доступ к не- локальным переменным возможен только через параметры 6,9.
Растнрьте язык ПЛ(0 н его транслятор, добавив переменные-мас. сипы. Пусть диапазон индексов такой переменной а указывается в ее описании как чаг и(!опп Ыдй) 5.10. Модифнцнруйте транслятор ПЛ)0, чтобы оп формировал рабочую программу для имеющейся у вас вычислительной машины. Примечание. формируйте программу на языке ассемблера, чтобы нзбелгать проблем, связанных с загрузкой. На первом этапе не пытайтесь оптимизировать рабочую программу, например использовать регистры. Возможная оптимизация должна включаться лишь на чет. вертом этапе уточнеяня трапслнтора. 531.
Расширьте программу 5.5 в программу, называемую ргеИупжлг (акра. сивая псчэтьэ). Задача этой программы — читать тексты ПЛ(0 и печатать их н форме, которая естественным образом отражает структуру текста прн помощи соответствующего разделения на строки и абзацы. Вначале аккуратно определите правила делении на строки и абзацы, основанные на синтаксической структуре ПЛ/О; затем реализуйте нх, вставив операторы печати в программу 6.5. (Разумеется, из сканера нужно убрать операторы печати.) ЛИТЕРАТУРА 51. АЛ!51Л)4Х 1!.
Тйе Мерной о1 5(гис(нгед Рго8гапгпмпй Лрр1!ед 1о 15е Оесе1ортеп1 о( а СотрВег. — (л1еглалола! Со!пргг(глй Бртроягпт 7973, Л ОйпГйег с1 а1., едя.. Авя1егдат НогВмНо)!апд Рпй)!я!стд Со,, 1974, 93 — 99. 5.2. СОВЕ% О. Л, ООТГ)ЕВ С. С. Л Е)я1 61гнс1пге Готт о1 Огатвагя (ог Зупгасгт Лпэ!узць — Сотух Бигоедя, 2, )со. 1, 1970, 65 — 82. 53.
РЕОУ0 Р %. 71ш Зуп1ах о1 Рго2гэвв п2 1эпипайес — Л Зигчеу.— /ЕЕЕ уганя., ЕС-13, 1964, 346 — 353 5.4. ОНА О. Совр)1сг Сопя(~ис(юп 1ог О!8йа) Соврц1егя. — )с)есч-Уогй: %!)еу 1971. !Имеется перевод: ГРНС Д. Конструирование компиляторов хля цяфровык вычислительных машин.— Мл Мнр, !975.) 5.5. Кй!СТП О. Е. Тор-дошл Буп1ах Лпа!уя(я. — Лгта уп)оггггпЛго, 1, Ио, 2, 1971. 79- 110.
5.6. 1.В%13 Р. М., ЗТЕАй)48 9, Е. Зуп1ахнВгес1сд ТгапядцсВоп, Л АСЛЕ !5, Ыо. 3, 1968, 465 — 488. 5.7. г)ЛПВ Р. )серег! оп Гле А18омВтт'с Еапйиаяе ЛЕВОЕ 60. — АСАЕ 6, Ио. 1. !963, 1 — !7. 5.8. ЗСНОВКЕ О. ЛГ. МЕТЛ П, А 5уп1ах-оНеп1ед Совр((ег %г!1!пн 1.апКиаке. — Ргог, ЛСМ МаЛ, Соп!., 19, 1964, 0 1 3. 1 — 11. 6.9. %!РТН 74. Тйе 0ая!8п о1 а РЛЗСЛЕ Сотрйег. — Бо)1ааге — Ргпггке апд Ехрелепге, 1.
Ио, 4, 1971, 309 — 333. ПРИЛОЖЕНИЕ А ззноукаствО сммВОлОЗ Аяс11 Порядковый номер символа опрелеляегся по его координатам и таблице как ого'(са1 16 ~ х+ о. Символы с порядковыми номерами от 0 до 31 и 127 — так называемые рлравля;оигие силоолок используемые для пере. да~1и данных и управления устройствами. Спмвол с порядка. вым номером 32 есть пробел. 0 пог Йо 1' зоЬ дс1 2 згх дс2 3 е1х йсз 4 ео', вс4 5 соя пад 6 ас1с зуо Ьег егь Я Ьз с«а 9 Ьз еза 10 1Г зоЬ 11 зз езс 12 11 гз 13 с«яз 14 зо тз 15 я' аз О 1 о Ф з з 4 ас б Ф 7 С 8 9 е С ас 1 > ( ф А в с о Е О н 1 К ь М р 0 а и Ь в с 'Г 4 е зг 1 1ЗГ д Х Ь У 1 е 3 1с 1 пз т о Р я в к У ( ! ) Ю бе1 ПРИЛОЖЕНИЕ В СИНТАКСИЧЕСКИЕ ДИАГРАММЫ ПАСКАПФ Цепое без знака Приловсемие В Простое выр:оковке Выражение Свисав па рамс с ров Прплоясенпе В Оператор епо Ьергп сазе выраженне оа епд оператор ангре оператор гереаз по — г оператор О- переменная еггзй цото СЭ пелоебез знака Фог нмя Г з константа ейе оператор ХКАЗАТЕПЬ ПРОГРАММ 1.1 !.2 1.3 !.4 2.1 2.4 25 2.6 2.7 2.8 2.9.
2.1 0 2.1 ! 2.12 2.13 2.11 2.15 2,!6 2.17 Вычисление степеней двойки 30 Сканер 42 Чтение вещественного числа 63 Печать вещественного числа 65 Сортировка простыми вклю- чениями 79 Сортировка бинзрнымн вклю- чениялщ 80 Сортировка простым выбором 82 Сортиропна методом пузырь- ка 84 Шейкер-сортнровка 86 Сортировка Шелла 89 Просеивание 93 Пирамидальная сортировка 95 Разделение 97 Быстрая сортировка 99 Нерекурсниная версия бы- строй сортировки 100 Поиск Ф-го элемента !05 Сортировка простым слия- нном 114 Сортировка естественным слиянием 12! Сортировка сбалансирован- ным слиянием !26 Многофззнзя сортировка 138 Распределение начальных се.
рий с помощью пирамиды 145 Кривые Гильберта 157 3.2. Кривые Серпинскога 16! 3.3. Кол коня !67 3.4. Восемь ферзей (одно ращение) 172 3.5. Восемь ферзей (все решения) 174 3.6. Устойчнвыс браки 180 3.7. Оптимальная выборка 184 4.1. Включение в список 204 4.2. Топологическая сортировка 2Г8 4.3. Построение идеально сбалансированного дерева 227 4.4. Поиск с включениями 236 4.5.
Построение таблицы перекрест. пых ссылок 240 4.6. Построение оптичального дерева поиска 274 4.7. Поиск, вкллоченпе и удаление в Б-дереве 290 4.8. Построение таблицы перекрестных ссылок с кспользоизиием функций расстановки 308 5.1. Грамматический разбор лзя синтаксиса яз примерз 5 334 5.2. Грамматический разбор зля езыка (6.12) 343 о.З, Транслятор лля языка (5.13) 345 5,4. Грамматический разбор зля ПЛ10 356 5.5.
Грамматлщескпй разбор для ПЛлО с восстановлением прп ошибках 368 5,6. Транслятор для ПЛ/О 380 УКАЗАТЕЛЬ Адельсон-Вельский 248 Адрес 44, 48 — збсо.потный 374 — базовый 374 — возврата 374 — относительный 374 Алгол-60 17, 320 Алгорити включения в Б-дерсзо 285 — — в ББ-дерево 296 — — в сбалансированное дерево 254 -- — в список 200 — вып1сльчшп и-го фшыориглького ясла 153 — грамматического разбора 324 — ;шнейзого просмотра 203 — поиска чедкапьг 103 — — по дереву с включением 233 — построения кустарников 300 — сортнргзкн акл!очешгячн бннар~п~ии 79 — — — простыни 78 — - — — с убыашогппи прнраще' пси )сгртпровкз Шелла) 87 — — выбором прость|и 81 — — обчепои простым 83 — — пнратшдзльной 90 -- — с разделешк"л 96 -- сэсзпгс.з г"тестзсппым 115 -- -- сгншкие г з1погогйгз~ ыи 137 — простым 109 — — — сбзлапснровзнл:чз1 Лчпугевып 122 -- у илеппз пт Б-дерева 288 -- — из < балапсироааниого дереза 2 6 — псйкср.сор 1чжхн 85 Лаго)пп~'.ы рткурспшгые 9 с ао,ар-: -1 9, 168 Лпал.ю алгоритмов сортяровки 79, ВО, 82, 85, 88, 94, 100, 113 Балансировка 288 Бенки дапнык 58 Барабаны чзгяитные 57 Барьер 79, 203, 233 ББ дерево с,и.
Б-лерезо бинарное Б-дереао 282 Б-дерево бинарное 295 — — симметричное 298 Буквы латинские 24 Буфер 54 Бэиер 282, 289, 295, 298 Варианты в записях 35 Вес дерева 264 Ветвь 223 Возврат 9, 168, 325 Вольтер 13 Восстановление при ошибках 373 Время патентное 58 Выборочное изменение 2Ч Выравнивание 46 Выраженве 17 — индексное 27 Высота дерева 220 Гарса 169 Гильберг 156 Глубина дерева 220 Горизонтальное распределение 134 Готлиб 267 Грамматический разбор 10, 328 — — нисходящий 323 — — целеориентированный 328 Граф распознавапвя 328 — свнтаксичсскпй 328 — — детерминированный 332 Графы 19 Дзпаыс 11 Дейкстра 7, 12 Декартово ировзведсиис 31 Декартовы координаты 15, 36 Дерево 10, 19, 219 — — АВЛ-сбалансированное 248 — бинарное 223 — вырожденное 220 — идеально сбалансированное 226 — лексчкографнческое 238 — оптимальное 263 — поиска 231 — сильно ветващееся 223 — сортировни 91 аказагазь — упорядоченное 220 — Фибоначчи 249 2.3 дерево 295 Диаграмма зависимости 361 Днзъюнкция логическая 23 Диски магнитные 57 Дискриминант типа 36 Длина пути 220 — — взвешенная 261 — — внешнего 220 — — янутреннего 220 Доступ последовательный 53 — прямой 58 — случайный 25 Заглядывание вперед 55, 68 Заголовок спкска 314 Задача об устойчивых браках !74 — о восьми ферзях 169 — о ходе коня 164 — оптимального выбора 182 — поиска медианы 103 — построения школьного распнсапяя 41 Запись !гесогб) 8, 31, 48 — с вариантами 36 Запись бесскобочная 377 — инфиксная 230 — польская 377 — постфнксная 230 — префнксная 230 Инвариант никла 28 Индекс 26, 44 Интерпретатор 373 Искусственный интеллект 163 Итерация 9, 99, 154 Карта (индексов) 123, 128 Квантнль 105 Ключ 76, 303 Ключей преобразование 303 Ключи переменной дляны 318 Кирг 77, 86, 134, 144, 264 Кольца 19 Конкатенация 51, 52, 54 Константа 17 Конструктор 20 — записи 32 — массива 26 Контекстная зависимость 322 Конфликт 304 Конфликтов разрешение 304 Коныонкции логическая 23 Кооршшаты 15, 31, 36 — декартовы 15, 36 Корень дсрева 220 Коэффициент заполнения 312 — использования памяти 46 Кривая Гильберта !56 — Сзрлиискозо 158 Кустарники 299 Лаидис 248, 249 Лента 54 — магнитная 108 Лист дерева 220 Лорин 77 Лукагеаич 377 Мак-Вити 179 Мак-Крейт 289 Мантисса 15 Массив 19, 25, 44 Матрица 29 Магпвиа ПЛ/О 373 Медиана 101, 103 Метасимволы 320 Метод деления пополам 28 — пузырька 84 — рассеянных таблиц 307 Мни!нести объединение 40 — пересечение 40 — разность 40 — сложение 40 — умноженне 40 Множество 15, 19, 38 Множество-степень 38 Множеству принадлежность 40 Моррис 306 Нотация 52 Область переполнения 306 Обход дерева 229 Оператор варианта 37 — присоединении 34, 286 — процедуры 190 — услввный 190 — цикла 29 — — с параметром 190 — — с предисловием 190 Операция булевские 23 — над файлами 54 — отношений 40 — преобразования 20 7/О-операции 62 Операция 17, 18, 19 Описание 17 Опробирование квадратичное 307 — линейное 306 Открытая адресация 306 Очередь 198 Ошибки наведенные 373 Укпзатель 403 Память лля программы 373 — оперативная 295 //аскаль 8, 11, 16, 19, 62 Переменная буферная 55 Переменные !7, 23 Псреупорядоченне списка 209 Пирамида 91 ПЛ/О 331, 349 ПЛ/! 20 Поддерево 223 Поиск бинарный 28 — в списке 202 — медианы 103 — по дереву с включением 233 — по списку самоорганнзующийся 209 Поле 48 Поле признака 36 Порядок Б-дерева 282 — частичный 211 — числа 15 Последовательность 16, 19, 52 Потомок 220 Поэтапное уточнение 11, 67, 344 Правила подстановки 320 — порождающие 320 — построения графа 329 Правило «не поднимай панику» 363 Предложения 319 Преобразование (типов) 24 — ключей 303 Приоритеты операций 40 Присваивание 19, 21, 189 Проблема пустой строки 326 Программа рабочая 373 — таблично-управляемаи 328 Просеивание 92 Просмотр на один символ вперед без возврата 323 Проход !09 — по списку 20! Процедура !90 Путь внешний 222 — внутренний 220 Разряд!5, 44 Расписание школьное 41 Распознавание предложений 322 Распределение горизонтальное !34 — памяти динамическое 51, !93 Расстановка 303 — повторная 318 Реализация 47, 50 Регистр адреса команды 374 — команды 374 — вершины стека 374 Редактирование 67 Рекурснв 9, 99, !50 — косвенная 151 — припая 151 СББ-дерево 298 Связка динамическая 374 Сегмент 57 — логический 58 — физический 58 Сектор 58 Селектор 20, 37 — записи 32 — массива 26 Серии 1!5 — максимальные 115 — фиктивные 132 — фиктивные 132 Серпинский 158 Символ 23, 40, 3!9 — начальный 320 — пустой 24 Символы внешние 363 — возобновлении 363 — нетерминальные 320 — терминальные 320 — управляющие 393 Сканер 40, 34! Слияние !09 — двухфазное 115 — естественное 115 — каскадное !49 — многопутевое !22 — однофазное 110 — простое 109 — сбалансированное 110, 122 — трехлеяточнос 109 Слова размер 44 Словарь частотный 203 Слово памяти 44 Случайный доступ 25 Смешение 48, 374 Сопрограммы !44 Сортировка 9, 74„ 77 — быстрая 96 — включениями 77 — — бинзрнымн 80 — — простымн 78 — внешняя 75 — внутренняя 75 — выбороьг 77 — — простым 81 — массивов 75 — методом пузырька 84 — обменом 83 — — простым 83 — пирамидальная 91 — слиянием 109 — — многофатная 128 — — простым !09 404 Указатель — с помощью дерева 89 — топологическан 2!1 — устойчивая 79 — файлов 75 — !!?алла 88 1-сортировка 88 Список 10, !98 — лвунаправленный 315 — циклический 314 Сравнение !9 — метадон сортировки массивов 105 Ссылки 1О, 19, 193 Стек 99, 374 Строка разрядов 49 — текущая 69 Структуры данных динамические 10 — — усложненные 8, 5! — — фундаментальные 8 — лревовидпые 219 Структурнрчвания методы !9 Схемы программ 56 Таблица рассеянная 307 — расстаноокн 305 Таблнчно-управляемые программы 328 Таккер 266 Тексты 59 Тнп базовый 18 — даниык 17 — — регулярный 26 — — скалярный !9 — — составной 30 — — стандартный 19 — индексов 26 — рекурсигпый 3!4 Транс»тят< р 1О, 17, 40, 3!9 Трансляция 40 Удаление из дерева 241 †.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
