## 4. Simple recursive parser

Now let's see a small example. We will create a parser that can evaluate expressions with additions. That means we only need to recognize one operator, "+".In the code below you can see that the function Eval calls itself twice by calculating the answers of part1 and part2 of the expression. This is the recursive part of the parser. It does not matter if part1 and part2 are also expressions, in that case the function Eval will be called again and again until the expression is solved. That is when the end of all brances of the expression tree are reached.

Example 1

AUTODEFINE "Off" DEF inputexpr:STRING OPENCONSOLE/* Recursive expression parser, Example 1. Written with IBasic Professional By Jos de Jong, may 2006 Supports expressions with additions */PRINT "Examples:" PRINT "2 + 3 = ", Eval("2 + 3") PRINT "2 + 3 + 4 + 5 = ", Eval("2 + 3 + 4 + 5") PRINT "2.5 + 3.25 = ", Eval("2.5 + 3.25") PRINT "" PRINT "Enter an expression and press Enter to calculate it." PRINT "Enter an empty expression to quit" DO'print some examples of expressions with their answers'ask the user to enter an expression. After this the expressionINPUT ">>", inputexpr IF RTRIM$(inputexpr)<>"" PRINT " Ans = ", Eval(inputexpr) ENDIF UNTIL RTRIM$(inputexpr)=""'will be evaluated and the answer will be printedCLOSECONSOLE END'end the programSUB Eval(Expression:STRING), DOUBLE DEF pos:INT DEF expr:STRING DEF part1, part2:STRING'_____________________________________________________________________expr = LTRIM$(RTRIM$(Expression))'remove spaces at start and end of the expressionpos = INSTR(expr, "+") IF pos'search for an operator'there is an operator found at position pos. Split up the'expression in two parts and calculate the result of that twopart1 = LEFT$(expr, pos-'parts. Then calculate the result for the complete expression.1) part2 = RIGHT$(expr, LEN(expr)-pos)RETURN Eval(part1) + Eval(part2) ENDIF'calculate the result and return the answer'there are no more operators left in the expression. so theRETURN VAL(expr) ENDSUB'expression must be a value. return the value of the expression

Copyright © 2006 SpeQ Mathematics