BOOL7 (1131436)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

8.7. Трансляция логических выражений

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

A AND B эквивалентно if A then B else False,

A OR B эквивалентно if A then True else B.

Если в качестве компонент выражений могут входить функции с побочным эффектом, то, вообще говоря, результат вычисления может зависеть от способа вычисления. В некоторых языках программирования не оговаривается, каким способом должны вычисляться логические выражения (например, в Паскале), в некоторых требуется, чтобы вычисления производились тем или иным способом (например, в Модуле-2 требуется, чтобы выражения вычислялись по приведенным формулам), в некоторых языках есть возможность явно задать способ вычисления (Си, Ада). Вычисление логических выражений непосредственно по таблицам истинности аналогично вычислению арифметических выражений, поэтому мы не будем их рассматривать отдельно. Рассмотрим подробнее способ вычисления с помощью приведенных выше формул (будем называть его "вычисления с условными переходами"). Иногда такой способ рассматривают как оптимизацию вычисления логических выражений.

Рассмотрим следующую атрибутную грамматику со входным языком логических выражений:

RULE
Expr ::= BoolExpr
SEMANTICS
FalseLab<1>=False; TrueLab<1>=True;
Code<0>=Code<1>.

RULE
BoolExpr ::= BoolExpr 'AND' BoolExpr
SEMANTICS
FalseLab<1>=FalseLab<0>; TrueLab<1>=NodeLab<3>;
FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;
Code<0>=NodeLable<0>+”:”+Code<1>+Code<3>.

RULE
BoolExpr ::= BoolExpr 'OR' BoolExpr
SEMANTICS
TrueLab<1>=TrueLab<0>; FalseLab<1>=NodeLab<3>;
FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;
Code<0>=NodeLable<0>+”:”+Code<1>+Code<3>.

RULE
BoolExpr ::= F
SEMANTICS
Code<0>=“GOTO FalseLab<0>“.

RULE
BoolExpr ::= T
SEMANTICS
Code<0>=“GOTO TrueLab<0>“.

Здесь предполагается, что все вершины дерева занумерованы и номер вершины дает атрибут NodeLab. Метки вершин передаются, как это изображено на рис. 8.20.

TrueLab FalseLab
FalseLab TrueLab





FalseLab TrueLab TrueLab FalseLab
FalseLab TrueLab
TrueLab NodeLabel FalseLab NodeLabel
AND OR
Рис. 8.20.

Сопоставим каждому атрибутированному дереву в этой атрибутной грамматике текст (трансляцию), полученный следующим образом в результате обхода дерева сверху вниз слева направо: при входе в вершину будем генерировать ее номер, в вершине 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 T
| FalseLab=False
1 TrueLab=True

TrueLab=True OR
FalseLab=2 FalseLab=False
F 2 TrueLab=True

TrueLab=True OR
FalseLab=3

4 3
|
TrueLab=5 AND T
FalseLab=3 TrueLab=True
FalseLab=3
F 5

TrueLab=6 AND 1: GOTO 2
FalseLab=3 TrueLab=True 2:
FalseLab=3 4: GOTO 3
T 6 5: GOTO 6
| 6: GOTO True
T 3: GOTO True

Рис. 8.21 Рис. 8.22

Эту линеаризованную запись можно трактовать как программу вычисления логического значения: каждая строка может быть помечена номером вершины и содержать либо переход на другую строку, либо переход на True или False, что соответствует значению выражения true или false, либо пусто. Будем говорить, что полученная программа вычисляет (или интерпретирует) значение выражения, если в результате ее выполнения (от первой строки) мы придем к строке, содержащей GOTO True или GOTO False.

Утверждение 1. Для любого логического выражения, состоящего из констант, программа, полученная в результате обхода дерева этого выражения, завершается со значением логического выражения в обычной интерпретации, т.е. осуществляется переход на True для значения, равного true, и переход на метку False для значения false.

Это утверждение является частным случаем следующего.

Утверждение 2. В результате интерпретации поддерева с некоторыми значениями атрибутов FalseLab и TrueLab в его корне выполняется команда GOTO TrueLab, если значение выражения истинно, и команда GOTO FalseLab, если значение выражения ложно.

Доказательство можно провести индукцией по высоте дерева. Для деревьев высоты 1, соответствующих правилам BoolExpr ::= F и BoolExpr ::= T, утверждение очевидно из правил грамматики. Пусть дерево имеет высоту n>1. Зависимость атрибутов для дизъюнкции и конъюнкции приведена на рис. 8.23

FalseLab0
TrueLab0

AND
FalseLab1=FalseLab0 FalseLab2=FalseLab0
TrueLab1=NodeLab2 TrueLab2=TruLab0

FalseLab0
TrueLab0

OR
FalseLab1=NodeLab2 FalseLab2=FalseLab0
TrueLab1=TruLab0 TrueLab2=TruLab0




Рис. 8.23

Если для конъюнкции значение левого поддерева ложно и по индукции вычисление левого поддерева завершается командой GOTO FalseLab1, то и интерпретация всего дерева завершается командой GOTO FalseLab0 (=FalseLab1). Если значение левого поддерева истинно, то его интерпретация завершается командой GOTO TrueLab1 (=NodeLab2). Если значение правого поддерева ложно, то интерпретация всего дерева завершается командой GOTO FalseLab0 (=FalseLab2). Если же оно истинно, интерпретация всего дерева завершается командой GOTO TrueLab0 (=TrueLab2). Аналогично - для дизъюнкции.

Доказательство утверждения 1 следует из того, что метками вершины дерева логического выражения являются TrueLab=True и FalseLab=False.

Добавим теперь новое правило в предыдущую грамматику:

RULE
BoolExpr ::= Ident
SEMANTICS
Code<0>=”if (Val<1>==T)GOTO TrueLab<0>
else GOTO FalseLab<0>”;

Тогда, например, для предыдущего выражения получим следующую программу:

1: if (F==T) then GOTO True else GOTO 2
2:
4: if (F==T) GOTO 5 else GOTO 3
5: if (T==T) GOTO 6 else GOTO 3
6: if (T==T) GOTO True else GOTO 3
3: if (T==T) GOTO True else GOTO False

При каждом конкретном наборе данных эта программа превращается в программу вычисления логического значения.

Утверждение 3. В каждой строке программы, сформированной предыдущей атрибутной схемой, одна из меток совпадает с меткой следующей строки.

Действительно, по правилам наследования атрибутов TrueLab и FalseLab, в правилах для дизъюнкции и конъюнкции либо FalseLab, либо TrueLab принимает значение метки следующего поддерева. Кроме того, как значение FalseLab, так и значение TrueLab, передаются в правое поддерево от предка. Таким образом, самый правый потомок всегда имеет одну из меток TrueLab или FalseLab, равную метке правого брата соответствующего поддерева. Учитывая порядок генерации команд, получаем утверждение.

Дополним теперь атрибутную грамматику следующим образом:

RULE
Expr ::= BoolExpr
SEMANTICS
FalseLab<1>=False; TrueLab<1>=True;
Sign<1>=false;
Code<0>=Code<1>.

RULE
BoolExpr ::= BoolExpr 'AND' BoolExpr
SEMANTICS
FalseLab<1>=FalseLab<0>; TrueLab<1>=NodeLab<3>;
FalseLab<3>=FalseLab<0>; TrueLab<3>=TrueLab<0>;
Sign<1>=false; Sign<3>=Sign<0>;
Code<0>=NodeLable<0>+”:”+Code<1>+Code<3>.

RULE
BoolExpr ::= BoolExpr 'OR' BoolExpr
SEMANTICS
TrueLab<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>.

RULE
BoolExpr ::= NOT BoolExpr
SEMANTICS
FalseLab<1>=TrueLab<0>; TrueLab<1>=FalseLab<0>;
Sign<1>=! Sign<0>;
Code<0>=Code<1>.

RULE
BoolExpr ::= F
SEMANTICS
Code<0>=”GOTO FalseLab<0>”.

RULE
BoolExpr ::= T
SEMANTICS
Code<0>=”GOTO TrueLab<0>”.

RULE
BoolExpr ::= Ident
SEMANTICS
Code<0>=”if (Val<1>==T) GOTO TrueLab<0>
else GOTO FalseLab<0>”.

Правила наследования атрибута Sign приведены на рис. 8.24.

f alse | true | false | true |
OR OR AND AND



true false true true false false false true

true false

NOT NOT


false true

Рис. 8.24

Программу желательно сформировать таким образом, чтобы else-метка была как раз меткой следующей вершины. Как это можно сделать, следует из утверждения 4.

Утверждение 4. В каждой терминальной вершине, метка ближайшего правого для нее поддерева равна значению атрибута FalseLab этой вершины, тогда и только тогда, когда значение атрибута Sign этой вершины равно true, и наоборот, метка ближайшего правого для нее поддерева равна значению атрибута TrueLab этой вершины, тогда и только тогда, когда значение атрибута Sign равно false.

Эти два утверждения позволяют заменить последнее правило атрибутной грамматики следующим образом:

RULE
BoolExpr ::= Ident
SEMANTICS
Code<0>=Sign<0>
? ”if (Val<1>==T) GOTO TrueLab<0>”
: ”if Val<1>==F) GOTO FalseLab<0>”.

В свою очередь, при генерации машинных команд это правило можно заменить на следующее:

RULE
BoolExpr ::= Ident
SEMANTICS
<TST Ident>;
Code<0>=Sign<0>
? ”BNE TrueLab<0>”
: ”BEQ FalseLab<0>”.

Если элементом логического выражения является сравнение, то генерируется команда, соответствующая знаку сравнения (beq для =, bne для <>, bge для >= и т.д.), если атрибут sign соответствующей вершины имеет значение true, и отрицание (bne для =, beq для <>, blt для >= и т.д.), если атрибут sign имеет значение false.

Приведем несколько примеров. Выражение A AND (B OR C) транслируется в последовательность команд рис. 8.25. Выражение (NOT((A==B)OR(!=D)))AND(NOT((E<F)AND(G>H))) транслируется в последовательность команд рис. 8.26.

TST A CMP A,B
BEQ False BEQ False
TST B CMP C,D
BNE True BNE False
TST C CMP E,F
BEQ False BGE False
True: CMP G,H
False:. . . BGT False
True:
False:

Рис. 8.25 Рис. 8.26

151

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ответов (шпаргалок)