АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ELSE FALSE

Читайте также:
  1. a) Mark the sentences T (true), F (false) or DS (doesn’t say).
  2. Read the following facts about Thomas and Summer. Are they true of false?

Переопределим синтаксис и семантику логических выражений следующим образом:

S ® E

E ® TôT OR E

T ® FôF AND T

F ® iô(E)ôNOT F

Где: C OR D определяется, как IF C THEN TRUE ELSE D;

C AND D определяется, как IF C THEN D ELSE FALSE;

NOT C определяется, как IF C THEN FALSE ELSE TRUE;

При генерации тетрад используются идентификаторы, константы 0 (FALSE) и 1 (TRUE), тетрада (:=, K,, X) – что соответствует X:= K и тетрада (B, Y, i, j). Последняя тетрада имеет следующий смысл: если идентификатор Y имеет значение TRUE, то осуществляется переход на i -ю тетраду, в противном случае на j -ю.

На рис. 7.4 приведено несколько примеров, при разборе которых надо учесть, что результат выражения всегда заносится в X. В первой тетраде в X заносится 1, то есть значение выражения вначале предполагается равным TRUE. Если обнаруживается, что выражение и в самом деле имеет значение TRUE, то выполняется переход с пропуском оставшихся тетрад, в том числе и последней. Если же значение выражения FALSE, то происходит переход на последнюю тетраду, в которой в X заносится 0.

 

Идентификаторы в тетрадах с рис. 7.4 располагаются в том же порядке, что и в исходном выражении. И наконец, для оператора NOT тетрады не генерируются. Если A представляется, как (B, A, i, j), то NOT A, как (B, A, j, i), то есть меняются местами адреса переходов по TRUE и FALSE.

Главная проблема здесь, конечно же, в правильном формировании адресов переходов. В монографии Д. Гриса [5] показаны подходы к решению этой проблемы с помощью организации списков переходов, как при реализации семантических программ в восходящем разборе, аналогичном алгоритму Вирта-Вебера, так и в методе рекурсивного спуска.

ВЫНЕСЕНИЕ ИНВАРИАНТНЫХ ВЫЧИСЛЕНИЙ ЗА ЦИКЛ

 

Если вычисления внутри цикла зависят от переменной, которая в этом цикле не изменяется, то это вычисление можно вынести из цикла Это приведет к реорганизации части матрицы тетрад. При этом необходимо решить три задачи:

 

· Распознавание инвариантных вычислений – это наиболее сложная из них. Например, требуется определить, что можно вынести из цикла в следующей программе:

 

FOR i:=1 TO 10 DO BEGIN

¼¼¼

¼¼¼

FOR j:=1 TO 10 DO BEGIN

LA: A:=10;

LB: B:= Y[i +2];

LC: C:= C+10

END;

END;

 

Оператор с меткой LA приводит всегда к одному и тому же результату и поэтому может быть вынесен за цикл. В операторе LB индексное выражение i + 2 также не меняется при выполнении внутреннего цикла и может быть без ущерба вынесено из него. Можно также проверить, изменяется ли во внутреннем цикле значение Y и B и если они не меняется, то за внутренний цикл можно вынести весь оператор с меткой LB. Оператор LC включает в себя переменную C, значение которой меняется во внутреннем цикле, и, следовательно, этот оператор из цикла выносить нельзя. Заметим, что, если перед LA имеются операторы (внутри цикла), которые ссылаются на A или B, то в этом случае ничего кроме вычисления индексного выражения мы из цикла вынести не сможем.

 

· Определение места, куда выносить инвариантное вычисление. В общем случае такое вычисление необходимо помещать в ту часть программы, которая непосредственно предшествует циклу. Для этого необходимо, просматривая матрицу тетрад, найти точку начала цикла. Поэтому семантическая фаза должна специальным образом отмечать элементы матрицы, соответствующие началу каждого цикла и в каждом таком элементе должна быть обратная ссылка, с помощью которой можно оптимизировать процесс выхода во внешний цикл.

 

· Вынесение инвариантных вычислений. Используя подход, аналогичный методу исключения общих подвыражений, можно исключить инвариантное вычисление из исходной позиции в матрице и поместить его в соответствующие места.

Для циклов можно предложить и другие методы оптимизации. Иногда два цикла можно объединить в один, уменьшив таким образом число команд проверки и приращения значения переменной цикла. Например, следующие операторы:

 

FOR i:=1 TO 100 DO A[ i ]:=0

FOR j:=1 TO 100 DO B[ j ]:=3*C[ j ]

 

можно объединить в один цикл:

 

FOR k:=1 TO 100 DO BEGIN A[ k ]:=0; B[ k ]:=3*C[ k ] END;

 

В некоторых случаях один цикл можно разбить на два, из которых будет выполняться только один. Например, цикл

 

FOR i:=1 TO 100 DO

IF X > Y THEN A[ i ]:= B[ i ] + X

ELSE A[ i ]:= B[ i ] - Y;

 

можно превратить в

 

IF X > Y THEN

FOR i:=1 TO 100 DO A[ i ]:= B[ i ] + X

ELSE

FOR i:=1 TO 100 DO A[ i ]:= B[ i ] - X;

 

В преобразованной программе условный оператор выполняется лишь один раз, в то время как в исходной он бы исполнялся 100 раз.

Внутри циклов целесообразно по возможности уменьшать силу операций. Например цикл

 

FOR i:=1 TO 100 DO Q[ i ]:=i * 5;

 

можно заменить на

 

J:=5; FOR i:=1 TO 100 DO BEGIN Q[ i ]:= J; J:= J + 5 END;

 

Умножение i * 5 в исходном цикле заменено более быстрым сложением: J + 5.

 

Трудно найти компилятор, в котором были бы реализованы все перечисленные методы оптимизации. Да, скорее всего, это и не нужно, - такой компилятор работал бы чрезвычайно медленно. Мы здесь лишь коснулись возможных методов оптимизации, не давая готовых рецептов реализации. От вашего учебного компилятора не потребуется оптимизировать все и вся. Этот материал дан в первую очередь для того, чтобы вы сами разрабатывали более эффективные программы, не смотря на сверхпроизводительность вашего компьютера. Эффективное программирование – это немаловажный фактор, по которому судят о квалификации программиста.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)