Part 5 – Constructing a Parse Tree
By building a parse tree, it is now possible to evaluate efficiently mathematical expressions as when plotting the graph of a function. However, all the functions that have been included in the parser are continuous. It would therefore be difficult to draw a discontinuous graph such as shown on the right.
An if function as found in Excel or LibreOffice.Calc with conditional execution makes this relatively easy.
The if function
Formally the function
returns the value of true_expression when condition is true and returns the value of false_expression if the condition is false. Here is the statement for the figure on the right: if(x < 25, 2*x, 20+2*x).
The condition, x < 25 returns true when the value of the variable x is less than 25 and false otherwise. The exact nature of such Boolean relationships will be examined later. For now, the usual convention is adopted. The logical value false is represented by the number 0 and any other number represents the logical value true.
The straightforward implementation of the if function could be as below.
Then the function could be added to the function list,
Unfortunately, it is a mistake to proceed in that fashion because both the true and false expressions as well as the condition will be evaluated by TCallNode’s Eval method to fill the args array before _if.Calc is invoked. The problem is that if statements are often used to avoid calculating the value of a function when a variable is not in its domain. If drawing the graph of x·ln(x) over the interval −2 to 2, it would be better to draw if(x <= 0, 0, x*ln(x)).
There is no way to avoid the evaluating the three parameters of the if function when it is implemented as a normal internal function. A solution is to evaluate the if function as a special case in TCallNode.Eval method. First we remove the implementation _if, it is no longer needed. Then if is registered as a function without implementation
and then TCallNode.Eval is changed.
if function
if Nodes[0].Eval = 0 then
result := Nodes[2].eval
else
result := Nodes[1].eval;
exit;
end;
end;
result := FTarget.Calc;
end;
There is a potential problem, should another function without implementation be added to the internal function list later. More egregious, the above method is not the most efficient way since at each evaluation of an internal function an unnecessary test is performed. As usual with a little more coding that test can be performed only once when parsing.
What is needed is a new node for the if function only with a simple constructor and an Eval method that calculates directly only one of the true and false expressions on the basis of the value of the condition.
The parser’s Call method must be modified to create a TIfNode instead of a TCallNode when appropriate.
One side benefit of this approach is that a better test for the could be performed. Instead of an assertion, the test against the token could verify that an if function is invoked. Of course, there is the added verification that the function was called with 3 parameters
Avoiding Boolean Operations
As will become clear later on, it requires considerable work to add Boolean comparisons such as x < 0 to the parser. The grammar must be changed, and quite a few additional classes to represent a slew of new parse tree nodes must be created. All this work can be avoided by adding a few internal functions. Versions 0.92 and earlier of the application Gaston managed with the following set of functions:
The if statement to draw the broken line if(x<25, 2*x, 20+2*x) becomes
if(lt(x,25), 2*x, 20+2*x). Other functions could be added, such as gt(x, y) and /code>ge(x, y) but these can be avoided since x > y ↔ yy < x and x ≥ y ↔ y ≤ x. By the same token one could do without ne since ne(x, y) = 1 ↔ eq(x, y) = 0 so 1–eq(x, y) is the same as ne(x, y). That equivalence may not be obvious to all, which explains why ne was included in Gaston’s parser.
It may be necessary to combine Boolean values with the usual conjunction and disjunction operators ‘and’ and ‘or’. The set of all x less than 25 or greater than 50 is written x < 25 or x > 50 while the set of all x between 25 and 50 is written x > 25 and x < 50. Again, older versions of Gaston did not implement these operators but relied on their equivalence with the mathematical operators ‘*’ and ‘+’.
Boolean Constructs
There are six infix operators that represent comparisons of numeric values. As with other infix operators, a class descendant of TBinaryNode is created for each of them. To avoid introducing type checking, the comparisons return a number of type float like all other calculations in the parser. Again 1 will represent a true statement and 0 a false one. As usual the actual evaluation is simple.
| Operator | Node | Eval method | < | TLessNode |
if Nodes[0].Eval < Nodes[1].eval
then result := 1.0 else result := 0.0 |
|---|---|---|
| <= | TLessOrEqualNode |
if Nodes[0].Eval <= Nodes[1].eval
then result := 1.0 else result := 0.0 |
| > | TGreaterNode |
if Nodes[0].Eval > Nodes[1].eval
then result := 1.0 else result := 0.0 |
| >= | TGreaterOrEqualNode |
if Nodes[0].Eval >= Nodes[1].eval
then result := 1.0 else result := 0.0 |
= (or ==) | TEqualNode |
if Nodes[0].Eval = Nodes[1].eval
then result := 1.0 else result := 0.0 |
| <> (or !=) | TNotEqualNode |
if Nodes[0].Eval <> Nodes[1].eval
then result := 1.0 else result := 0.0 |
Of course, the tokenizer will have to be modified to recognize these operators. This will be simple, there is no new problem in making those changes. There remains the question of precedence. What is to be made of the expression 5 < 3 + 3? If the comparison is done first the result is 3 since 5 < 3 yields 0. If the addition is done first, the result is 1 because 5 is less than 6. In Pascal and many other languages, comparisons have the lowest precedence so that the correct answer will be deemed to be 1. This requires a change to the grammar as a new syntactic element is added.
The main productions of the grammar, as defined in part 3, were
A new term is needed for the new element. However, it seemed better to rename the production Term { ("-" | "+") Term } to Sum in order to call the new element Expression which is defined as a Sum or a comparison of two Sums:
The reader will notice that this definition is not similar to that of Term or Sum. One could certainly define something similar to the latter. Calling it Expression2 it would be:
An Expression2 is therefore a Sum or a sequences of Sums separated by comparison operators. This definition was not adopted because it is easy to make a mess of such expressions. Just what is meant by −2 < 3 = 3? If evaluated left to right the result is 1 = 3 -> 0 and if evaluated right to left -2 &tl; 1 -> 1. Of course it could be argued that this is exactly the same problem as mentioned in part 2 of this series when Exponent was introduced. Still, Pascal does not allow such constructs, hence the definition adopted above is the one chosen here.
There are three more operators required to complete the handling of logical statements: logical negation (not), conjunction (and), disjunction (or). Exclusive disjunction (xor) was not added. While bitwise xor is useful, the logical version is actually the same as not equal.
| Operator | Node | Eval method | ! | TNotNode |
if Nodes[0].Eval = 0 then result := 1.0
else result := 0.0 |
|---|---|---|
| & (or &&) | TAndNode |
if (Nodes[0].Eval = 0) or (Nodes[1].eval = 0)
then result := 0.0 else result := 1.0 |
| | (or ||) | TOrNode | if (Nodes[0].Eval = 0) and (Nodes[1].eval = 0) then result := 0.0 else result := 1.0 |
As discussed in the previous section conjunction is akin to multiplication, it will be handled as a Term. Disjunction on the other hand is like addition, and handled in Sum. The logical negation is just like the unary "-". So here is the complete augmented grammar
The following graph shows the hierarchy of nodes used to construct a parse tree. There are so many nodes descending from the class TBinaryNode, that they are shown piled one on top of the other in groups corresponding to the syntactic elements Exponent, Term, Sum and Expression left to right along the bottom and the arrow from TBinaryNode to each descendant is not drawn.
Of course the other six classes are used to represent a Factor.
In conclusion, it is tedious but not at all difficult to add logical and Boolean expression.
Source code
The source code for all units making up the parser is available along with a simple demonstration programme and test code. It is in the archive ParsingMathExpr-6.zip.
The demonstration program compiles with Delphi version 2 and up. It should also compile with Lazarus/FreePascal with minimal changes. As before, unit tests require DUnit.pas which works with newer versions of Delphi only. Unit testing was done with Delphi 2010.