Evaluating Expressions – Part 2: Parse the Expression

In my previous post I have provided some background theory for evaluating expressions with abstract syntax trees. As I was mentioning, the first step towards this goal is to parse the expression, make sure it is correct syntactically. This is what I’ll show you in this post.

Having the grammar defined, we’ll make one function for each non-terminal symbol (EXP, EXP1, TERM, TERM1, FACTOR).

Simply put the code will look like this:

However, I want to make it a little bit more organized, so the first thing to do will be defining a Token structure that will indicate the type of last extracted token and if the case its value (for numbers). A token is basically a symbol extracted (one at a time) from the input text. The possible tokens will be the arithmetical operators (‘+’, ‘-‘, ‘/’, ‘*’), the parentheses (‘(‘ and ‘)’), numbers and the end of the text.

Here is how I defined the token type and the token:

To be able to do the parsing, we’ll need some helper functions:

  • SkipWhitespaces(), skips all whitespaces between two tokens:
  • GetNextToken(), extracts the next token from the text; if an illegal token appears it throws an exception
  • GetNumber() extracts a number from the input text from the current position; the purpose of this tutorial is didactical, so this function is quite simple: it reads integers and doubles with ‘.’ As the decimal point; it doesn’t read numbers in a format like 123.3E+2.

With these defined, we can build the parser for the specified grammar.

The exception class is defined like this:

As you can see, the code for the grammar production is quite simple and straight forward. Now, let’s put it to the test.

The output for this testing program is:

Which is exactly what we expected: it validates correct expressions and throws an exception when the exception is incorrect.

In the next post I’ll show how to modify this code to build an abstract syntax tree.

1 Reply to “Evaluating Expressions – Part 2: Parse the Expression”

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.