7.2. Вычисления во время компиляции

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

AB

компилятор может выполнить умножение и деление и заменить все выражение в правой части на 14B. Это позволит исключить две тетрады, уменьшая тем самым количество кодов объектной программы.

При этом, простой алгоритм оптимизации будет сводиться к поиску в матрице операций, у которых оба операнда являются литералами. Когда такая операция найдена, она выполняется и порождается новая константа. Тетрада с найденной операцией исключается и все ссылки на ее результат заменяются ссылками на новую константу. Затем просмотр матрицы тетрад продолжается в поисках новых возможных вычислений. Приведенный алгоритм иллюстрируется преобразованиями матрицы на рис. 7.2.

7.3. Оптимизация булевых выражений

Мы можем использовать некоторые свойства булевых выражений для того, чтобы сократить их вычисления. Например, в операторе IF a OR b OR c THEN , где a, b, c – булевы выражения, прежде чем генерировать код, который каждый раз будет проверять все эти выражения, мы можем генерировать такие команды, при выполнении которых в случае, если a истинно, выражение для b и c вычисляться не будут, и аналогично для выражения b.

Традиционная грамматика логических выражений имеет вид:

S  E

E  TE OR T

T  FT AND F

F  i(E)NOT F

Здесь и далее все идентификаторы i – это переменные типа BOOLEAN, которые принимают значения TRUE (истина) или FALSE (ложь). Для них определены три операции: OR, AND и NOT, смысл которых традиционен (см. рис. 7.3).

Из синтаксиса видно, что AND имеет более высокий приоритет, чем or, а у not самый высокий приоритет из этих трех операций. Заметим, что NOT NOT A эквивалентно A. Обычный способ вычисления таких выражений тот же, что и для арифметических, то есть операции выполняются слева направо с учетом их приоритетов и скобок. Польская запись для A AND (B OR NOT C) будет следующей: A B C NOT OR AND. Таким образом, можно было бы легко написать семантические программы для перевода логических выражений в ПОЛИЗ или тетрады, по аналогии с семантикой для арифметических выражений (см. разделы 6.2, 6.3). Однако существует более эффективный способ.

Рассмотрим выражение A AND (B OR NOT C). Если переменная A имеет значение FALSE, то нет необходимости вычислять остальную часть выражения, так как результат всегда будет FALSE. Аналогично если A и B имеют значение TRUE, то не нужно вычислять NOT C. Поэтому мы хотим вычислять выражения слева направо, прекращая вычисления сразу, как только становится известным окончательный результат. Для предыдущего выражения можно считать эквивалентной следующую запись:

IF A THEN

IF B THEN TRUE ELSE NOT C

ELSE 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] показаны подходы к решению этой проблемы с помощью организации списков переходов, как при реализации семантических программ в восходящем разборе, аналогичном алгоритму Вирта-Вебера, так и в методе рекурсивного спуска.