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:
  
  void SkipWhitespaces() { while(isspace(m_Text[m_Index])) m_Index++; }

  1 2 3 4

  void SkipWhitespaces()    {       while(isspace(m_Text[m_Index])) m_Index++;    }

• GetNextToken(), extracts the next token from the text; if an illegal token appears it throws an exception
  
  void GetNextToken() { // ignore white spaces SkipWhitespaces(); m_crtToken.Value = 0; m_crtToken.Symbol = 0; // test for the end of text if(m_Text[m_Index] == 0) { m_crtToken.Type = EndOfText; return; } // if the current character is a digit read a number if(isdigit(m_Text[m_Index])) { m_crtToken.Type = Number; m_crtToken.Value = GetNumber(); return; } m_crtToken.Type = Error; // check if the current character is an operator or parentheses switch(m_Text[m_Index]) { case '+': m_crtToken.Type = Plus; break; case '-': m_crtToken.Type = Minus; break; case '*': m_crtToken.Type = Mul; break; case '/': m_crtToken.Type = Div; break; case '(': m_crtToken.Type = OpenParenthesis; break; case ')': m_crtToken.Type = ClosedParenthesis; break; } if(m_crtToken.Type != Error) { m_crtToken.Symbol = m_Text[m_Index]; m_Index++; } else { std::stringstream sstr; sstr << "Unexpected token '" << m_Text[m_Index] << "' at position " << m_Index; throw ParserException(sstr.str(), m_Index); } }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

  void GetNextToken()    {       // ignore white spaces       SkipWhitespaces();         m_crtToken.Value = 0;       m_crtToken.Symbol = 0;         // test for the end of text       if(m_Text[m_Index] == 0)       {          m_crtToken.Type = EndOfText;          return;       }         // if the current character is a digit read a number       if(isdigit(m_Text[m_Index]))       {          m_crtToken.Type = Number;          m_crtToken.Value = GetNumber();          return;       }         m_crtToken.Type = Error;         // check if the current character is an operator or parentheses       switch(m_Text[m_Index])       {       case '+': m_crtToken.Type = Plus; break;       case '-': m_crtToken.Type = Minus; break;       case '*': m_crtToken.Type = Mul; break;       case '/': m_crtToken.Type = Div; break;       case '(': m_crtToken.Type = OpenParenthesis; break;       case ')': m_crtToken.Type = ClosedParenthesis; break;       }         if(m_crtToken.Type != Error)       {          m_crtToken.Symbol = m_Text[m_Index];          m_Index++;       }       else       {          std::stringstream sstr;          sstr << "Unexpected token '" << m_Text[m_Index] << "' at position " << m_Index;          throw ParserException(sstr.str(), m_Index);       }    }

• 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.
  
  double GetNumber() { SkipWhitespaces(); int index = m_Index; while(isdigit(m_Text[m_Index])) m_Index++; if(m_Text[m_Index] == '.') m_Index++; while(isdigit(m_Text[m_Index])) m_Index++; if(m_Index - index == 0) throw ParserException("Number expected but not found!", m_Index); char buffer[32] = {0}; memcpy(buffer, &m_Text[index], m_Index - index); return atof(buffer); }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  double GetNumber()    {       SkipWhitespaces();         int index = m_Index;       while(isdigit(m_Text[m_Index])) m_Index++;       if(m_Text[m_Index] == '.') m_Index++;       while(isdigit(m_Text[m_Index])) m_Index++;         if(m_Index - index == 0)          throw ParserException("Number expected but not found!", m_Index);         char buffer[32] = {0};       memcpy(buffer, &m_Text[index], m_Index - index);         return atof(buffer);    }

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.