{"id":149,"date":"2009-02-04T15:32:25","date_gmt":"2009-02-04T13:32:25","guid":{"rendered":"http:\/\/mariusbancila.ro\/blog\/?p=149"},"modified":"2009-02-25T08:30:45","modified_gmt":"2009-02-25T06:30:45","slug":"evaluating-expressions-part-2-parse-the-expression","status":"publish","type":"post","link":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/","title":{"rendered":"Evaluating Expressions &#8211; Part 2: Parse the Expression"},"content":{"rendered":"<p>In my <a href=\"http:\/\/mariusbancila.ro\/blog\/?p=148\">previous post<\/a> 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&#8217;ll show you in this post.<\/p>\n<p>Having the grammar defined, we&#8217;ll make one function for each non-terminal symbol (EXP, EXP1, TERM, TERM1, FACTOR).<\/p>\n<p>Simply put the code will look like this:<\/p>\n<pre class=\"prettyprint\">\r\n   void Expression()\r\n   {\r\n      Term();\r\n      Expression1();\r\n   }\r\n\r\n   void Expression1()\r\n   {\r\n      switch(current_token)\r\n      {\r\n      case '+':\r\n         GetNextToken();\r\n         Term();\r\n         Expression1();\r\n         break;\r\n\r\n      case '-':\r\n         GetNextToken();\r\n         Term();\r\n         Expression1();\r\n         break;\r\n      }\r\n   }\r\n<\/pre>\n<p>However, I want to make it a little bit more organized, so the first thing to do will be defining a <tt>Token<\/tt> 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 (&#8216;+&#8217;, &#8216;-&#8216;, &#8216;\/&#8217;, &#8216;*&#8217;), the parentheses (&#8216;(&#8216; and &#8216;)&#8217;), numbers and the end of the text.<\/p>\n<p>Here is how I defined the token type and the token:<\/p>\n<pre class=\"prettyprint\">\r\nenum TokenType \r\n{\r\n   Error,\r\n   Plus,\r\n   Minus,\r\n   Mul,\r\n   Div,\r\n   EndOfText,\r\n   OpenParenthesis,\r\n   ClosedParenthesis,\r\n   Number\r\n};\r\n\r\nstruct Token \r\n{\r\n   TokenType\tType;\r\n   double\t\tValue;\r\n   char\t\tSymbol;\r\n\r\n   Token():Type(Error), Value(0), Symbol(0)\r\n   {}\r\n};\r\n<\/pre>\n<p>To be able to do the parsing, we&#8217;ll need some helper functions:<\/p>\n<ul>\n<li><b>SkipWhitespaces()<\/b>, skips all whitespaces between two tokens:\n<pre class=\"prettyprint\">\r\n   void SkipWhitespaces()\r\n   {\r\n      while(isspace(m_Text[m_Index])) m_Index++;\r\n   }\r\n<\/pre>\n<\/li>\n<li><b>GetNextToken()<\/b>, extracts the next token from the text; if an illegal token appears it throws an exception\n<pre class=\"prettyprint\">\r\n   void GetNextToken()\r\n   {\r\n      \/\/ ignore white spaces\r\n      SkipWhitespaces();\r\n\r\n      m_crtToken.Value = 0;\r\n      m_crtToken.Symbol = 0;\r\n\r\n      \/\/ test for the end of text\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 the current character is a digit read a number\r\n      if(isdigit(m_Text[m_Index]))\r\n      {\r\n         m_crtToken.Type = Number;\r\n         m_crtToken.Value = GetNumber();\r\n         return;\r\n      }\r\n\r\n      m_crtToken.Type = Error;\r\n\r\n      \/\/ check if the current character is an operator or parentheses\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      {\r\n         m_crtToken.Symbol = m_Text[m_Index];\r\n         m_Index++;\r\n      }\r\n      else\r\n      {\r\n         std::stringstream sstr; \r\n         sstr &lt;&lt; \"Unexpected token '\" &lt;&lt; m_Text[m_Index] &lt;&lt; \"' at position \" &lt;&lt; m_Index;\r\n         throw ParserException(sstr.str(), m_Index);\r\n      }\r\n   }\r\n<\/pre>\n<\/li>\n<li><b>GetNumber()<\/b> 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 &#8216;.&#8217; As the decimal point; it doesn&#8217;t read numbers in a format like 123.3E+2.\n<pre class=\"prettyprint\">\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<\/pre>\n<\/li>\n<\/ul>\n<p>With these defined, we can build the parser for the specified grammar.<\/p>\n<pre class=\"prettyprint\">\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   void Expression()\r\n   {\r\n      Term();\r\n      Expression1();\r\n   }\r\n\r\n   void Expression1()\r\n   {\r\n      switch(m_crtToken.Type)\r\n      {\r\n      case Plus:\r\n         GetNextToken();\r\n         Term();\r\n         Expression1();\r\n         break;\r\n\r\n      case Minus:\r\n         GetNextToken();\r\n         Term();\r\n         Expression1();\r\n         break;\r\n      }\r\n   }\r\n\r\n   void Term()\r\n   {\r\n      Factor();\r\n      Term1();\r\n   }\r\n\r\n   void Term1()\r\n   {\r\n      switch(m_crtToken.Type)\r\n      {\r\n      case Mul: \r\n         GetNextToken();\r\n         Factor();\r\n         Term1();\r\n         break;\r\n\r\n      case Div:\r\n         GetNextToken();\r\n         Factor();\r\n         Term1();\r\n         break;\r\n      }\r\n   }\r\n\r\n   void Factor()\r\n   {\r\n      switch(m_crtToken.Type)\r\n      {\r\n      case OpenParenthesis:\r\n         GetNextToken();\r\n         Expression();\r\n         Match(')');\r\n         break;\r\n\r\n      case Minus:\r\n         GetNextToken();\r\n         Factor();\r\n         break;\r\n\r\n      case Number:\r\n         GetNextToken();\r\n         break;\r\n\r\n      default:\r\n         {\r\n            std::stringstream sstr; \r\n            sstr &lt;&lt; \"Unexpected token '\" &lt;&lt; m_crtToken.Symbol &lt;&lt; \"' at position \" &lt;&lt; m_Index;\r\n            throw ParserException(sstr.str(), m_Index);\r\n         }\r\n      }\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 &lt;&lt; \"Expected token '\" &lt;&lt; expected &lt;&lt; \"' at position \" &lt;&lt; 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      \/\/ ignore white spaces\r\n      SkipWhitespaces();\r\n\r\n      m_crtToken.Value = 0;\r\n      m_crtToken.Symbol = 0;\r\n\r\n      \/\/ test for the end of text\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 the current character is a digit read a number\r\n      if(isdigit(m_Text[m_Index]))\r\n      {\r\n         m_crtToken.Type = Number;\r\n         m_crtToken.Value = GetNumber();\r\n         return;\r\n      }\r\n\r\n      m_crtToken.Type = Error;\r\n\r\n      \/\/ check if the current character is an operator or parentheses\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      {\r\n         m_crtToken.Symbol = m_Text[m_Index];\r\n         m_Index++;\r\n      }\r\n      else\r\n      {\r\n         std::stringstream sstr; \r\n         sstr &lt;&lt; \"Unexpected token '\" &lt;&lt; m_Text[m_Index] &lt;&lt; \"' at position \" &lt;&lt; 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, &amp;m_Text[index], m_Index - index);\r\n\r\n      return atof(buffer);\r\n   }\r\n\r\npublic:\r\n   void Parse(const char* text)\r\n   {\r\n      m_Text = text;\r\n      m_Index = 0;\r\n      GetNextToken();\r\n\r\n      Expression();\r\n   }\r\n};\r\n<\/pre>\n<p>The exception class is defined like this:<\/p>\n<pre class=\"prettyprint\">\r\nclass ParserException : public std::exception\r\n{\r\n   int m_Pos;\r\n\r\npublic:\r\n   ParserException(const std::string&amp; message, int pos):\r\n      std::exception(message.c_str()),\r\n      m_Pos(pos)\r\n   {\r\n   }\r\n};\r\n<\/pre>\n<p>As you can see, the code for the grammar production is quite simple and straight forward. Now, let&#8217;s put it to the test.<\/p>\n<pre class=\"prettyprint\">\r\nvoid Test(const char* text)\r\n{\r\n   Parser parser;\r\n   try \r\n   {\r\n      parser.Parse(text);\r\n      std::cout &lt;&lt; \"\"\" &lt;&lt; text &lt;&lt; \"\"t OK\" &lt;&lt; std::endl;\r\n   }\r\n   catch(ParserException&amp; ex)\r\n   {\r\n      std::cout &lt;&lt; \"\"\" &lt;&lt; text &lt;&lt; \"\"t \" &lt;&lt; ex.what() &lt;&lt; std::endl;\r\n   }\t\r\n}\r\n\r\nint main()\r\n{\r\n   Test(\"1+2+3+4\");\r\n   Test(\"1*2*3*4\");\r\n   Test(\"1-2-3-4\");\r\n   Test(\"1\/2\/3\/4\");\r\n   Test(\"1*2+3*4\");\r\n   Test(\"1+2*3+4\");\r\n   Test(\"(1+2)*(3+4)\");\r\n   Test(\"1+(2*3)*(4+5)\");\r\n   Test(\"1+(2*3)\/4+5\");\r\n   Test(\"5\/(4+3)\/2\");\r\n   Test(\"1 + 2.5\");\r\n   Test(\"125\");\r\n   Test(\"-1\");\r\n   Test(\"-1+(-2)\");\r\n   Test(\"-1+(-2.0)\");\r\n\r\n   Test(\"   1*2,5\");\r\n   Test(\"   1*2.5e2\");\r\n   Test(\"M1 + 2.5\");\r\n   Test(\"1 + 2&amp;5\");\r\n   Test(\"1 * 2.5.6\");\r\n   Test(\"1 ** 2.5\");\r\n   Test(\"*1 \/ 2.5\");\r\n\r\n   return 0;\r\n}\r\n<\/pre>\n<p>The output for this testing program is:<\/p>\n<pre class=\"prettyprint\">\r\n\"1+2+3+4\"        OK\r\n\"1*2*3*4\"        OK\r\n\"1-2-3-4\"        OK\r\n\"1\/2\/3\/4\"        OK\r\n\"1*2+3*4\"        OK\r\n\"1+2*3+4\"        OK\r\n\"(1+2)*(3+4)\"    OK\r\n\"1+(2*3)*(4+5)\"  OK\r\n\"1+(2*3)\/4+5\"    OK\r\n\"5\/(4+3)\/2\"      OK\r\n\"1 + 2.5\"        OK\r\n\"125\"    OK\r\n\"-1\"     OK\r\n\"-1+(-2)\"        OK\r\n\"-1+(-2.0)\"      OK\r\n\"   1*2,5\"       Unexpected token ',' at position 6\r\n\"   1*2.5e2\"     Unexpected token 'e' at position 8\r\n\"M1 + 2.5\"       Unexpected token 'M' at position 0\r\n\"1 + 2&amp;5\"        Unexpected token '&amp;' at position 5\r\n\"1 * 2.5.6\"      Unexpected token '.' at position 7\r\n\"1 ** 2.5\"       Unexpected token '*' at position 4\r\n\"*1 \/ 2.5\"       Unexpected token '*' at position 1\r\n<\/pre>\n<p>Which is exactly what we expected: it validates correct expressions and throws an exception when the exception is incorrect.<\/p>\n<p>In the next post I&#8217;ll show how to modify this code to build an abstract syntax tree.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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&#8217;ll show you in this post. Having the grammar defined, we&#8217;ll make one function &#8230; <a title=\"Evaluating Expressions &#8211; Part 2: Parse the Expression\" class=\"read-more\" href=\"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/\" aria-label=\"Read more about Evaluating Expressions &#8211; Part 2: Parse the Expression\">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,11,7],"tags":[60,58,451,61,64,59,63,62],"class_list":["post-149","post","type-post","status-publish","format-standard","hentry","category-articles_and_tutorials","category-csharp","category-c","tag-analyzer","tag-ast","tag-c","tag-expression","tag-factor","tag-parser","tag-term","tag-tree"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.1.1 - aioseo.com -->\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Marius Bancila\"\/>\n\t<meta name=\"keywords\" content=\"analyzer,ast,c++,expression,factor,parser,term,tree\" \/>\n\t<link rel=\"canonical\" href=\"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/\" \/>\n\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.1.1\" \/>\n\t\t<meta property=\"og:locale\" content=\"en_US\" \/>\n\t\t<meta property=\"og:site_name\" content=\"Marius Bancila&#039;s Blog | About code. Mostly on C++\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"Evaluating Expressions \u2013 Part 2: Parse the Expression\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2009-02-04T13:32:25+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2009-02-25T06:30:45+00:00\" \/>\n\t\t<meta name=\"twitter:card\" content=\"summary\" \/>\n\t\t<meta name=\"twitter:title\" content=\"Evaluating Expressions \u2013 Part 2: Parse the Expression\" \/>\n\t\t<script type=\"application\/ld+json\" class=\"aioseo-schema\">\n\t\t\t{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2009\\\/02\\\/04\\\/evaluating-expressions-part-2-parse-the-expression\\\/#article\",\"name\":\"Evaluating Expressions \\u2013 Part 2: Parse the Expression\",\"headline\":\"Evaluating Expressions &#8211; Part 2: Parse the Expression\",\"author\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"publisher\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\"},\"datePublished\":\"2009-02-04T15:32:25+02:00\",\"dateModified\":\"2009-02-25T08:30:45+02:00\",\"inLanguage\":\"en-US\",\"commentCount\":1,\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2009\\\/02\\\/04\\\/evaluating-expressions-part-2-parse-the-expression\\\/#webpage\"},\"isPartOf\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2009\\\/02\\\/04\\\/evaluating-expressions-part-2-parse-the-expression\\\/#webpage\"},\"articleSection\":\"Articles &amp; Tutorials, C#, C++, analyzer, AST, C++, expression, factor, parser, term, tree\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2009\\\/02\\\/04\\\/evaluating-expressions-part-2-parse-the-expression\\\/#breadcrumblist\",\"itemListElement\":[{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog#listItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"name\":\"IT\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"position\":2,\"name\":\"IT\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"name\":\"Software\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog#listItem\",\"name\":\"Home\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"position\":3,\"name\":\"Software\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/net\\\/#listItem\",\"name\":\".NET\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"name\":\"IT\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/net\\\/#listItem\",\"position\":4,\"name\":\".NET\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/net\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/net\\\/csharp\\\/#listItem\",\"name\":\"C#\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"name\":\"Software\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/net\\\/csharp\\\/#listItem\",\"position\":5,\"name\":\"C#\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/net\\\/csharp\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2009\\\/02\\\/04\\\/evaluating-expressions-part-2-parse-the-expression\\\/#listItem\",\"name\":\"Evaluating Expressions &#8211; Part 2: Parse the Expression\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/net\\\/#listItem\",\"name\":\".NET\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2009\\\/02\\\/04\\\/evaluating-expressions-part-2-parse-the-expression\\\/#listItem\",\"position\":6,\"name\":\"Evaluating Expressions &#8211; Part 2: Parse the Expression\",\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/net\\\/csharp\\\/#listItem\",\"name\":\"C#\"}}]},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\",\"name\":\"Marius Bancila's Blog\",\"description\":\"About code. Mostly on C++\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/\",\"name\":\"Marius Bancila\",\"image\":{\"@type\":\"ImageObject\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2009\\\/02\\\/04\\\/evaluating-expressions-part-2-parse-the-expression\\\/#authorImage\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/a84dd2831d955c38355ddea55df4df260809b88f36408bc14fd4eab8f7f131c9?s=96&d=mm&r=g\",\"width\":96,\"height\":96,\"caption\":\"Marius Bancila\"}},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2009\\\/02\\\/04\\\/evaluating-expressions-part-2-parse-the-expression\\\/#webpage\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2009\\\/02\\\/04\\\/evaluating-expressions-part-2-parse-the-expression\\\/\",\"name\":\"Evaluating Expressions \\u2013 Part 2: Parse the Expression\",\"inLanguage\":\"en-US\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#website\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2009\\\/02\\\/04\\\/evaluating-expressions-part-2-parse-the-expression\\\/#breadcrumblist\"},\"author\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"creator\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"datePublished\":\"2009-02-04T15:32:25+02:00\",\"dateModified\":\"2009-02-25T08:30:45+02:00\"},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\",\"name\":\"Marius Bancila's Blog\",\"description\":\"About code. Mostly on C++\",\"inLanguage\":\"en-US\",\"publisher\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\"}}]}\n\t\t<\/script>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"Evaluating Expressions \u2013 Part 2: Parse the Expression","description":"","canonical_url":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/","robots":"max-image-preview:large","keywords":"analyzer,ast,c++,expression,factor,parser,term,tree","webmasterTools":{"miscellaneous":""},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/#article","name":"Evaluating Expressions \u2013 Part 2: Parse the Expression","headline":"Evaluating Expressions &#8211; Part 2: Parse the Expression","author":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"publisher":{"@id":"https:\/\/mariusbancila.ro\/blog\/#organization"},"datePublished":"2009-02-04T15:32:25+02:00","dateModified":"2009-02-25T08:30:45+02:00","inLanguage":"en-US","commentCount":1,"mainEntityOfPage":{"@id":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/#webpage"},"isPartOf":{"@id":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/#webpage"},"articleSection":"Articles &amp; Tutorials, C#, C++, analyzer, AST, C++, expression, factor, parser, term, tree"},{"@type":"BreadcrumbList","@id":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/#breadcrumblist","itemListElement":[{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog#listItem","position":1,"name":"Home","item":"https:\/\/mariusbancila.ro\/blog","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","name":"IT"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","position":2,"name":"IT","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","name":"Software"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog#listItem","name":"Home"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","position":3,"name":"Software","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/net\/#listItem","name":".NET"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","name":"IT"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/net\/#listItem","position":4,"name":".NET","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/net\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/net\/csharp\/#listItem","name":"C#"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","name":"Software"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/net\/csharp\/#listItem","position":5,"name":"C#","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/net\/csharp\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/#listItem","name":"Evaluating Expressions &#8211; Part 2: Parse the Expression"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/net\/#listItem","name":".NET"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/#listItem","position":6,"name":"Evaluating Expressions &#8211; Part 2: Parse the Expression","previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/net\/csharp\/#listItem","name":"C#"}}]},{"@type":"Organization","@id":"https:\/\/mariusbancila.ro\/blog\/#organization","name":"Marius Bancila's Blog","description":"About code. Mostly on C++","url":"https:\/\/mariusbancila.ro\/blog\/"},{"@type":"Person","@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author","url":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/","name":"Marius Bancila","image":{"@type":"ImageObject","@id":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/#authorImage","url":"https:\/\/secure.gravatar.com\/avatar\/a84dd2831d955c38355ddea55df4df260809b88f36408bc14fd4eab8f7f131c9?s=96&d=mm&r=g","width":96,"height":96,"caption":"Marius Bancila"}},{"@type":"WebPage","@id":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/#webpage","url":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/","name":"Evaluating Expressions \u2013 Part 2: Parse the Expression","inLanguage":"en-US","isPartOf":{"@id":"https:\/\/mariusbancila.ro\/blog\/#website"},"breadcrumb":{"@id":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/#breadcrumblist"},"author":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"creator":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"datePublished":"2009-02-04T15:32:25+02:00","dateModified":"2009-02-25T08:30:45+02:00"},{"@type":"WebSite","@id":"https:\/\/mariusbancila.ro\/blog\/#website","url":"https:\/\/mariusbancila.ro\/blog\/","name":"Marius Bancila's Blog","description":"About code. Mostly on C++","inLanguage":"en-US","publisher":{"@id":"https:\/\/mariusbancila.ro\/blog\/#organization"}}]},"og:locale":"en_US","og:site_name":"Marius Bancila's Blog | About code. Mostly on C++","og:type":"article","og:title":"Evaluating Expressions \u2013 Part 2: Parse the Expression","og:url":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/04\/evaluating-expressions-part-2-parse-the-expression\/","article:published_time":"2009-02-04T13:32:25+00:00","article:modified_time":"2009-02-25T06:30:45+00:00","twitter:card":"summary","twitter:title":"Evaluating Expressions \u2013 Part 2: Parse the Expression"},"aioseo_meta_data":{"post_id":"149","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"Article","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"ai":null,"created":"2021-03-18 21:16:02","updated":"2025-12-12 07:24:40","seo_analyzer_scan_date":null,"focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"author_meta":{"display_name":"Marius Bancila","author_link":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/"},"featured_img":null,"jetpack_publicize_connections":[],"uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false},"uagb_author_info":{"display_name":"Marius Bancila","author_link":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/"},"uagb_comment_info":1,"uagb_excerpt":"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&#8217;ll show you in this post. Having the grammar defined, we&#8217;ll make one function&hellip;","coauthors":[],"tax_additional":{"categories":{"linked":["<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/articles_and_tutorials\/\" class=\"advgb-post-tax-term\">Articles &amp; Tutorials<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/net\/csharp\/\" class=\"advgb-post-tax-term\">C#<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">C++<\/a>"],"unlinked":["<span class=\"advgb-post-tax-term\">Articles &amp; Tutorials<\/span>","<span class=\"advgb-post-tax-term\">C#<\/span>","<span class=\"advgb-post-tax-term\">C++<\/span>"]},"tags":{"linked":["<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">analyzer<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">AST<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">C++<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">expression<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">factor<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">parser<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">term<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">tree<\/a>"],"unlinked":["<span class=\"advgb-post-tax-term\">analyzer<\/span>","<span class=\"advgb-post-tax-term\">AST<\/span>","<span class=\"advgb-post-tax-term\">C++<\/span>","<span class=\"advgb-post-tax-term\">expression<\/span>","<span class=\"advgb-post-tax-term\">factor<\/span>","<span class=\"advgb-post-tax-term\">parser<\/span>","<span class=\"advgb-post-tax-term\">term<\/span>","<span class=\"advgb-post-tax-term\">tree<\/span>"]}},"comment_count":"1","relative_dates":{"created":"Posted 18 years ago","modified":"Updated 18 years ago"},"absolute_dates":{"created":"Posted on February 4, 2009","modified":"Updated on February 25, 2009"},"absolute_dates_time":{"created":"Posted on February 4, 2009 3:32 pm","modified":"Updated on February 25, 2009 8:30 am"},"featured_img_caption":"","series_order":"","jetpack_shortlink":"https:\/\/wp.me\/pYNdv-2p","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/149","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/comments?post=149"}],"version-history":[{"count":1,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/149\/revisions"}],"predecessor-version":[{"id":193,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/149\/revisions\/193"}],"wp:attachment":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/media?parent=149"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/categories?post=149"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/tags?post=149"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}