В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 34
Текст из файла (страница 34)
Метки вершин передаются, как это изображенона рис. 9.10.Рис. 9.109.7. Трансляция логических выражений185Таким образом, каждому атрибутированному дереву в этой атрибутной грамматике сопоставляется код, полученный в результате обхода дерева сверху-вниз слева-направо следующим образом. При входе в вершинуBoolExpr генерируется ее номер, в вершине F генерируется текст GOTOзначение атрибута FalseLab<0>, в вершине T — GOTO значение атрибутаTrueLab<0>. Например, для выраженияF OR ( F AND T AND T ) OR Tполучим атрибутированное дерево, изображенное на рис. 9.11, и кодРис.
9.111:7:GOTO2:8:4:9: GOTO5:10:GOTO6:GOTO3:GOTOTrue: ...False: ...236TrueTrueЭту линеаризованную запись можно трактовать как программу вычисления логического значения: каждая строка может быть помечена номеромвершины и содержать либо переход на другую строку, либо переход на Trueили False, что соответствует значению выражения true или false. Будем186Глава 9. Генерация кодаговорить, что полученная программа вычисляет (или интерпретирует)значение выражения, если в результате ее выполнения (от первой строки)мы придем к строке, содержащей GOTO True или GOTO False.Утверждение 9.1. В результате интерпретации поддерева с некоторыми значениями атрибутов FalseLab и TrueLab в его корне выполняетсякоманда GOTO TrueLab, если значение выражения истинно, или командаGOTO FalseLab, если значение выражения ложно.Д о к а з а т е л ь с т в о .
Применим индукцию по высоте дерева. Для деревьев высоты 1, соответствующих правиламBoolExpr ::= F, BoolExpr ::= T,справедливость утверждения следует из соответствующих атрибутных правил. Пусть дерево имеет высоту n > 1. Зависимость атрибутов для дизъюнкции и конъюнкции приведена на рис. 9.12.Рис. 9.12Если для конъюнкции значение левого поддерева ложно и по индукции вычисление левого поддерева завершается командой GOTO FalseLab<1>,то получаем, что вычисление всего дерева завершается командой переходаGOTO FalseLab<0> (= FalseLab<1>).
Если же значение левого поддерева истинно, то его вычисление завершается командой перехода GOTO TrueLab<1>(= NodeLab<3>). Если значение правого поддерева ложно, то вычисление всего дерева завершается командой GOTO FalseLab<0> (= FalseLab<3>). Еслиже оно истинно, вычисление всего дерева завершается командой переходаGOTO TrueLab<0> (= TrueLab<3>).
Аналогично — для дизъюнкции.Утверждение 9.2. Для любого логического выражения, состоящегоиз констант, программа, полученная в результате обхода дерева этого9.7. Трансляция логических выражений187выражения, завершается со значением логического выражения в обычнойинтерпретации, т.
е. осуществляется переход на True для значения, равного true, и переход на метку False для значения false.Д о к а з а т е л ь с т в о . Это утверждение является частным случаемпредыдущего. Его справедливость следует из того, что метки корня дереваравны соответственно TrueLab = True и FalseLab = False.Добавим теперь новое правило в предыдущую грамматику:RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" + "if (" + Val<1> + ")GOTO"+ TrueLab<0> + "else GOTO" + FalseLab<0>.Тогда, например, для выражения A OR (B AND C AND D) OR E получимследующую программу:1:7:if (A) GOTO True else GOTO 22:8:4:9: if (B) GOTO 5 else GOTO 35:10:if (C) GOTO 6 else GOTO 36:if (D) GOTO True else GOTO 33:if (E) GOTO True else GOTO FalseTrue: ...False: ...При каждом конкретном наборе данных эта программа превращаетсяв программу вычисления логического значения.Утверждение 9.3. В каждой строке программы, сформированнойпредыдущей атрибутной схемой, одна из меток внутри условногооператора совпадает с меткой следующей строки.Д о к а з а т е л ь с т в о .
Действительно, по правилам наследования атрибутов TrueLab и FalseLab, в правилах для дизъюнкции и конъюнкциилибо атрибут FalseLab, либо атрибут TrueLab принимает значение меткиследующего поддерева. Кроме того, как значение FalseLab, так и значениеTrueLab, передаются в правое поддерево от предка. Таким образом, самыйправый потомок всегда имеет одну из меток TrueLab или FalseLab, равнуюметке правого брата соответствующего поддерева. Учитывая порядок генерации команд, получаем справедливость утверждения.Дополним теперь атрибутную грамматику следующим образом:RULEExpr ::= BoolExprSEMANTICSFalseLab<1>=False; TrueLab<1>=True;Sign<1>=false;188Глава 9. Генерация кода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 ::= FSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + FalseLab<0>.RULEBoolExpr ::= TSEMANTICSCode<0>=NodeLab<0> + ":" + "GOTO" + TrueLab<0>.RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" + "if (" + Val<1> +") GOTO"+ TrueLab<0> + "else GOTO" + FalseLab<0>.Правила наследования атрибута Sign приведены на рис.
9.13.Программу желательно сформировать таким образом, чтобы else-меткабыла как раз меткой следующей вершины. Это можно сделать исходя из следующего утверждения.9.7. Трансляция логических выражений189Рис. 9.13Утверждение 9.4. В каждой терминальной вершине метка ближайшего правого для нее поддерева равна значению атрибута FalseLab этойвершины тогда и только тогда, когда значение атрибута Sign этойвершины равно true, а метка ближайшего правого для нее поддерева равназначению атрибута TrueLab этой вершины тогда и только тогда, когдазначение атрибута Sign равно false.Д о к а з а т е л ь с т в о .
Действительно, если ближайшей общей вершиной является AND, то в левого потомка передается NodeLab правого потомкав качестве TrueLab, причем Sign правого потомка равен true. Если жеближайшей общей вершиной является OR, то в левого потомка передаетсяNodeLab правого потомка в качестве FalseLab, тогда Sign правого потомкаравен f alse.
Во все же правые потомки значения TrueLab, FalseLab и Signпередаются из предка (за исключением правила для NOT, в котором TrueLabи FalseLab меняются местами, но одновременно меняется на противоположное и значение Sign).Эти два утверждения (3 и 4) позволяют заменить последнее правилоатрибутной грамматики следующим образом:RULEBoolExpr ::= IdentSEMANTICSCode<0>=NodeLab<0> + ":" +(Sign<0>? "if (" + Val<1> + ") GOTO" + TrueLab<0>: "if (" + Val<1> + ") GOTO" + FalseLab<0>).В свою очередь, при генерации машинных команд это правило можнозаменить на следующее:RULEBoolExpr ::= IdentSEMANTICSCode<0>="TST" + Val<1> +(Sign<0>? "BNE" + TrueLab<0>: "BEQ" + FalseLab<0>).Таким образом, для выражения A OR (B AND C AND D) OR E получимследующий код на командах перехода:1901:7:Глава 9. Генерация кодаTSTBNE2:8:4:9: TSTBEQ5:10:TSTBEQ6:TSTBNE3:TSTBEQTrue: ...False: ...ATrueB3C3DTrueEFalseЕсли элементом логического выражения является сравнение, то генерируется команда, соответствующая знаку сравнения (BEQ для =, BNE для <>, BGEдля >= и т.
д.), если атрибут Sign соответствующей вершины имеет значениеtrue, или команда, соответсвующая противоположному знаку (BNE для =, BEQдля <>, BLT для >= и т. д.), если атрибут Sign имеет значение f alse.Реализация этой атрибутной схемы приведена в программном приложениив пакете Bool.9.8. Выделение общих подвыраженийВыделение общих подвыражений относится к области оптимизации программ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
