title: How do I parse basic arithmetic (eg "5+5") using a simple recursive descent parser in C++?
body: <p>This has been on my mind for a while. I'm intrigued by recursive descent parsers, and would like to know how to implement one. What I want is a simple parser that will understand simple arithmetic such as "5+5", or "(5+5)*3".</p>
  
  <p>I figure the first step is to write a 'tokenizer', which takes the entire input string and breaks it into many substrings. This part I have done (I've even had to ask about it <a href="https://stackoverflow.com/questions/10358598/why-is-this-function-not-breaking-up-this-input-string">here</a>. You don't have to follow the link if you don't want to, since I'm posting the relavent code here as well.) With this tokenizer of mine, I end up with a <code>vector</code> of <code>string</code>s, or tokens. Now, the hard part: I'd like to parse those tokens.</p>
  
  <p>I've read the <a href="http://en.wikipedia.org/wiki/Recursive_descent_parser" rel="nofollow noreferrer">Wikipedia article on recursive descent parsers</a>. I do understand the overall concept, but as always, the implementation is a bit confusing. In that article, there is a C implementation of a recursive descent parser for a very simple programming language, also discussed in the article. I studied that code as best I could, and tried to basically write the same thing, but for my program. Below is that code.</p>
  
  <p>What I am really confused about is what this parser does. It seems to go through the program and 'expect' certain parts of the grammar. But once it gets there, what does it do? For example, here is one function from the Wikipedia code that is supposed to parse a 'term':</p>
  
  <pre><code>void term(void) {
      factor();
      while (sym == times || sym == slash) {
          getsym();
          factor();
      }
  }
  </code></pre>
  
  <p>This is meant to parse this grammar:</p>
  
  <pre><code>term = factor {("*"|"/") factor} .
  </code></pre>
  
  <p>which makes sense. But what does it do with the actual term? Let's say that term is simply "6", or was "3*2" and came out to be of value 6. How would it incorporate that into the rest of the input? Shouldn't <code>term()</code> return a <code>double</code> instead of <code>void</code> (to return the 6)? Or is it done some other way?</p>
  
  <p>Also, what would be the difference between getting a parser like this to output code, and to immediately act upon the input (ie compiler vs. interpreter)? Are those two (in this example at least) theoretically implemented the same way, or are they fundamentally different?</p>
  
  <p>Any input is welcome. Here is my code thus far:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;string&gt;
  #include &lt;vector&gt;
  #include &lt;ctype.h&gt;
  #include &lt;sstream&gt;
  
  using namespace std;
  
  vector&lt;string&gt; symbolize(string);
  bool accept(string);
  void getSymbol();
  void error(string s);
  bool expect(string);
  void expression();
  void term();
  void factor();
  
  int currentPosition = -1;
  string symbol;
  vector&lt;string&gt; symbols;
  
  int main(int argc, const char * argv[])
  {
  
      string input;
      getline(cin,input);
  
      symbols = symbolize(input);
      getSymbol();
      expression();
  
  
      return 0;
  }
  
  void factor(){
      if(isdigit(symbol.c_str()[0])){}
      else if(accept("(")){
          expression();
          expect(")");
      }
      else {
          error("Syntax error");
      }
  
  }
  
  void term(){
      factor();
      while(symbol=="*"||symbol=="/"){
          getSymbol();
          factor();
      }
  }
  
  void expression(){
      if(symbol == "+" || symbol == "-") getSymbol();
      term();
      while(symbol == "+" || symbol == "-"){
          getSymbol();
          term();
      }
  }
  
  void error(string s){
      cout &lt;&lt; endl &lt;&lt; "ERROR: " &lt;&lt; s &lt;&lt; endl;
  }
  
  void getSymbol(){
      currentPosition++;
      if(currentPosition&gt;=symbols.size())error("Unexpectedly reached end of input");
  
  }
  
  bool expect(string s){
      if(accept(s))return true;
      else error("Expected '" + s + "'");
      return false;
  }
  
  bool accept(string s){
      if(s==symbol){getSymbol();return true;}
      return false;
  }
  
  // Takes a string and breaks it into substrings
  vector&lt;string&gt; symbolize(string input){
      int position = 0;
      char c;
      //stringstream s;
      vector&lt;string&gt; symbols;
      enum symbolType {TEXT,OPERATOR}symbolType,charType;
  
      while(position &lt; input.size()){
          stringstream s;
          c = input.at(position);
          if(isalnum(c))symbolType = TEXT;
          else symbolType = OPERATOR;
          charType = symbolType;
  
          while(symbolType == charType){
              s &lt;&lt; c;
              position++;
              if(position&gt;=input.length())break;
              c = input.at(position);
              if(isspace(c)||c=='\n'){position++; break;}
              if(isalnum(c)) charType = TEXT;
              else charType = OPERATOR;
          }
  
          symbols.push_back(s.str());
      }
  
      return symbols;
  }
  </code></pre>
  
  <p><strong>Edit:</strong> I should mention that my code <em>always</em> prints: <code>ERROR: syntax error</code>, from the <code>factor()</code> function.</p>