title: Recursive Descent Parser and Nested Parentheses
body: <p>I'm new to the area of grammars and parsing.</p>
  
  <p>I'm trying to write a recursive descent parser that evaluates strings like this:</p>
  
  <p>((3 == 5 AND 4 == 5) OR (6 == 6 ))</p>
  
  <p>Everything works fine for me until I start to deal with nested parentheses.  Essentially I find that I'm reaching the end of my target string too early.</p>
  
  <p>I think the problem is due to the fact when I encounter a token like the "6" or the second-to-last parenthesis, I evaluate it and then move to the next token.  I'd remove the code for advancing to the next token, but then I'm not sure how I move forward.   </p>
  
  <p>My grammar, such as it is, looks like this (the "=>" signs are my own notation for the "translation" of a rule):</p>
  
  <p>Test: If CompoundSentence Then CompoundSentence | CompoundSentence</p>
  
  <p>CompoundSentence :   ( CompoundSentence ) PCSopt |CompoundSentence Conjunction Sentence | </p>
  
  <p>Sentence =></p>
  
  <p>CompoundSentence = ( CompoundSentence ) PCSopt  | Sentence CSOpt</p>
  
  <p>PCSOpt = ParenConjunction CompoundSentence PCSOpt| Epsilon</p>
  
  <p>CSOpt = Conjunction Sentence CSOpt| Epsilon</p>
  
  <p>ParenConjunction:  And|Or</p>
  
  <p>Conjunction: And|Or</p>
  
  <p>Sentence : Subject Verb Prefix</p>
  
  <p>Subject:  Subject Infix Value | Value   =></p>
  
  <p>Subject = Value SubjectOpt</p>
  
  <p>SubjectOpt = Infix Value SubjectOpt | Epsilon</p>
  
  <p>Verb: ==|!=|>|&lt;</p>
  
  <p>Predicate:  Predicate Infix Value | Value   =></p>
  
  <p>Predicate= Value PredicateOpt</p>
  
  <p>PredicateOpt = Infix Value PredicateOpt | Epsilon</p>
  
  <p>Infix:  +, -, *, /</p>
  
  <p>My code for a compound sentence is as follows:</p>
  
  <pre><code>    private string CompoundSentence(IEnumerator&lt;Token&gt; ts)
      {
          //  CompoundSentence = ( CompoundSentence ) PCSopt  | Sentence CSOpt
  
          string sReturnValue = "";
  
          switch(ts.Current.Category) {
  
              case "OPENPAREN":
              {
                       //Skip past the open parenthesis
                  ts.MoveNext();
  
                  string sCSValue = CompoundSentence(ts);
  
                  if(ts.Current.Category != "CLOSEPAREN") {
  
                      sReturnValue = "Missing parenthesis at " + ts.Current.OriginalString;
                      return sError;
                  }
                  else {
  
                          //Skip past the close parenthesis
                      ts.MoveNext();  
                  }
  
                  sReturnValue = PCSOpt(sCSValue, ts);
  
                  break;
              }
              default:
              {
                  string sSentenceVal = Sentence(ts);
  
                      //sSentenceVal is the truth value -- "TRUE" or "FALSE"
                      //of the initial Sentence component
                      //CSOpt will use that value, along with the particular conjunction
                      //and the value of the current token, 
                      //to generate a new truth value.
                  sReturnValue = CSOpt(sSentenceVal, ts);
  
                  break;
              }
          }
  
          return sReturnValue;
      }
  </code></pre>
  
  <p>As I say, I'm new to this area, so I'm probably not understanding something quite fundamental.</p>
  
  <p>If anyone could steer me in the right direction, I'd greatly appreciate it.</p>