★ CODING ★ 13. IMPLEMENTING THE EXPRESSION EVALUATOR ★ |
| Writing Adventure Games on the Amstrad - 00 - Contents | Writing Adventure Games on the Amstrad - 13 - Implementing the expression evaluator |
The behaviour of the AKS expression evaluator has already been discussed. This chapter explains how the AKS Basic program arrives at a result of true or false for a conditional expression. This description of the expression evaluator will be invaluable should you decide to alter the terminology, implement additional operators or allow the use of further flags and predicates. In addition, the expression evaluator in AKS illustrates some fundamental programming techniques and data structures. The Basic code corresponding to the expression evaluator is contained in the subroutine *evalthis* and the subroutines it invokes. On entry to this routine, the expression string should be stored in the variable 'expr$'. On exit, the variable 'res' holds the result of true or false. The integer values representing true or false are -1 and 0 respectively. This is the same as the internal notation used by Amstrad Basic when it evaluates conditional expressions in IF statements. Consequently, the AKS program can test the result returned by *evalthis* as follows: IF res THEN . . . Thus to evaluate an expression, AKS copies the expression string into expr$ and calls *evalthis*. Often, the AKS program wishes to read in the next string and then evaluate it. This is reflected in the presence of the subroutine 'evalnext*, which reads the next string in the DATA into 'expr$' and then calls *evalthis* to evaluate it. Considering that the function of *evalthis* is to return something which can be tested by a Basic IF statement, it may seem pointless to go to the trouble of writing a conditional expression evaluator to do the same thing as the existing Amstrad Basic conditional expression evaluator. Take for example, the AKS condition string (having already stripped off the preceding -(W3/C3).V12 It is not difficult to see how, by substituting 'NOT' for'OR' for 7' and 'AND' forthis could be transformed into the string: NOT (W3 OR C3) AND V12 Now if you replaced all occurrences of sequences of digits by '(', the sequence of digits itself and the resulting string appears to become a Basic conditional expression: NOT (W(3) OR C(3)) AND V(12) Given that the arrays W, C and V existed and contained true/false values (-1 or 0), it would be very convenient if Amstrad Basic could then be made to evaluate this for us. Unfortunately, this information is locked inside a string variable and Amstrad Basic is unable to evaluate a string variable. For example, it is INVALID to write in a program: IF expr$ THEN . . . Some Basics have a command to overcome this problem and force the Basic interpreter to evaluate a string. A very 'dirty' way in which Amstrad Basic could be made to evaluate a string would be to convert the string into Amstrad Basic's internal representation and POKE this into the program between an IF and a THEN and then execute this line. However, AKS expressions are variable lengths and so other parts of the program would need to be adjusted to create exactly the right number of spaces between the IF and the THEN. An alternative method of evaluation must be used. Therefore, the AKS program is forced to do a step by step evaluation of 'expr$'. Ignoring the trivial case of 'expr$' being just '*' where *evalthis* returns true, the evaluation process can be divided into three stages:
Although the evaluation takes place in three logical stages, in practice stage 1 can be performed during the same scan through the expression string as stage 2. A brief glance at *evalthis* reveals that it has two subroutines performing the three stages:
The letters 'RP' stand for Reverse Polish. An expression written in Reverse Polish notation requires no brackets or operator prededence as the ordering of the expression precisely represents the order of evaluation. To achieve this, Reverse Polish notation places an operator after its operands, giving rise to the alternative name of postfix notation. The normal notation used in mathematics and Basic is called infix notation and places an operator in between its operands. The scenario writer is allowed to write AKS expressions in infix notation for the sake of readability. It would be unacceptable to force the scenario writer to learn Reverse Polish before he could use AKS. However, anyone who has done a lot of programming in the language Forth, which uses Reverse Polish all the time, may be happier writing expressions in Reverse Polish. If this is the case, the *converttoRP* subroutine can be replaced by a subroutine which just performs stage 1 of the evaluation process. A slight increase in the execution speed would also be achieved. To help convince you to stick to infix notation, some examples of infix AKS expressions and their corresponding Reverse Polish versions are given below:
The subroutine *converttoRP* converts the infix expression held in 'expr$' into the Reverse Polish equivalent which is returned in 'revpol$'. It repeatedly calls 'getlex* to get the next operator or operand from 'expr$'. It is the subroutine 'getlex* which performs the substitution of flags and predicates for either't' or 'f to perform 1 of the evaluation process. When *getlex* encounters an operator (ie. next character is '/', V,'(' orit simply returns it to *converttoRP* in 'dat$'. However, if it encounters a flag or predicate (ie. next character is 'F', 'V', 'W, 'C', L' or 'O') then it calls *evalflag* to determine a value of true or false and set 'dat$' to 't1 or 'f accordingly. Having performed stage 1 of the evaluation, "converttoRP* must reorder the lexical units returned by calls to *getlex* to form Reverse 3olish. There are several algorithms which could be used to do this reordering and removal of brackets. All of these algorithms require a means of determining the priority of operators shown below:
The algorithm used in AKS is often referred to as the Shunting Algorithm. This name arises from an analogy with a simple railway network, shown in the diagram below. OUTPUT -----------+-------<------+------------ INPUT Let us ignore brackets for the moment. The algorithm takes carriages (lexical units) from 'input' (infix expression) one at a time. If the carriage is type-A (operand) then it passes straight across to 'output' (Reverse Polish). However, if the carriage is type-B (operator) it goes into the 'siding'. Each carriage has a priority (operator priority). When a new carriage approaches the 'siding' it allows carriages already in the 'siding' to go to 'output' one at a time until a carriage of lower priority is at the front of the 'siding'. The new carriage then takes its place at the front of the 'siding'. Eventually, there are no more carriages at 'input' and all the carriages in the 'siding' are allowed to continue to 'output'. The Reverse Polish expression is now at 'output'. An example conversion using this algorithm is given below. For clarity, flags and predicates are shown as their identifiers instead of their actual't' or 'f values from stage 1.
By a simple extension, this algorithm can be made to remove brackets after they have served their purpose. Firstly, the symbol ')' must be considered as the highest priority operator. When a '(' is encountered it goes into 'siding' obeying the same rules as the other operators. The algorithm then continues as normal until a ')' is encountered. This causes all operators in 'siding' to be released to 'output' until a '(' is reached. This bracket pair can now be discarded. For example:
In computing terms, a structure called a stack embodies the idea of the 'siding'. Machine code programmers will undoubtedly be very familiar with the operation of the Amstrad's hardware stack. The AKS program is unable to use this stack freely because Amstrad Basic is using it as the program is running. Therefore AKS maintains its own software stack. Whether it is implemented in hardware or in software, a stack has the same logical structure. There are two operations associated with a stack, adding an item and removing an item. In Z80 assembler these operations are known as PUSH and POP respectively. AKS uses somewhat the more readable names of 'stack' and 'unstack' for the subroutines performing these operations. The important thing to remember about a stack is the Last In First Out (LIFO) rule, which means last item in will be the first item out. This is the reason for the analogy of the Shunting Algorithm where the last carriage in is always the first carriage out. The internal mechanism by which the status of a stack is maintained is by a pointer to the next free element of the stack. The AKS stack elements are held in an array called 'stack' and the pointer to the next free element of 'stack' is 'stacktop'. At the start of the program 'stacktop' is initialised to point to the first element of 'stack'. From then on, 'stacktop' is only changed by the 'stack* and 'unstack* subroutines. Stacking or unstacking a variable is done by storing the value of the variable in 'dat' and calling *stack* or *unstack* respectively. Having converted the infix string into Reverse Polish it must be evaluated. This can be done very simply by the use of a stack. As *converttoRP* has finished using the software stack, *evaluateRP* can make use of the same stack. The algorithm scans through 'revpol$' one character at a time from left to right. If the character is an operand ('t' or 'f') then stack it. if the character is an operator then take the required number of operands off the stack, perform the operation and stack the result of 't' or T. The binary operators, 7 and '/' will unstack two operands whereas the unary operatorwill just unstack one operand. When all the characters in 'revpol$' have been processed, a single value remains on the stack. If this value is 't', 'dat' is set to 'true' otherwise 'dat' is set to 'false'. The expression has now been fully evaluated. However, what happens if the original 'expr$' was incorrect? Fortunately, this method of expression evaluation allows simple checks to be made at each stage of the evaluation process to detect the validity of the expression. Firstly, if any invalid characters (ie. not in ()FVWCLO" or a digit) are included then these are recognized during the initial scan through the string — stage 1 of the evaluation process. Missing numbers after a flag or predicate character (eg. '(C/W3)') are detected when the evaluator attempts to substitute't' or 'f for the flag/ predicate — stage 2. Finally, an incorrectly structured expression (eg. '(C3/W3)V12') will be detected after the Reverse Polish expression has been evaluated because the stack will hold more than just the result — at the end of stage 3.
|
