An Algorithm for Translating Boolean Expressions

Publisher Website
Google Scholar
Abstract
This paper describes an algorithm for scanning Boolean expressions. Such an algorithm takes a complex, relational expression and transforms it into an optimal set of computing steps. The result is optimal in the sense that no redundant evaluations are made. The particular algorithm described is advantageous in that, as a variant of a well-known arithmetic scan, it fits into a general scheme for the translation of statements to machine language. Consistent with this arithmetic expression scan, which is included as a starting point for the development, this Boolean scan does not require the re-ordering of subex- pressions. Various algorithms for scanning algebraic expressions and decomposing them into standard forms equivalent to Polish prefix notation are quite well known by now. One such algorithm involves scanning the expression from right to left and retaining operands, operations, relations etc., on a list L until an operation or relation ~ occurs which is of lower precedence than the immediately preceding operation or relation on the list, ~j-1. When such an operation or relation as ~i is encountered, ~s-1 is compiled (or executed, if one is interpreting). The compilation consists here of creating a row of a three-column matrix M, so that if ~i-1 = "+", the row of M (say row i) created for a + b would be M~i = "a", Me = "+", M~a = "b". Figures 1 and 2 below show a flow diagram for the scan. (This diagram is similar to others which have appeared in the Communications of the ACM (1, 2), but it is more complete.) Entries and exits indicated by dotted lines are discussed later in this paper and should be ignored for the present. This diagram assumes that the expression to be scanned is stored in a list S, with the leftmost symbol in $1, the next in $2, and so on. (We assume that blanks have been deleted.) The symbols "1-" and "-~" represent left and right termination characters which are generated by the algorithm. The precedence hierarchy assumed here is as follows. t "'" )

This publication has 3 references indexed in Scilit: