In the previous article, we documented the behavior and syntax of UCL expressions. In this article, we will look at the support code and definitions used by the expression parsing and evaluation.

First let us examine the Get_Token function. We've used this function previously to get the next token from the input stream. It is a wrapper for the parser class, of which UCL uses an instance. We won't cover the TParser class here (or any time soon), but the Get_Token function is important to the operation of UCL expression parsing.

function Get_Token : string ;

var S : string ;

begin
    Result := Parser.Token ;
    if( copy( Result, 1, 1 ) = '!' ) then // Comment
    begin
        while( copy( Result, 1, 1 ) = '!' ) do 
        begin
            Parser.Get_Token_Line ;
            Result := Parser.Token ;
        end ;
    end ;
    if( copy( Result, 1, 1 ) = '%' ) then // Possible hexadecimal value
    begin
        S := Parser.Token ;
        if( lowercase( copy( S, 1, 1 ) ) = 'x' ) then
        begin
            Result := Result + S ;
        end else
        begin
            Parser.Put_Token( S ) ;
        end ;
    end else
    if( Result = '.' ) then // operator
    begin
        Result := '.' + Parser.Token + Parser.Token ;
    end ;
end ;

function Valid_Int( S : string ; var I : int64 ) : boolean ;

begin
    if( copy( S, 1, 2 ) = '%X' ) then
    begin
        S := copy( S, 3, length( S ) ) ;
        if( not Valid_Hex( S ) ) then
        begin
            Result := False ;
            exit ;
        end ;
        Result := True ;
        I := From_Hex( S ) ;
        exit ;
    end ;
    Result := trystrtoint64( S, I ) ;
end ;

function UCL_Strtoint( S : string ) : string ;

var I : int64 ;

begin
    Result := '' ;
    if( copy( S, 1, 2 ) = '%X' ) then
    begin
        S := copy( S, 3, length( S ) ) ;
        if( not Valid_Hex( S ) ) then
        begin
            Result := '0' ;
            exit ;
        end ;
        Result := inttostr( From_Hex( S ) ) ;
        exit ;
    end ;
    if( Valid_Int( S, I ) ) then
    begin
        Result := S ;
        exit ;
    end else
    if( S = '' ) then
    begin
        Result := '0' ;
    end else
    if( pos( S[ 1 ], 'TtYy' ) = 0 ) then
    begin
        Result := '0' ;
    end else
    begin
        Result := '1' ;
    end ;
end ;

const Op_EQ = 1 ;
const Op_EQS = 2 ;
const Op_NE = 3 ;
const Op_NES = 4 ;
const Op_GE = 5 ;
const Op_GES = 6 ;
const Op_LE = 7 ;
const Op_LES = 8 ;
const Op_GT = 9 ;
const Op_GTS = 10 ;
const Op_LT = 11 ;
const Op_LTS = 12 ;
const Op_NOT = 13 ;
const Op_OR = 14 ;
const Op_AND = 15 ;
const Op_Multiply = 20 ;
const Op_Divide = 21 ;
const Op_Add = 22 ;
const Op_Subtract = 23 ;

const Function_Context = 100 ;
const Function_CSID = 101 ;
const Function_Cunits = 102 ;
const Function_Cvsi = 103 ;
const Function_Cvtime = 104 ;
const Function_Cvui = 105 ;
const Function_Delta = 106 ;
const Function_Device = 107 ;
const Function_Directory = 108 ;
const Function_Edit = 109 ;
const Function_Element = 110 ;
const Function_Environment = 111 ;
const Function_Extract = 112 ;
const Function_FAO = 113 ;
const Function_FID_To_Name = 114 ;
const Function_File_Attributes = 115 ;
const Function_GetDVI = 116 ;
const Function_Getenv = 117 ;
const Function_GetJPI = 118 ;
const Function_GETQUI = 119 ;
const Function_GETSYI = 120 ;
const Function_IDENTIFIER = 121 ;
const Function_INTEGER = 122 ;
const Function_LENGTH = 123 ;
const Function_LICENSE = 124 ;
const Function_LOCATE = 125 ;
const Function_MATCH_WILD = 126 ;
const Function_MESSAGE = 127 ;
const Function_MODE = 128 ;
const Function_MULTIPATH = 129 ;
const Function_PARSE = 130 ;
const Function_PID = 131 ;
const Function_PRIVILEGE = 132 ;
const Function_PROCESS = 133 ;
const Function_SEARCH = 134 ;
const Function_SETPRV = 135 ;
const Function_STRING = 136 ;
const Function_TIME = 137 ;
const Function_TRNLNM = 138 ;
const Function_TYPE = 139 ;
const Function_UNIQUE = 140 ;
const Function_USER = 141 ;
const Function_VERIFY = 142 ;

// UCL errors...
const UCL_OK = 0 ; // No error
const UCL_ARGREQ = 1 ; // Missing argument
const UCL_EXPSYN = 2 ; // Invalid expression syntax
const UCL_IVCHAR = 3 ; // Invalid numeric value
const UCL_IVKEYW = 4 ; // Unrecognized keyword
const UCL_IVOPER = 5 ; // unrecognized operator in expression
const UCL_MISSRP = 6 ; // Missing right parenthesis
const UCL_NOLBLS = 7 ; // Label ignored
const UCL_NULFIL = 8 ; // Missing or invalid file specification
const UCL_ONERR  = 9 ; // use WARNING, SEVER, ERROR or CONTROL_Y
const UCL_ONLEVL = 10 ; // Invalid ON context
const UCL_SYMDEL = 11 ; // Invalid symbol or value delimiter
const UCL_UNDSYM = 12 ; // Undefined symbol

Expression Trees
The expression evaluation occurs in two phases: 1) parsing, and 2) evaluating. The parsing phase builds an expression tree for later evaluation. The expression tree is a binary tree, which we will look at in a moment. But first, why create a tree and then evaluate it rather than evaluate as we go? Certainly, we could take that approach. However, the issue of precedence (discussed in the previous article) would make the code more complicated. Instead, we create the tree, and make slight adjustments to it based on precedence as we encounter operators and parentheses. Once the entire expression is parsed, the tree is complete and the evaluation is done recursively - as we will see in a couple articles from now. The tree recursion is, perhaps, the simplest way to evaluate things in precedence order. We'll look at the tree structure next, but first here is the structure we use for each node in the tree:

type tExpression_Node = class
                            Operator : longint ; // Operator
                            Precedence : integer ; // Precedence of node
                            Back, Left, Right : tExpression_Node ;
                            Value : Ansistring ;
                        end ;

Before we continue looking at code, let's consider some simple examples of expression trees to illustrate what we will be building.

These three examples of expression trees should help illustrate what we are talking about. Before any operator node can be evaluated, all sub-trees must first be evaluated. Thus, placing higher precedence operators into subtrees ensures that they will be evaluated before other operations. Such is the case with the rightmost example. Before the addition operation in the root node can be evaluated, the right sub-tree has to be evaluated. Evaluating that sub-tree gives us a value of 6. Then the addition can be done, resulting in 7. Using parentheses changes the tree structure so that the sub-trees that are evaluated first are those within the parentheses. For example:

Once we've evaluated the expression tree, we will need to free up the memory used by the data structure. The following function accomplishes this:

procedure Zero_Expression_Tree( X : tExpression_Node ) ;
// Zero storage stored at tree with root X

var Current, Previous : tExpression_Node ;

begin
    // Start at root
    Current := X ;
    while( Current <> nil ) do
    begin
        // Go all the way left 
        while( Current.Left <> nil ) do
        begin
            Current := Current.Left ;
        end ;
        if( Current.Right <> nil ) then
        begin
            Current := Current.Right ;
        end else
        begin
            Previous := Current.Back ;
            if( Previous <> nil ) then
            begin
                if( Previous.Left = Current ) then
                begin
                    Previous.Left := nil ;
                end else
                begin
                    Previous.Right := nil ;
                end ;
            end ;
            Current.Free ;
            Current := Previous ;
        end ;
    end ; // while( Current <> nil ) do
end ; // Zero_Expression_Tree

We'll leave it here for now. In the next article, we will look at the parsing code itself, as it builds the expression tree. That will be a long enough article by itself, so we put the support code in this separate article so that the next one won't be so long.