Browse Prior Art Database

Evaluation of Logical Expressions

IP.com Disclosure Number: IPCOM000035766D
Original Publication Date: 1989-Aug-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 4 page(s) / 43K

Publishing Venue

IBM

Related People

Coyle, DJ: AUTHOR [+2]

Abstract

This describes a method of evaluating logical expressions by use of a stack, but allows for early termination when the answer is determined.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 4

Evaluation of Logical Expressions

This describes a method of evaluating logical expressions by use of a stack, but allows for early termination when the answer is determined.

A logical expression is defined as one of the following: 1. A predicate. This is a statement that is TRUE, FALSE, or UNKNOWN.

For example, "A>10". 2. Two logical expressions connected by "AND" or "OR" For example, "A=5 OR A=10". 3. A logical expression in parentheses. For example, "(A<100)". 4. A logical expression preceded by "NOT". For example, "NOT A=1" or "NOT (A>10 OR B>10)".

The operators AND, OR, and NOT result in the values TRUE, FALSE, or UNKNOWN, by combining their operands according to the following tables:

By convention, an expression involving ANDs and ORs is evaluated by evaluating the ANDs first, and then the ORs. Parentheses can be used to override this convention. For example, the expression A=5 OR A=10 AND B<100 is equivalent to

A=5 OR (A=10 AND B<100) This example would be TRUE if

either

1. A had the value 5, or

2. A had the value 10 and B's value was less than 100.

It is commonly understood in computer science that one need not always evaluate every predicate in order to determine the value of the whole expression. For example, in the expression X>10 AND Y>20 one would first check the value of X against 10. If X is not greater, there is no need to evaluate the second operand of the AND. Since the first operand is FALSE, the result of the AND will always be FALSE, no matter what the result of the second operand would be. Likewise, if the first operand of an OR is TRUE, the second operand has no effect on the result, and thus need not be evaluated.

This invention is a method of producing code to evaluate a logical expression, using a stack to record the results of intermediate results, while taking advantage of the fact that not all components of the expression may need to be processed.

The code produced for a predicate is conventional comparison operations, and perhaps arithmetic operations, and the details are not pertinent to this discussion. Such code will be represented here simply as 'pred1', 'pred2', etc., corresponding to the same names in the expression examples. For brevity, TRUE, FALSE, and UNKNOWN will be represented by T, F, and U, respectively.

Code for logical expressions consists of the predicates' code, and the JF, JT, AND, OR, and NOT instructions, built as explain...