Delphi Programming - Expression evaluation the xBase way

Copyright © 2001 Alirio A. Gavidia B.. To see more of my articles
visit Programación Orientada en Delphi (Site in Spanish)
Translated by Ernesto De Spirito with the author's permission

Introduction

A couple of years ago I was asked to solve a common "Compatibility" problem. This was to be able to evaluate xBase expressions from Delphi (by xBase we understand dBase and its derivatives like Clipper and FoxPro).

All this happens because the xBase languages based all in some form of interpretation support what is known as "Macros" (don't mistake them with the storing of a series of commands and actions for future execution).

Evaluating expressions given as strings of characters

The application created in that opportunity asked expressions to the user as search filters for queries and reports, showing each time a button that poped up a dialog form with the elements to build an expression. The expression is of xBase type, so if the user knows this kind of applications he/she can provide the expression directly.

To be or not to be, that is the question

Basically there were two alternatives:

1. Creating a control to evaluate xBase expressions.
2. Using an existent control.

The third, teaching SQL to the users, was discarded due to the principle of compatibility with the previous application.

There are interesting components in this area, matter of fact I found that there are two sets of components for this: oriented to arithmetic and oriented to databases. The first ones are practical, nice, cheap (many are freeware) but they are usually oriented to the resolution of graphs and mathematical problems. The second ones consider the matter of the fields. I got interested in the components of the second kind. I ended up using a BDE replacement with support for Clipper files that accepts xBase expressions as filters.

However, at the same time I developed some functions to evaluate expressions (they are in my web page and they are freeware, only documented in Spanish). As a part of this article I introduce the class TExpression. On the other hand I developed a components set (these are shareware in English and with documentation in English/Spanish) that allow to evaluate expressions like:

(CUSTOMER->DOB > CTOD('01/01/1900')) .AND. CREDIT

when the majority of the components that evaluate formulas don't go beyond constants expressions like:

3-2/3.14

How expressions get evaluated?

In general there are two steps: first the analysis (search) of patterns and second the combination of the values obtained in the previous step to get a result.

The patterns search (lexicography) allows to recognize in a series of characters the type and functionality of certain patterns. For example to recognize if a word starts with a digit it indicates that possibly it's a numeric literal (or an error), or otherwise the word is possibly and identifier that defines some value or operator that alters a value.

Once discovered the patterns, these are stored in some data structure (normally a stack, also I've seen it with two stacks) and they get reduced combining the values according to the identifiers. In the end what remains is the result of the expression on the stack.

And the variables?

Variables and constants and in general anything associated to an identifier has to be provided by the programmer thru an event or a list. The components I'm introducing consider both ways. They also consider arrays and functions (many predefined, mainly similar to the ones of Clipper).

For example:

HalSimpleExpr.Eval('Variable*Pi()');

In this case there are two identifiers Variable and Pi. Since the second one is followed by a pair of parenthesis it's a function. The component fires the event OnRequestIdentifier (to evaluate Variable) and OnRequestFunction (to evaluate Pi).

The evaluation of Pi would be handled this way:

procedure TForm1.HalSimpleExpr1RequestFunction(Sender: TObject;
  ident: String; var value: Variant; var cancel: Boolean);
Var
  col, row : integer;
begin
  if CompareText(ident,'Pi')=0 then
    value := Pi
  else
    cancel := true
end;

Note: I must point out that there is a great absent among the parameters of the event; this is an array with the arguments of the function. In the next version the argument of the evaluated function will be part of the parameters, but for now it's just a public field of the class.

You'll see that if the function isn't Pi, the control raises an exception (this is what the parameter cancel defines). The solution to evaluate Variable is analogous but with another event. All this works pretty well until we have some 50 functions.

We cannot use case..of

It's not possible to use the case sentence since it works with "integral" types (integer, char, boolean, etc.) and the alternative to implement one if after the other is efficient for the first identifier but terrible for the latests. The next step is using a sorted list.

Binary search

The binary search on sorted lists looks like a good alternative, if we talk of 1000 elements we can find any value in 10 steps 50% of the times (the other 50% in less). In most of the cases this is good, but there's an alternative worthy of study.

Implementation of searches by "hashing"

Better than revising a list is having a function that beforehand signals the position of the identifier in the list. For example a function that adds the first character, the last minus 97 and the length of the string. This way, if we would be looking for the word "program" we would apply something like IndexOf("program") that would return Ord('p') + Ord('m') - 97 + Length('program'), that is 112 + 109 + 7 – 97 –> 131. This would mean the position 131 of the table.

As you can see, the searching with "Hash" tables improve the search efforts dramatically. However, they waste memory. It's up to the programmer to define which path to follow, nevertheless the components I referred as shareware present lists of this kind as part of their intrinsic working.

Where SQL has not gone before

It happens that SQL solves very well the problems regarding filters and searching. But what happens if I wanted to make something less voluminous like a small spreadsheet with formulas definable by the user? For this purpose I'm attaching an example that uses a StringGrid and the class TExpression. I believe that in general there are small needs for which it it might result convenient the use of a formulas evaluator rather than intending to imitate the xBase macros.

Notes about the example

The example is a TStringGrid control that makes use of the properties Cells and Objects. The first shows the result of a formula stored in Objects. The strings have to be specified with single quotes. The files that save/load are simple text. Each defined formula requires one to press the 'ok' key to be stored. There's a defined event to handle the function Cell(c,r) where c is the column and r is the row.

Going back to the package

The use is simple, one method: eval. The expression is given as a string parameter. However, there are different methods according to the type to handle.

The components consider different types of syntax: xBase, Basic, Pascal and Java. Fundamentally altering the use of boolean operators between dots like being done in xBase expressions.

Three components with different scopes: ThalSimpleExpr, ThalMacroExpr and ThalArithmeticExpr.

The first one doesn't have functions and identifiers lists management, the second implements about 75 functions, lists management and datasets references. The third one doesn't manage "aliases" nor datasets, but nevertheless it supports many of the predefined functions.

The details are documented with the package and there are many examples included. I hope you enjoy it.

You can download the shareware demo directly from my web page:

  http://www.gavidia.org/he-shareware.zip

You can also ask for it to the following email address:

  delphi@gavidia.org.

For the examples attached to this article:

  http://www.latiumsoftware.com/en/file.php?id=p19

In http://www.gavidia.org/pod there is freeware material related with the subject.

What's next

I'll take the time to give more information about the "hash" lists that I mentioned. That will be the subject of my next article.

Copyright © 2001 by Alirio A. Gavidia B. All rights reserved.

The publication of this material is allowed by any means from anyone as long as this material is not modified and the original source is mentioned.