Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 22
Текст из файла (страница 22)
В некоторых языках программированияне оговаривается, каким способом должны вычисляться логическиевыражения (например, в Паскале), в некоторых требуется, чтобывычисления производились тем или иным способом (например, в Модуле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>;Code<0>=NodeLable<0>+”:”+Code<1>+Code<3>.RULEBoolExpr ::= BoolExpr 'OR' BoolExpr144SEMANTICSTrueLab<1>=TrueLab<0>; FalseLab<1>=NodeLab<3>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Code<0>=NodeLable<0>+”:”+Code<1>+Code<3>.RULEBoolExpr ::= FSEMANTICSCode<0>=“GOTO FalseLab<0>“.RULEBoolExpr ::= TSEMANTICSCode<0>=“GOTO TrueLab<0>“.Здесь предполагается, что все вершины дерева занумерованы и номервершины дает атрибут NodeLab.
Метки вершин передаются, как этоизображено на рис. 8.20.TrueLabFalseLabFalseLabTrueLabANDFalseLabTrueLabTrueLab TrueLabFalseLabNodeLabelFalseLabORРис. 8.20.FalseLabTrueLabNodeLabelСопоставим каждому атрибутированному дереву в этой атрибутнойграмматике текст (трансляцию), полученный следующим образом врезультате обхода дерева сверху вниз слева направо: при входе в вершинубудем генерировать ее номер, в вершине F будем генерировать текстGOTO значение атрибута FalseLab<0>, в вершине T - GOTO значениеатрибута TrueLab<0>.
Например, для выражения F OR ( F AND T AND T )OR T получим атрибутированное дерево и трансляцию, изображенные нарис. 8.21 и 8.22.:F OR ( F AND T AND T ) OR T145| FalseLab=False1 TrueLab=TrueTrueLab=TrueFalseLab=2ORFalseLab=False2 TrueLab=TrueFTrueLab=TrueFalseLab=3OR4TrueLab=5FalseLab=33|TTrueLab=TrueFalseLab=3ANDF5TrueLab=6FalseLab=3AND6|1:2:4:5:6:T3: GOTOTrueLab=TrueFalseLab=3TGOTO 2GOTO 3GOTO 6GOTOTrueTrueРис. 8.21Рис.
8.22Эту линеаризованную запись можно трактовать как программувычисления логического значения: каждая строка может быть помеченаномером вершины и содержать либо переход на другую строку, либопереход на True или False, что соответствует значению выражения true илиfalse, либо пусто. Будем говорить, что полученная программа вычисляет(или интерпретирует) значение выражения, если в результате еевыполнения (от первой строки) мы придем к строке, содержащей GOTOTrue или GOTO False.Утверждение 1. Для любого логического выражения, состоящего изконстант, программа, полученная в результате обхода дерева этоговыражения, завершается со значением логического выражения в обычнойинтерпретации, т.е.
осуществляется переход на True для значения, равногоtrue, и переход на метку False для значения false.Это утверждение является частным случаем следующего.146Утверждение 2. В результате интерпретации поддерева с некоторымизначениями атрибутов FalseLab и TrueLab в его корне выполняетсякоманда GOTO TrueLab, если значение выражения истинно, и командаGOTO FalseLab, если значение выражения ложно.Доказательство можно провести индукцией по высоте дерева.
Длядеревьев высоты 1, соответствующих правилам BoolExpr ::= F и BoolExpr::= T, утверждение очевидно из правил грамматики. Пусть дерево имеетвысоту n>1. Зависимость атрибутов для дизъюнкции и конъюнкцииприведена на рис. 8.23FalseLab0TrueLab0ANDFalseLab1=FalseLab0TrueLab1=NodeLab2FalseLab2=FalseLab0TrueLab2=TruLab0FalseLab0TrueLab0ORFalseLab1=NodeLab2TrueLab1=TruLab0FalseLab2=FalseLab0TrueLab2=TruLab0Рис.
8.23Если для конъюнкции значение левого поддерева ложно и по индукциивычисление левого поддерева завершается командой GOTO FalseLab1, тои интерпретация всего дерева завершается командой GOTO FalseLab0(=FalseLab1). Если значение левого поддерева истинно, то егоинтерпретация завершается командой GOTO TrueLab1 (=NodeLab2). Еслизначение правого поддерева ложно, то интерпретация всего деревазавершается командой GOTO FalseLab0 (=FalseLab2).
Если же оноистинно, интерпретация всего дерева завершается командой GOTOTrueLab0 (=TrueLab2). Аналогично - для дизъюнкции.Доказательство утверждения 1 следует из того, что меткамивершины дерева логического выражения являются TrueLab=True иFalseLab=False.147Добавим теперь новое правило в предыдущую грамматику:RULEBoolExpr ::= IdentSEMANTICSCode<0>=”if (Val<1>==T)GOTO TrueLab<0>else GOTO FalseLab<0>”;Тогда, например, для предыдущего выражения получим следующуюпрограмму:1:2:4:5:6:3:if (F==T) then GOTO True else GOTO 2ifififif(F==T)(T==T)(T==T)(T==T)GOTOGOTOGOTOGOTO5 else GOTO 36 else GOTO 3True else GOTO 3True else GOTO FalseПри каждом конкретном наборе данных эта программа превращается впрограмму вычисления логического значения.Утверждение 3.
В каждой строке программы, сформированной предыдущейатрибутной схемой, одна из меток совпадает с меткой следующей строки.Действительно, по правилам наследования атрибутов TrueLab иFalseLab, в правилах для дизъюнкции и конъюнкции либо FalseLab, либоTrueLab принимает значение метки следующего поддерева. Кроме того,как значение FalseLab, так и значение TrueLab, передаются в правоеподдерево от предка. Таким образом, самый правый потомок всегда имеетодну из меток TrueLab или FalseLab, равную метке правого братасоответствующего поддерева.
Учитывая порядок генерации команд,получаем утверждение.Дополним теперь атрибутную грамматику следующим образом: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>;148Code<0>=NodeLable<0>+”:”+Code<1>+Code<3>.RULEBoolExpr ::= BoolExpr 'OR' BoolExprSEMANTICSTrueLab<1>=TrueLab<0>; FalseLab<1>=NodeLab<3>;FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;Sign<1>=true; Sign<3>=Sign<0>;Code<0>=NodeLable<0>+”:”+Code<1>+Code<3>.RULEBoolExpr ::= NOT BoolExprSEMANTICSFalseLab<1>=TrueLab<0>; TrueLab<1>=FalseLab<0>;Sign<1>=! Sign<0>;Code<0>=Code<1>.RULEBoolExpr ::= FSEMANTICSCode<0>=”GOTO FalseLab<0>”.RULEBoolExpr ::= TSEMANTICSCode<0>=”GOTO TrueLab<0>”.RULEBoolExpr ::= IdentSEMANTICSCode<0>=”if (Val<1>==T) GOTO TrueLab<0>else GOTO FalseLab<0>”.Правила наследования атрибута Sign приведены на рис.
8.24.false |ORtruefalsetrue |ORtruetrue149false |ANDtrue |ANDfalse falsefalse truetruefalseNOTNOTfalsetrueРис. 8.24Программу желательно сформировать таким образом, чтобы else-меткабыла как раз меткой следующей вершины. Как это можно сделать, следуетиз утверждения 4.Утверждение 4. В каждой терминальной вершине, метка ближайшегоправого для нее поддерева равна значению атрибута FalseLab этойвершины, тогда и только тогда, когда значение атрибута Sign этойвершины равно true, и наоборот, метка ближайшего правого для нееподдерева равна значению атрибута TrueLab этой вершины, тогда и толькотогда, когда значение атрибута Sign равно false.Эти два утверждения позволяют заменить последнее правилоатрибутной грамматики следующим образом:RULEBoolExpr ::= IdentSEMANTICSCode<0>=Sign<0>? ”if (Val<1>==T) GOTO TrueLab<0>”: ”if Val<1>==F) GOTO FalseLab<0>”.В свою очередь, при генерации машинных команд это правило можнозаменить на следующее:RULEBoolExpr ::= IdentSEMANTICS<TST Ident>;Code<0>=Sign<0>? ”BNE TrueLab<0>”: ”BEQ FalseLab<0>”.Если элементом логического выражения является сравнение, тогенерируется команда, соответствующая знаку сравнения (beq для =, bneдля <>, bge для >= и т.д.), если атрибут sign соответствующей вершиныимеет значение true, и отрицание (bne для =, beq для <>, blt для >= и т.д.),если атрибут sign имеет значение false.150Приведем несколько примеров.
Выражение A AND (B OR C)транслируется в последовательность команд рис. 8.25. Выражение(NOT((A==B)OR(!=D)))AND(NOT((E<F)AND(G>H))) транслируется впоследовательность команд рис. 8.26.TSTBEQTSTBNETSTBEQAFalseBTrueCFalseCMPBEQCMPBNECMPBGECMPBGTTrue:False:True:False:. . .Рис. 8.25A,BFalseC,DFalseE,FFalseG,HFalseРис.
8.261518.8. Выделение общих подвыраженийВыделение общих подвыражений проводится на линейном участке иосновывается на двух положениях.1. Поскольку на линейном участке переменной может бытьнесколько присваиваний, то при выделении общих подвыраженийнеобходимо различать вхождения переменных до и после присваивания.Для этого каждая переменная снабжается счетчиком. Вначале номера всехпеременных устанавливаются равными 0. При каждом присваиваниипеременной ее номер увеличивается на 1.2. Выделение общих подвыражений осуществляется при обходедерева выражения снизу вверх слева направо.
При достижении очереднойвершины (пусть операция, примененная в этой вершине, есть бинарная'op'; в случае унарной операции рассуждения те же) просматриваем общиеподвыражения, связанные с op. Если имеется выражение, связанное с op итакое, что его левый операнд есть общее подвыражение с левымоперандом нового выражения, а правый операнд - общее подвыражение справым операндом нового выражения, то объявляем новое выражениеобщим с найденным и в новом выражении запоминаем указатель нанайденное общее выражение. Базисом построения служит переменная:если операндами обоих выражений являются одинаковые переменные содинаковыми счетчиками, то они являются общими подвыражениями.Если выражение не выделено как общее, оно заносится в список операций,связанных с op (рис. 8.27).OPРис.8.27Рассмотрим теперь реализацию алгоритма выделения общихподвыражений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
