В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 25
Текст из файла (страница 25)
В некоторых языках программированияне оговаривается, каким способом должны вычисляться логические выражения (например, в Паскале), в некоторых требуется, чтобы вычисления производились тем или иным способом (например, в Модуле-2требуется, чтобы выражения вычислялись по приведенным формулам),в некоторых языках есть возможность явно задать способ вычисления(Си, Ада). Вычисление логических выражений непосредственно по таблицам истинности аналогично вычислению арифметических выражений, поэтому мы не будем их рассматривать отдельно.
Рассмотрим подробнее способ вычисления с помощью приведенных выше формул (будем называть его “вычислением с условными переходами”). Иногда такой способ рассматривают как оптимизацию вычисления логическихвыражений.Рассмотрим следующую атрибутную грамматику со входным языком логических выражений:RULEExpr ::= BoolExprSEMANTICSFalseLab<1>=False; TrueLab<1>=True;Code<0>=Code<1>.RULEBoolExpr ::= BoolExpr ’AND’ BoolExprSEMANTICSFalseLab<1>=FalseLab<0>; TrueLab<1>=NodeLab<3>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;9.7. ТРАНСЛЯЦИЯ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ159Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= BoolExpr ’OR’ BoolExprSEMANTICSFalseLab<1>=NodeLab<3>; TrueLab<1>=TrueLab<0>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= ’(’ BoolExpr ’)’SEMANTICSFalseLab<2>=FalseLab<0>;TrueLab<2>=TrueLab<0>;Code<0>=NodeLab<0> + ":" + Code<2>.RULEBoolExpr ::= FSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + FalseLab<0>.RULEBoolExpr ::= TSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + TrueLab<0>.Здесь предполагается, что все вершины дерева занумерованы и номер вершины дает атрибут NodeLab.
Метки вершин передаются, как этоизображено на рис. 9.11.7UXH/DE)DOVH/DE)DOVH/DE7UXH/DE$1')DOVH/DE7UXH/DE7UXH/DE)DOVH/DE1RGH/DE7UXH/DE)DOVH/DE25)DOVH/DE7UXH/DE1RGH/DEРис. 9.11:Таким образом, каждому атрибутированному дереву в этой атрибутной грамматике сопоставляется код, полученный в результате обходаГЛАВА 9.
ГЕНЕРАЦИЯ КОДА160дерева сверху-вниз слева-направо следующим образом. При входе в вершину BoolExpr генерируется ее номер, в вершине F генерируется текстGOTO значение атрибута FalseLab<0>, в вершине T – GOTO значение атрибута TrueLab<0>. Например, для выраженияF OR ( F AND T AND T ) OR Tполучим атрибутированное дерево, изображенное на рис. 9.12, и код([SU7UXH/DE 7UXH%RRO([SU )DOVH/DE )DOVH257UXH/DE 7UXH)DOVH/DE %RRO([SU1RGH/DE )1RGH/DE 7UXH/DE 7UXH%RRO([SU )DOVH/DE )DOVH257UXH/DE 7UXH%RRO([SU )DOVH/DE 1RGH/DE 7UXH/DE 7UXH%RRO([SU )DOVH/DE 7UXH/DE )DOVH/DE 1RGH/DE %RRO([SU)$1'%RRO([SU1RGH/DE 1RGH/DE 7UXH/DE 7UXH%RRO([SU )DOVH/DE )DOVH1RGH/DE 77UXH/DE 7UXH%RRO([SU )DOVH/DE $1'7UXH/DE )DOVH/DE 1RGH/DE 71RGH/DE 7UXH/DE 7UXH%RRO([SU )DOVH/DE 1RGH/DE 7Рис.
9.12:1:7: GOTO 22:8:4:9: GOTO 35:10: GOTO 66:GOTO True3:GOTO TrueTrue: ...False: ...Эту линеаризованную запись можно трактовать как программу вычисления логического значения: каждая строка может быть помечена9.7. ТРАНСЛЯЦИЯ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ161номером вершины и содержать либо переход на другую строку, либопереход на True или False, что соответствует значению выражения trueили false. Будем говорить, что полученная программа вычисляет (илиинтерпретирует) значение выражения, если в результате ее выполнения (от первой строки) мы придем к строке, содержащей GOTO True илиGOTO False.Утверждение 9.1.
В результате интерпретации поддерева с некоторыми значениями атрибутов FalseLab и TrueLab в его корне выполняется команда GOTO TrueLab, если значение выражения истинно, и команда GOTO FalseLab, если значение выражения ложно.Доказательство. Применим индукцию по высоте дерева. Для деревьев высоты 1, соответствующих правиламBoolExpr ::= F и BoolExpr ::= T,справедливость утверждения следует из соответствующих атрибутныхправил.
Пусть дерево имеет высоту n > 1. Зависимость атрибутов длядизъюнкции и конъюнкции приведена на рис. 9.13.)DOVH/DE !7UXH/DE !)DOVH/DE ! )DOVH/DE !7UXH/DE ! 1RGH/DE !$1')DOVH/DE ! )DOVH/DE !7UXH/DE ! 7UXH/DE !)DOVH/DE !7UXH/DE !)DOVH/DE ! 1RGH/DE !7UXH/DE ! 7UXH/DE !25)DOVH/DE ! )DOVH/DE !7UXH/DE ! 7UXH/DE !Рис. 9.13:Если для конъюнкции значение левого поддерева ложно и по индукции вычисление левого поддерева завершается командой GOTO FalseLab<1>,то получаем, что вычисление всего дерева завершается командой перехода GOTO FalseLab<0> (= FalseLab<1>). Если же значение левого поддереваистинно, то его вычисление завершается командой перехода GOTO TrueLab<1>(= NodeLab<3>).
Если значение правого поддерева ложно, то вычисление162ГЛАВА 9. ГЕНЕРАЦИЯ КОДАвсего дерева завершается командой GOTO FalseLab<0> (= FalseLab<3>). Еслиже оно истинно, вычисление всего дерева завершается командой перехода GOTO TrueLab<0> (= TrueLab<3>). Аналогично – для дизъюнкции.Утверждение 9.2. Для любого логического выражения, состоящего изконстант, программа, полученная в результате обхода дерева этого выражения, завершается со значением логического выражения вобычной интерпретации, т.е. осуществляется переход на True длязначения, равного true, и переход на метку False для значения f alse.Доказательство.
Это утверждение является частным случаем предыдущего. Его справедливость следует из того, что метки корня дерева равны соответственно TrueLab = True и FalseLab = False.Добавим теперь новое правило в предыдущую грамматику:RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" + "if (" + Val<1> + "==T) GOTO" +TrueLab<0> + "else GOTO" + FalseLab<0>.Тогда, например, для выражения A OR ( B AND C AND D ) OR E получимследующую программу:1:7: if (A==T) GOTO True else GOTO 22:8:4:9: if (B==T) GOTO 5 else GOTO 35:10: if (C==T) GOTO 6 else GOTO 36:if (D==T) GOTO True else GOTO 33:if (E==T) GOTO True else GOTO FalseTrue: ...False: ...При каждом конкретном наборе данных эта программа превращается в программу вычисления логического значения.Утверждение 9.3.
В каждой строке программы, сформированной предыдущей атрибутной схемой, одна из меток внутри условного оператора совпадает с меткой следующей строки.Доказательство. Действительно, по правилам наследования атрибутов TrueLab и FalseLab, в правилах для дизъюнкции и конъюнкции либоатрибут FalseLab, либо атрибут TrueLab принимает значение метки следующего поддерева. Кроме того, как значение FalseLab, так и значениеTrueLab, передаются в правое поддерево от предка.
Таким образом, самый правый потомок всегда имеет одну из меток TrueLab или FalseLab,равную метке правого брата соответствующего поддерева. Учитывая порядок генерации команд, получаем справедливость утверждения.9.7. ТРАНСЛЯЦИЯ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙДополним теперь атрибутную грамматику следующим образом:RULEExpr ::= BoolExprSEMANTICSFalseLab<1>=False; TrueLab<1>=True;Sign<1>=false;Code<0>=Code<1>.RULEBoolExpr ::= BoolExpr ’AND’ BoolExprSEMANTICSFalseLab<1>=FalseLab<0>; TrueLab<1>=NodeLab<3>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Sign<1>=false; Sign<3>=Sign<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= BoolExpr ’OR’ BoolExprSEMANTICSFalseLab<1>=NodeLab<3>; TrueLab<1>=TrueLab<0>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Sign<1>=true; Sign<3>=Sign<0>;Code<0>=NodeLab<0> + ":" + Code<1> + Code<3>.RULEBoolExpr ::= ’NOT’ BoolExprSEMANTICSFalseLab<2>=TrueLab<0>; TrueLab<2>=FalseLab<0>;Sign<2>=! Sign<0>;Code<0>=Code<2>.RULEBoolExpr ::= ’(’ BoolExpr ’)’SEMANTICSFalseLab<2>=FalseLab<0>;TrueLab<2>=TrueLab<0>;Sign<2>=Sign<0>;Code<0>=NodeLab<0> + ":" + Code<2>.RULEBoolExpr ::= FSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + FalseLab<0>.RULE163ГЛАВА 9.
ГЕНЕРАЦИЯ КОДА164BoolExpr ::= TSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + TrueLab<0>.RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" + "if (" + Val<1> + "==T) GOTO"+ TrueLab<0> + "else GOTO" + FalseLab<0>.Правила наследования атрибута Sign приведены на рис. 9.14.6LJQ6LJQ$1'6LJQIDOVH6LJQ !127256LJQ6LJQWUXH6LJQ6LJQ ! QRW6LJQ !Рис. 9.14:Программу желательно сформировать таким образом, чтобы else-меткабыла как раз меткой следующей вершины. Как это можно сделать, следует из следующего утверждения.Утверждение 9.4. В каждой терминальной вершине, метка ближайшего правого для нее поддерева равна значению атрибута FalseLabэтой вершины, тогда и только тогда, когда значение атрибута Signэтой вершины равно true, и наоборот, метка ближайшего правогодля нее поддерева равна значению атрибута TrueLab этой вершины,тогда и только тогда, когда значение атрибута Sign равно f alse.Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
