А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 238
Текст из файла (страница 238)
Выход: матрица В линейно независимых решений Ах > О. МетОд: псевдокод алгоритма приведен ниже. Заметим, что Х [у] означает у-ю строку матрицы Х, Х [у: г] означает строки у — г матрицы Х, а Х [у: г] [и: о]— прямоугольник в матрице Х со строками у-з и столбцами и — о. о М = Ат; то = 1; са = 1; В = 1„,„; /* Тождественная матрица размером и х и *I тгЫ)е ( 1гне ) ( Р" 1. Преобразуем М [то .
т' — Ц [со . с' — 1] в диагональную матрицу с положительными диагональными элементами, и М [т': и] [со . т] = О. М [т': и] является решением. ~! т =то', / / /, с =со~ зч)н)е ( существует М [т] [с] ,—~ О, такое, что и т — т', и с — с' не меньше О ) 1 Переместить опорный элемент М [т] [с] в М [т'] [с'] путем перестановки соответствующих строк и столбцов; Поменять местами строки т и т' в В; 1Г( М [т'] [с'] ( О ) [ М[т'] = — 1Ф М[т']; В[т'] = — 1х В[т']; !!64 Приложение Б, Поиск линейно независимых решений Гог(тош=г'доп) 1 Ы1 тош ф т' и М[тош] [с'] ф О ) [ и = — (М~[тош] [с']/М [т'] [с']); М [тош] = М [тош] + и * ЛХ [т']; В1тош] = В [тош! + и а В [г']; т' = т'+1; с' = с' + 1; /* 2. Поиск решения, кроме М [г': и].
Оно должно быть неотрицательной комбинацией М [то . т' — Ц [го . гп] */ Ищем й„„..., /сг ! > О, такие, что ЙгаМ [то] [с': гп] + + Й, ~М [г' — Ц [с': гп] > О; !!'1 существует нетривиальное решение, скажем, /с, > О ) [ М [г] = йгаЛ| [го] + ' ' ' + /гг' — ъЛ'| [г Ц 1ЧоМогеоо1п = !а!ве; е!ае /* М [т': п] является единственным решением */ Л/оМогеЯо/л = 1гне; /* 3. Делаем М [го . т„— Ц [со . т] > О */ !!' 1 Л/оМогеБо/п ) ( /* Перемещаем решения М [т': и] в М [то .
т„— Ц ~/ !ог ( т = т' до и, ) Обмениваем строки г и го + т — г в М и В; т„=го+и — г +1; е!яе ( /* Используем добавление строки для поиска решений */ та — — п+ 1; !ог 1 со1 = с' до гп ) !! ( существует М [тозе] [со1] ( О, такое, что гош > то ) 1165 Ы ( существует М [г] [со1] > О, такое, что т > то ) ( Гог ( гош = го до г„— 1 ) Ы( М [гош] [со1] < 0) ( и = ИМ [тош] ]соЕ]/М [т] [со(])~; М [гош] = М[гош]+ и*М[т]; В[тош] = В [тош]+ и «В [г]; е)ве Хог ( гош = т„— 1 до го с шагом — 1 ) Ы ( М [тош] [со(] < О ) ( т„= г„— 1; Перестановка М [тош] и М [т„]; Перестановка В [тош] и В [т„]; /«4.
Делаем М [го . т„— 1] ]1: со — 1] > 0 «/ 1ог ( гош = го до т„— 1 ) Гог(со1 = 1 до со — 1) 11 ( М[тош] [со1] < 0 ) ( Выбираем г, такое, что М [т] [со1] > 0 и т < тд, и = ИМ [гош] [со(]/М [г] [со(])]; М [гош] = М [тош]+и «М[т]; В[гош] = В[тош]+и «В[т]; I«5. При необходимости повторяем со строками М [г„: и] «I К ( УоМогеоо1и или г„> п нли т„== то ) ( Удаляем строки т„-и из В; те1вти В; е!ае ( с„= т+1; 1166 Приложение Б. Поиск линейно независимых решений 1ог ( со1 = т до 1 с шагом — 1) !Г ( не существует М [г] [со1] > О, такого, что г < г„) [ ся = сто 1~ Переставить строки со1 и с„в М; гд — — г„; со =се Предметный указатель с С!ЗС, 53, 620 ч ЧЬИХ, 51, 53, 844 0 1)ага!о8, 1082 Л )УМ, 620 М ЬП)МА, 916 о О-обозначения, 2! 3 Р РцпГу, 567 К г-значение, 143, 453 К)8С, 52, 620 Я ЯМ)3, 53 8ЬК(1)-анализатор, 324 8ЬК11)-таблица, 324 Я.К-анализ, 322 8РМЮ, 9!9 ь 1-значение, 143, 453 1.ех, 191, 37! Прогностический оператор, 197, 226 Программа„ 192 Разрешение конфликтов, 196 ЬЬ1)г), 283 ЬК10)-автомат, 312, 3! 6 ЬК-анализатор, 319 1.К-грамматика, 301 У тасс, 311, 363 Восстановление после ошибки, 372 Неоднозначная грамматика, 368 Семантические действия, 367 А Абстрактное синтаксическое дерево, 110 Адрес возврата, 533 Активация, 529 Запись, 532 Активный префикс, 327 Алгоритм 1.К-анализа, 320 Анализ активных переменных, 734 Анализ на основе областей, 812 Ахо-Корасик, 187 Выведение типа для полиморфиых функций, 485 Вычисление границ для заданного порядка переменных, 943 Генерации кода с использованием динамического программирования,697 Генерация кода для помеченного дерева выражения, 690, 692 Генерация кода, последовательно выполняющего части разбиения программы, 992 Глубинное остовное дерево и упорядочение графа в глубину, 792 Достигающие определения, 730 1168 Предметный указатель Доступные выражения, 739 Евклида, 968 Инкрементное вычисление программы Оа1а!о8, 1091 Исключение Фурье — Моцкина, 942 Итеративное решение обобщенной задачи потока данных, 753 Кнута-Морриса-Пратга, 187 Кока — Янгера-Касами, 252, 300 Копирующий сборщик Чени, 587 Левая факторизация грамматики, 278 Мак-Нотона-Ямалы-Томпсона, 213 Максимизация степени параллельности с использованием О(1) синхронизаций, 10!2 Метод номера значения построения узла ориентированного ациклического графа, 448 Минимизация количества состояний ДКА, 238 Моделирование ДКА, 203 Моделирование НКА, 210 Объединение двух ВОЮ, 1122 Определение информации о живучести и последующем использовании для каждой инструкции базового блока, 643 Определение предпросмотров, 346 Оптимизация локальности данных в однопроцессорной системе, !047 Оптимизация параллелизма и локальности данных в многопроцессорной системе, 1049 Отложенное перемешение кода, 775, 784 Планирование на основе областей, 871 Планирование списка базового блока, 86! Поезда, 599 Поиск всех степеней максимально крупномодульного параллелизма в программе, 1035 Поиск доминаторов, 789 Поиск множества допустимых максимально независимых отображений временных разбиений для внешнего последовательного цикла, 1027 Поиск не требующего синхронизации аффинного разбиения программы с наивысшим рангом, 988 Построение восходящего порядка областей приводимого графа потока, 808 Построение ДКА из регулярного выражения, 235 Построение естественного цикла обратной дуги, 797 Построение множеств ЕК(1)-пунктов, 333 Построение подмножества ДКА из НКА, 206 Построение таблиц канонического 1.К-анализа, 336 Построение таблицы Б).й-анализа, 323 Построение таблицы предиктивного синтаксического анализа, 290 Предиктивный синтаксический анализ, управляемый таблицей, 293 Преобразования регулярного выражения в НКА, 213 Программная конвейеризация, 895 Программная конвейеризация ациклического графа зависимости данных, 889 Программная конвейеризация с модульным расширением переменной, 90! Простое вычисление программ Оа1а!о8, 1089 Простое построение 1.АЕК-таблицы, 341 Разбиение трехадресных команд на базовые блоки, 641 Решение задачи целочисленного линейного программирования методом ветвей и границ, 974 Предметный указатель 1169 Сборка мусора "пометить и подмести", 578 Сборщик мусора "пометить и подмести" Бейкера, 582 Сборщик мусора "пометить и сжать", 585 Сжатие массива, 1043 Символический анализ на основе областей, 829 Унификация пар узлов в графе типа, 488 Устранение левой рекурсии, 277 Эрли, 252 Эффективное вычисление ядер наборов множеств БАЕК(1)-пунктов, 347 Алфавит, 165 Входной, 200 Альтернатива, 260 Анализ, 32 Активных переменных, 733 Лексический, 33 Предиктивный, 278 Семантический, 37 Символический, 8!9 Синтаксический, 35, 252 Указателей, 1095 Анализ потоков данных, 719, 744 Анализатор Предиктивный, 106 Архитектура процессора, 842 Ассемблер, 32 Ассоциативность, 85, 171, 353 Атрибут, 91, !59, 383 Наследуемый, 93, 385 Синтезируемый, 93, 384 Аффинное выражение, 820 Б Базовый блок, 640, 641 Лидер, 64! Барьерная синхронизация, 919, 1006 Блочная структура, 62 Буферизация ввода, !62 Бзкуса-Наура форма, 76, 251 в Векторная машина, 921 Виртуальный метод, 1062, 1076 Висящий указатель, 566 Вложение циклов, 924 Волновое распараллеливание, !031 Восстановление после ошибки, 255, 358, 372 Глобальная коррекция, 257 На уровне фразы, 297, 359 Продукции ошибок, 257 Режим паники, 256, 295, 359 Уровень фразы, 257 Встраивание, 50, 1061 Выведение типа, 478 Вывод, 261 Выполнение с опережением, 852 Выравнивание адресов, 463 Выражение типа, 459 Вычет цикла, 972 Вычисление, инвариантное относительно цикла, 714 г Генерация Кода, 39, 6!7, 660 Выбор порядка вычислений, 625 Промежуточного кода, 38, 136 Глобальное планирование, 864 Глубина вложенности, 545 Грамматика, 25! !.А1.8(1), 342 Щ1), 288 Щ)г), 283 Бй, 30! 1,К!1), 337 ЯЩ1), 324 Атрибутная, 386 Контекстно-свободная, 79, 258„ 310 Леворекурсивная, 275 Неоднозначная, 84, 265, 353, 368 Устранение неоднозначности, 273 Грамматический символ, 260 Граф Взаимодействия регистров, 676 Вызовов, 1062 Зависимостей, 391 1170 Предметный указатель Зависимостей программы, 1007 Зависимости данных, 858 Критический путь, 861 Ориентированный ациклический, 445, 648 Переходов, 200 Потока, 640, 644, 720 Глубина, 795 Полный, 802 Представление, 646 Цикл, 646 Раскраска, 676 Сильно связанный компонент, 891 Топологическая сортировка, 393 Дерево Активаций, 53! Глубинное остовное, 790 Доминаторов, 787 Крона, 263 Разбора, 82, 100, 263 Аннотированное, 387 Синтаксическое, 35, 400 Дескриптор Адреса, 661 Регистра, 661 Диаграмма бинарного выбора, 1110, 1115 Упорядоченная, 1118 Диаграмма переходов, 179, 289 Динамическое программирование, 695 Диофантово уравнение, 967 Диспетчер памяти, 555 Дисплей, 552 Доминатор, 787 Достигающее определение, 721, 725 Алгоритм, 730 Доступное выражение, 735 Дублирование констант, 722, 760 Зависимость через данные, 846 Загрузчик, 32 Задача потока данных, 722 Закон Амдаля, 917 Замыкание Клини„167, 168 Позитивное, 168 Запись активации, 532 Заполнение, 526 Зарезервированное слово, 122 и Идемпотентность, 171 Идентификатор, 34, 6! Распознавание, 181 Иерархическое время, 1012 Иерархическое приведение, 903 Иерархия памяти, 51 Имитационное моделирование, 55 Инкапсуляция, 65 Инкрементная трансляция, 470 Интерпретатор, 30 Исключение Фурье-Моцкнна, 942 Использование, 643 Итерация, 168 к Кадр, 532 Канонический набор, 312 Ключевое слово, 121 Распознавание, 181 Код Мертвый, 649, 651 Трехадресный, 38 Коммутативность, !71 Компилятор, 29 Заключительная стадия, 33 Начальная стадия, 33 Структура, 32 Компоновщик, 32 Конвейер команд, 842 Конвейеризация, 1014 Конвейеризация программная, 876 Конечный автомат, 199 Важные состояния НКА, 229 Детерминированный, 200 ДКА с минимальным количеством состояний, 237 Недетерминированный, 199, 200, 268 Преобразование НКА в ДКА, 206 Тупиковое состояние, 240 Тупиковые состояния ДКА, 227 1172 Предметный указатель Сжатие массива, 1041 Удаление бесполезного кода, 713 Удаление общих подвыражений, 7!О Устранение излишних загрузок и сохранений, 668 Устранение недостижимого кода, 669 Устранение частичной избыточности, 768 Частично избыточные выражения, 771 Отложенное перемещение кода, 774 Относительный адрес, 459 Ошибка Лексическая, 255 Логическая, 255 Семантическая, 255 Синтаксическая, 255 и Память, 51, 525 Выделение, 555 Выделение в стеке, 528, 635 Динамическая, 558 Диспетчер, 555 Иерархия, 557 Освобохсление, 555 Статическая, 558 Статическое выделение, 632 Статическое и динамическое распределение, 527 Страница, 559 Утечка, 565 Фрагментация, 561 Параллелизм, 51 На уровне задач, 919 Параметрический полиморфизм, 482 Перегрузка, 144 Передаточная функция, 723, 750 Передача параметров По значению, 68 По имени, 69 По ссылке, 69 Переменная, 61 Глобальная, 543 Индукции, 820 Ссылочная, 819 Перенос, 305 Планирование Глобальное„ 864 Перемещение кода, 874 Списков базовых блоков, 859 Планирование кода, 845 Повторное использование данных, 951 Подпоследовательность, 167 Подстрока, 167 Подсчет ссылок, 567 Полностью переставляемые циклы, 1017, 1030 Полурешетка, 744 Высота, 750 Порождение, 81, 261 Каноническое, 263 Последовательная сверхрелаксация, 1016 Последовательное вычисление, 696 Последовательность Возврата, 535 Вызовов, 535 Постфиксная запись, 91 Поток Данных, 722, 744 Анализ, 719 Управления, 491, 729 Правило последнего вложения, 130 Правоассоциативность, 86 Предвыборка,1053 Предикатная команда, 854 Предиктивный анализ, 104 Предиктивный анализатор, 106 Предложение, 166 Предпросмотр,332 Препроцессор, 31 Префикс, 167 Приведение типа, 37, 144 Примитивное аффинное преобразование, 1000 Приоритет, 353 Приоритет операторов, 86 Проверка Статическая, 443 Типов, 37, 56, 143, 459, 477, 519 Программная конвейеризация, 876, 895 Продукция, 79, 259 Единичная, 299 Предметный указатель И73 Одинарная, 111 Ошибки, 257 Промежуточное представление, 136 Протокол когерентной кэш-памяти, 915 Проход, 41 Процедура Вложенная, 543 Псевдоним, 70, 848 Пункт (.К(0), 311 1.К(1), 33! Путь выполнения, 720 Р Разбиение аффинного пространства, 981 Разбор, 35 Разыменование висящего указателя, 565 Ранг матрицы, 954 Распределение регистров, 40 Распространение констант, 760 Расширение переменной, 900 Модульное, 901 Регистр Глобальное распределение, 672 Граф взаимодействия, 676 Дескриптор, 661 Назначение, 623 Распределение, 623 Регулярное выражение, 168, 268 Эквивалентность, 170 Регулярное множество, !70 Регулярное определение, 171 Рекурсия Левая, 107 Оконечная, 114 Решетка, 748 Диаграмма, 747 Произведения, 749 с Сборка мусора, 50, 528, 569 Алгоритм поезда, 599 Инкрементная, 591 Конкурентная, 605 Копирующая, 587 На основе отслеживания, 574 Отложенный подсчет ссылок, 576 Параллельная, 605 Перемещающая, 583 По поколениям, 597 С подсчетом ссылок, 574 Свертка, 302, 305 Свертывание констан и 652 Связь Доступа, 534, 547, 548 Управления, 534 Семантическая ошибка, 255 Семантический анализ, 37 Семантическое действие, 97, 406 Сентенциальная форма, 262 Сжатие массива, 1041 Сигнатура, 66, 448 Символический анализ, 8!9 Симметричная мультипроцессорность, 914 Синтаксическая оц~ибка, 255 Синтаксически управляемая трансляция, 76 Синтаксически управляемое определение, 92, 96, 384 Синтаксический анализ, 35, 82, 84, 252 Восходящий, 100, 253, 301 Методом рекурсивного спуска, 104, 283 Нисходящий, 100, 101, 253, 281 Перенос1свертка, 301, 304 Предиктивный, 104 Синтаксический анализатор Нерекурсивный предиктивный, 292 Предикгивный, 288 Синтаксическое дерево, 35, 77, 110, 137 Абстрактное, ! 10 Аннотированное, 93 Конкретное, 111 Синтез, 33 Синтез типа, 477 Синхронизирующий барьер, ! 006 Система типов Надежная, 477 Сканирование, 33 Сканируемый символ, 102 Слабые ссылки, 610 Словарь, 448 Слово, 166 1174 Предметный указатель Сокращенные вычисления, 492 Ссылочная переменная, 819 Стартовый символ, 79, 259 Статическая проверка программы, ! 42 Статическое единственное присваивание, 457 Стек, 528 Строка, 166 Вызовов, 1067 Конкатенация, 166 Основа, 302 Подпоследовательность, 167 Подстрока, 167 Префикс, 167 Пустая, 81, 166 Суффикс, 167 Фибоначчи, 189 Структура Дистрибутивная, 752 Монотонная.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
