ОПТИМИЗАЦИЯ БУЛЕВЫХ ВЫРАЖЕНИЙ

Мы можем использовать некоторые свойства булевых выражений для того, чтобы сократить их вычисления. Например, в операторе 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. Поэтому мы хотим вычислять выражения слева направо, прекращая вычисления сразу, как только становится известным окончательный результат. Для предыдущего выражения можно считать эквивалентной следующую запись:

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