Quark's place

Parsing and Evaluating the Script

Introduction

On the library introduction page we used Pythagoras’s theorem to calculate the hypotenuse of a right angle triangle where the other sides were 5 and 12. .

println(Solver.evaluate("sqrt(5^2 + 12^2)"));

Here is the code and the answer is 13, but how did QScript do it.

Although we can scan the expression above and decide the order of evaluation the computer needs some help. So before the computer can give us the answer it must be converted into something the computer can understand.

Parsing and Tokenising the expression

The first stage is to break the expression down into tokens. A token maybe a number, literal string, a variable or an operator or function. If we look at the result of parsing the above expression we get

-------- Infix List  -------------
Line  Pos  Width  Token
0     0    4      sqrt(1)   Pr 30
0     4    1      (         Pr 12
0     5    1      5
0     6    1      ^         Pr 27
0     7    1      2
0     9    1      +         Pr 24
0    11    2      12
0    13    1      ^         Pr 27
0    14    1      2
0    15    1      )         Pr 11
----------------------------------

This is called the infix list, and the tokens are in the order that they appear in the expression. Unfortunately this order is not the easiest for a computer to process so another algorithm is used to convert it into postfix order which we can see here.

-------- Postfix List ------------
Line  Pos  Width  Token
0     5    1      5
0     7    1      2
0     6    1      ^         Pr 27
0    11    2      12
0    14    1      2
0    13    1      ^         Pr 27
0     9    1      +         Pr 24
0     0    4      sqrt(1)   Pr 30
----------------------------------

Notice that the '(' and ')' tokens have dissappeared. In maths these are used to change the order mathematical operations are performed but they are no longer needed because the tokens are in the correct order for evaluation. I am not going into further details here, if you are interested in knowing more about the topic then Google awaits!

If a syntax error is detected then a SyntaxException is thrown and a scripting event is fired. Possible causes of syntax errors include -

unmatched or missing parentheses
unmatched flow operator e.g. IF without ENDIF
comma found when not expected
unclosed literal string
invalid number format
expecting an operator but none persent
invalid number of arguments

Evaluating the expression

Once parsed the expression can be evaluated many times. For instance in the graphing example each equation is evaluated hundreds of times (with different starting values) but the parsing was only done once. In the prime number sieve example parts of the script have to be evaluated many times because of the loops but again the algorithm was only parsed once. This makes the library very quick in these situations.

Even though there are no syntax errors we can still get evaluation errors such as

the script has not been parsed
invalid argument types e.g. expected a number and got a boolean
attempting to use an uninitialised variable
left-hand-side of asignment statemnt is not a variable

If any of these occur evaulation stops immediately and, an EvaluationException is thrown and a scripting event is fired.

Evaluation can also be halted by the user and when the script times out. A time-out occurs when the script's execution time exceeds a predetermined value, this protects against inifinite loops.

Error handling modes

Since exceptions are thrown when an error occurs the user can decide whether to let the libray catch and process them (BASIC mode) or the user to catch and deal with them (EXPERT mode). In BASIC mode error messages are simply printed to the Java console window, EXPERT mode allows greater flexibility but requires more effort from the programmer.

The other option is to catch the scripting events that are fired, this is really useful for scripts evaluated in a separate thread since the events are asynchronous. The other advantage of using event handling is that other evnts are fired and used to trace the evaluation progress.

Scripting Events

Events are fired when

a parse error occured
an evaluation error occured
a token has been processed (used for tracing the evaluation)
the script is paused with the WAIT operator
the script is resumed after a pause
the execution is halted by user or timeout
the script has finished evaluation normally
a variable has been updated
a print or println operators has outputted to the console window