Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 62
Текст из файла (страница 62)
Если А — массив, то рассматриваем оперэтор присваивании А (1) - У так, как если бы А была скалярной переменной, которой было присвоено значение некого. рой функции от 1, У и предыдущего значевия. Другими словами, можно написать А ВА)У, где й — операция, символизирующая присваиаание массвву. Аналогично такой оператор, как .1 =А(1), можно выразить в виде У -фА(. Сделаем, кроме того, еще несколько предположений, в результате чего наши построения потеряют некоторую общность, Например, будем пренебрегать операторами проверки, константами, операторами присваивании вида А В. Однако снятие этих ограни чений приведет к ацалогичиой теории, и ыы делаем зги предположения прежде всего для удобства †что привести пример теории такого типа. Наши основные предположения: (1) Важным фактором, касающимся блока, япляется набор функций входных переменных (переменных, определенных вне блока), эычвсляемых внутри блока.
Сколько раз вычисляется конкретная функция, иесущсстпенно. Такой подход основан на точ, что различные блоки программы передают друг пруту аизчсния переменных а что нет необходимости передавать двв копии одного и того же значения нз одного блока в другой. (2) Ичена переыенных, тчастэующих в вычислениях, несущественны. Это предположение неудовлетворительно, если блок составляет чавгь цикла н функция вьгчисляечся повторно. Например, если вычисляется 1 1 4- 1, то педоп>стима заменя гь зто вычисление на У 1-~- 1, а затем повторять блок, ожидая, что результаты бчдуг такими же. Тем ие менее мы принимаем зто предположение, посиольку оно вспет к некоторой сиьчьчечрии решения и часто оказывается сираэедливым.
В упражнениях предлагается сделать молификации, необхолимые для того, чтобы допустить, :то некоторым выходным значениям даны фиксированные имена. (2) 3(ы не включаем операторы вида Х У. Если такой оператор встречается, то при условии, чю прешюложение (2) выло:шено, можно вместо Х подставить 1', исключив всюлу Х. И виояь зто предположение вносит сизчметрнчо в ыодель, и читателю предлгггьечся модифицировать теорию так, чтобы такие операторы можно было включать.
33! гл и оптимизлпия кодл лл ь оптиллизлпия липеяиога тчлсткл 11.1.2. Преобразования бпанан Заметим, чта если даны даа блока .Я, и Я„то можно установить, эквивалентны лн опи, вычислив их значения а(Ял) и а (Мл) и выяснив, выполняется лн раненство л (Зг) =и (3),). Однако можно указать бесконечное число блоков, эквивалентных любому данному. Например, если М вЂ .(Р, (, О) — блок, Х вЂ переменн, на которую пет ссылки в аг, А †входн перемсннаа, а Π†операпия, то к Р можно любое число раз присоедивять оператор Х ОА ...
А, ие меняя значения Ж. Если выбрать подходящую опенку, то не все эквивалентные блоки будут одинаково эффективны. При данном блоке Я существуют различные преобразования, применимые для отобра. жсния его в зкпивалелппый и, ватна;кна, более желательный блок йй' Пусть Т вЂ множест всех преобразований, сохраняюгпих эквнналентность блоков. Тды покажем, чта любое преобразование из Г можно осуществить с помощью конечной послеловательностн четырех простейшвх преобразований блоков. Зателл оиишелг последовательности преобразований, которые приводят к блоку, оптимальному относительно некоторой разумной опенки. Определение. Пусть Я =- (Р, (, О) †бл, Р = 5,; 5,;, ..; 5„. Для единообразия обозначений примем, гто все элементы входного множества 1 приписаны к некоторому нулевому оператору 5, а все элементы выходного множества в к некоторому (и†;, 1)-у оператору 5„, Переменная А называется активной после момента времени (, если (1) ей присвоено значение некоторым оператором 5г, (2) ей не присвоены значения операторамн 5ы „ 5г, „ ..., 5, (2) на нее ссылается оператор 5гло (4) О < г < С < ! < л.
Если числа 1, о катаром идет речь выше, имеет максимально возможное значение, то пОследовательность опсраторав 5, 5„„..., 5,, называют областью действия оператора 52 и обла. стыа действия этого присваипашзя перемеввой А. Если А — выходная переменная и после 52 ей не присваивается значение, то 1 = и ф 1, и говорят, что 0 лежит в области действия оператора 52 (зто следует из принятого выше соглапюння; здесь мы лилин подчеркиваем это). Если блок содержит такой оператор 5, что переменная, которой присваивается значение в 5, не является активной после этого оператора, то область действия оператора 5 пуста, и говорят, что 5 †бесполезн оператор.
Другими словами, 5— 332 бесполезный оператор, если ан присваивает значение переменной, которая ие является выходной и на вторую нет ссылки в последующих операторах. Пример 1!.2. Рассмотрим блок, в катаром а, й и у — списки из нуля или более операторов: а А В-(-С 0 АлЕ Если перемешюй А яе присванвается значение в последовательности операторов й и на иее пет ссылки из у, то область действия оператора А В ОС включает полностью йл н опе. ратар 0 А «Е. Если в у иет операторов, ссылающглхся на О, и 0 не является выходной переменной, то оператор 0 — А » Е бесполезен.
П Определим теперь четыре простейших преобразования бло. ков, сохраняющие эквивалевпгость. Пусть Я =(Р, Д 0) — блок и Р =-5,;5,;...;5„. Как и вьппе, прсдположилг, что всем вход. ным переменным присванваются зпачевиг в операторе 5, и все выходные переменные входят в оператор 5„,, Преобразования определим в тернинах их воздействия на данный блок .В.
Первое из преобразований интуитивно желательно, а именно нз блока удаляются все те входные переменныс или операторы, которые не оказывают влияния па выходные переменные. Тб Удагеилм бесполезных аригааизаний Если оператор 5о 0< 3 ..л, присваивает значение перезгенной А н она не активна после момента (, то (1) при г ) О можно удалить 5, из Р, (2) при л =0 ма кна удалить А яз /. Пример 1\.3.
Пусть 21= (Р, П О), где ( — -- (А, В, С), 0 = (Р, С) и Р состоит из Р А-) 'А С Р С Р А-';В С АлВ Второй оператор бесполезен, так как его область действия пуста. Таким образом, адно применение преобразования Т, ГЛ. 11 ОПТИМИЗАПИЯ КОЛЛ 11.1 ОПТИАН1ЗЛПИЯ ЛИНЕИНОГО УЧАСТКА отображает З в З, =(Ро /, У), где Р, состоит из Р А'А Р А В 6 ААВ Теперь в З, бесполезны входная переменная С в первый опера. тор. Поэтому Т, можно применвть дважды и получить З, = .— — (Р„(А, В), У), где Р, состоит из Р А — ,'В 6 ААВ Отметим, что З, получается независимо от того, удаляется сначала переменная С или первый оператор нз Р,. Д Для того чгобы можно было систематически удалять вз блока З =(Р, 1, У) все бесполезные операторы, надо определить множество полезных переменных (тех, которые явна или неявно нспользуютсн в вычислении выхода) после каждого оператора блока, вачиная с последнего оператора в Р и поднимаясь затем вверх.
Ясно, что У„= У вЂ множест переменных, полезных после последнего оператора 5„. Предположим, что оператором 51 явлиется А ОВ, ... В, и У, — множес~во переменных, полезных после 5О (1) Если А Е Уг, то 51 †полезн оператор, так как пере. менная А используется для вычисления выходной переменной. Тогда множество Уг 1 полезных переменных после 51, находится заменой А в У, на переменные В„ ..., В, (т. е. У,, = = (У; — (А)) (/(Вчз " В.)). (2) Если А 1)(/1, то оператор 5, бесполезен, и его можно уда.тить.
В этом случае У,, =Уо (3) После вычисления У, можно удалить из / все входные переменные, которых нет в 1/,. Второе преобразование блоков сливает Общие выражения. Тч: Исклго гение иабмзчочиих о мислсний Предположим теперь, что З вЂ”.— (Р, /„У) — блок, где Р имеет вид а А-ОС,... С„ В ОС,...С, у причем нн одна из переменных Со ..., С, не есть А н ни одной нз ннх не присваивается значение ни в какам Операторе в )1. 334 Преобразование Т, отображает З в З'= (Р', /, У'), где Р' есть о 0 ОС,...С, у и (1) Р' — зто список Р, в котором асе ссылки на переменную А в области действия данкого изображения этой переменной заменены ссылками на О, (2) 1' †-это список у, в котором все ссылки на А и В в областях лействня данных изображений А и В заменены ссылками на О. Если область действия переменной А или В распространяется на 5„„, то У' — зто множество У, в котором А нли В заменена на 0.
В противном случае У' = У. 0 может быть:побым нменсч, пе меняющим значения блока. Подходит любой символ, на который нет ссылки в Р, кроме того, могут использоваться и некоторые символы, на которые есть ссылки в Р. Пример ! 1.4. Пусть З вЂ”.— (Р, (А, В), (Р, 6)), где Р состоит вз 5 — А+В Р Ач5 /1  — 'В Т А45 6 Ть/( Второй и четвертый операторы дают избыточныс вычисления, так что к З чожпа применить преобразоващчс Т„в результате чего получится З' =(Р', (А, В), (0, 6)), где Р' состоит из 5 А)В 0 АА5 )(+ — В -1-В 6 Уь/( Выхолным множествам становится (О, 6) 0 чожет быть любыи новым сичволом нлн одной чы переменных Р, А, 5 али Т. Легко проверить, чта сели в качестве 0 взять В, /т нлн 6, то изменится значение программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
