{"id":150,"date":"2009-02-05T08:00:14","date_gmt":"2009-02-05T06:00:14","guid":{"rendered":"http:\/\/mariusbancila.ro\/blog\/?p=150"},"modified":"2009-02-25T08:30:35","modified_gmt":"2009-02-25T06:30:35","slug":"evaluating-expressions-part-3-building-the-ast","status":"publish","type":"post","link":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/05\/evaluating-expressions-part-3-building-the-ast\/","title":{"rendered":"Evaluating Expressions – Part 3: Building the AST"},"content":{"rendered":"

In my previous post<\/a> we’ve parsed an exception verifying whether it’s correct or not syntactically. But we still have to evaluate it. To be able to do that we’ll have to build an abstract syntax tree. This can be done by modifying the previous code and inserting semantic action. That means we do something more when we match productions.<\/p>\n

An abstract syntax tree is a binary tree. The inner nodes will represent operators and leafs will be numerical values.<\/p>\n

Here is how a node in the AST will look:<\/p>\n

\"AST<\/p>\n

It is defined like this:<\/p>\n

\r\nenum ASTNodeType \r\n{\r\n   Undefined,\r\n   OperatorPlus,\r\n   OperatorMinus,\r\n   OperatorMul,\r\n   OperatorDiv,\r\n   UnaryMinus,\r\n   NumberValue\r\n};\r\n\r\nclass ASTNode\r\n{\r\npublic:\r\n   ASTNodeType Type;\r\n   double      Value;\r\n   ASTNode*    Left;\r\n   ASTNode*    Right;\r\n\r\n   ASTNode()\r\n   {\r\n      Type = Undefined;\r\n      Value = 0;\r\n      Left = NULL;\r\n      Right = NULL;\r\n   }\r\n\r\n   ~ASTNode()\r\n   {\r\n      delete Left;\r\n      delete Right;\r\n   }\r\n};\r\n<\/pre>\n
For the expression 1+2*3, the AST will be:<\/p>\n
\"AST<\/p>\n
We’ll build this tree by inserting semantic actions and adding nodes according to the following rules:<\/p>\n
\"AST<\/p>\n
You’ll probably notice that based on these rules the AST shown above will be modified a little bit, with some additional nodes for operators + and *, having on the left a leaf node with the neutral element for the operation (zero for + and 1 for *), and on the right a node corresponding to a TERM or FACTOR. This won’t affect the evaluation.<\/p>\n
The Parser class will change so that the functions corresponding to the non-terminal symbols EXP, EXP1, TERM, TERM1 and FACTOR will return an ASTNode* instead of void. That is the node created as a semantic action.<\/p>\n
\r\nclass Parser\r\n{\r\n   Token m_crtToken;\r\n   const char* m_Text;\r\n   size_t m_Index;\r\n\r\nprivate:\r\n\r\n   ASTNode* Expression()\r\n   {\r\n      ASTNode* tnode = Term();\r\n      ASTNode* e1node = Expression1();\r\n\r\n      return CreateNode(OperatorPlus, tnode, e1node);\r\n   }\r\n\r\n   ASTNode* Expression1()\r\n   {\r\n      ASTNode* tnode;\r\n      ASTNode* e1node;\r\n\r\n      switch(m_crtToken.Type)\r\n      {\r\n      case Plus:\r\n         GetNextToken();\r\n         tnode = Term();\r\n         e1node = Expression1();\r\n\r\n         return CreateNode(OperatorPlus, e1node, tnode);\r\n\r\n      case Minus:\r\n         GetNextToken();\r\n         tnode = Term();\r\n         e1node = Expression1();\r\n\r\n         return CreateNode(OperatorMinus, e1node, tnode);\r\n      }\r\n\r\n      return CreateNodeNumber(0);\r\n   }\r\n\r\n   ASTNode* Term()\r\n   {\r\n      ASTNode* fnode = Factor();\r\n      ASTNode* t1node = Term1();\r\n\r\n      return CreateNode(OperatorMul, fnode, t1node);\r\n   }\r\n\r\n   ASTNode* Term1()\r\n   {\r\n      ASTNode* fnode;\r\n      ASTNode* t1node;\r\n\r\n      switch(m_crtToken.Type)\r\n      {\r\n      case Mul: \r\n         GetNextToken();\r\n         fnode = Factor();\r\n         t1node = Term1();\r\n         return CreateNode(OperatorMul, t1node, fnode);\r\n\r\n      case Div:\r\n         GetNextToken();\r\n         fnode = Factor();\r\n         t1node = Term1();\r\n         return CreateNode(OperatorDiv, t1node, fnode);\r\n      }\r\n\r\n      return CreateNodeNumber(1);\r\n   }\r\n\r\n   ASTNode* Factor()\r\n   {\r\n      ASTNode* node;\r\n      switch(m_crtToken.Type)\r\n      {\r\n      case OpenParenthesis:\r\n         GetNextToken();\r\n         node = Expression();\r\n         Match(')');\r\n         return node;\r\n\r\n      case Minus:\r\n         GetNextToken();\r\n\t\t node = Factor();\r\n         return CreateUnaryNode(node);\r\n\r\n      case Number:\r\n         {\r\n            double value = m_crtToken.Value;\r\n            GetNextToken();\r\n            return CreateNodeNumber(value);\r\n         }\r\n\r\n      default:\r\n         {\r\n            std::stringstream sstr; \r\n            sstr << \"Unexpected token '\" << m_crtToken.Symbol << \"' at position \" << m_Index;\r\n            throw ParserException(sstr.str(), m_Index);\r\n         }\r\n      }\r\n   }\r\n\r\n   ASTNode* CreateNode(ASTNodeType type, ASTNode* left, ASTNode* right)\r\n   {\r\n      ASTNode* node = new ASTNode;\r\n      node->Type = type;\r\n      node->Left = left;\r\n      node->Right = right;\r\n\r\n      return node;\r\n   }\r\n\r\n   ASTNode* CreateUnaryNode(ASTNode* left)\r\n   {\r\n      ASTNode* node = new ASTNode;\r\n      node->Type = UnaryMinus;\r\n      node->Left = left;\r\n      node->Right = NULL;\r\n\r\n      return node;\r\n   }\r\n\r\n   ASTNode* CreateNodeNumber(double value)\r\n   {\r\n      ASTNode* node = new ASTNode;\r\n      node->Type = NumberValue;\r\n      node->Value = value;\r\n\r\n      return node;\r\n   }\r\n\r\n   void Match(char expected)\r\n   {\r\n      if(m_Text[m_Index-1] == expected)\r\n         GetNextToken();\r\n      else\r\n      {\r\n         std::stringstream sstr;\r\n         sstr << \"Expected token '\" << expected << \"' at position \" << m_Index;\r\n         throw ParserException(sstr.str(), m_Index);\r\n      }\r\n   }\r\n\r\n   void SkipWhitespaces()\r\n   {\r\n      while(isspace(m_Text[m_Index])) m_Index++;\r\n   }\r\n\r\n   void GetNextToken()\r\n   {\r\n      SkipWhitespaces();\r\n\r\n\t  m_crtToken.Value = 0;\r\n\t  m_crtToken.Symbol = 0;\r\n\r\n      if(m_Text[m_Index] == 0)\r\n      {\r\n         m_crtToken.Type = EndOfText;\r\n         return;\r\n      }\r\n\r\n      if(isdigit(m_Text[m_Index]))\r\n      {\r\n         m_crtToken.Type = Number;\r\n\t\t m_crtToken.Value = GetNumber();\r\n         return;\r\n      }\r\n\r\n      m_crtToken.Type = Error;\r\n\r\n      switch(m_Text[m_Index])\r\n      {\r\n      case '+': m_crtToken.Type = Plus; break;\r\n      case '-': m_crtToken.Type = Minus; break;\r\n      case '*': m_crtToken.Type = Mul; break;\r\n      case '\/': m_crtToken.Type = Div; break;\r\n      case '(': m_crtToken.Type = OpenParenthesis; break;\r\n      case ')': m_crtToken.Type = ClosedParenthesis; break;\r\n      }\r\n\r\n      if(m_crtToken.Type != Error)\r\n\t  {\r\n         m_crtToken.Symbol = m_Text[m_Index];\r\n         m_Index++;\r\n\t  }\r\n      else\r\n      {\r\n         std::stringstream sstr; \r\n         sstr << \"Unexpected token '\" << m_Text[m_Index] << \"' at position \" << m_Index;\r\n         throw ParserException(sstr.str(), m_Index);\r\n      }\r\n   }\r\n\r\n   double GetNumber()\r\n   {\r\n      SkipWhitespaces();\r\n\r\n      int index = m_Index;\r\n      while(isdigit(m_Text[m_Index])) m_Index++;\r\n      if(m_Text[m_Index] == '.') m_Index++;\r\n      while(isdigit(m_Text[m_Index])) m_Index++;\r\n\r\n      if(m_Index - index == 0)\r\n         throw ParserException(\"Number expected but not found!\", m_Index);\r\n\r\n      char buffer[32] = {0};\r\n      memcpy(buffer, &m_Text[index], m_Index - index);\r\n\r\n      return atof(buffer);\r\n   }\r\n\r\npublic:\r\n   ASTNode* Parse(const char* text)\r\n   {\r\n      m_Text = text;\r\n      m_Index = 0;\r\n      GetNextToken();\r\n\r\n      return Expression();\r\n   }\r\n};\r\n<\/pre>\n
Now the Parse() method will return the created abstract syntax tree. We will see how to evaluate the expression by traversing this tree in the next post.<\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
In my previous post we’ve parsed an exception verifying whether it’s correct or not syntactically. But we still have to evaluate it. To be able to do that we’ll have to build an abstract syntax tree. This can be done by modifying the previous code and inserting semantic action. That means we do something more … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[9,7],"tags":[58,451,61,59,62],"class_list":["post-150","post","type-post","status-publish","format-standard","hentry","category-articles_and_tutorials","category-c","tag-ast","tag-c","tag-expression","tag-parser","tag-tree"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t