Recursive Descent Parser and Nested Parentheses

Question

I'm new to the area of grammars and parsing.

I'm trying to write a recursive descent parser that evaluates strings like this:

((3 == 5 AND 4 == 5) OR (6 == 6 ))

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.

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.

My grammar, such as it is, looks like this (the "=>" signs are my own notation for the "translation" of a rule):

Test: If CompoundSentence Then CompoundSentence | CompoundSentence

CompoundSentence : ( CompoundSentence ) PCSopt |CompoundSentence Conjunction Sentence |

Sentence =>

CompoundSentence = ( CompoundSentence ) PCSopt | Sentence CSOpt

PCSOpt = ParenConjunction CompoundSentence PCSOpt| Epsilon

CSOpt = Conjunction Sentence CSOpt| Epsilon

ParenConjunction: And|Or

Conjunction: And|Or

Sentence : Subject Verb Prefix

Subject: Subject Infix Value | Value =>

Subject = Value SubjectOpt

SubjectOpt = Infix Value SubjectOpt | Epsilon

Verb: ==|!=|>|<

Predicate: Predicate Infix Value | Value =>

Predicate= Value PredicateOpt

PredicateOpt = Infix Value PredicateOpt | Epsilon

Infix: +, -, *, /

My code for a compound sentence is as follows:

 private string CompoundSentence(IEnumerator<Token> 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;
 }

As I say, I'm new to this area, so I'm probably not understanding something quite fundamental.

If anyone could steer me in the right direction, I'd greatly appreciate it.

Answer 1

For expressions, a hand-coded recursive descent parser is a pretty easy thing to code.

See my SO answer for how to write recursive descent parsers.

Once you have the structure of the parser, it is pretty easy to evaluate an expression as-you-parse.

Answer 2

The basic convention to follow for parsing is:

1. At the start of a rule, the current token should be the first token that the rule covers.

2. A rule should consume all of the tokens it covers.

Answer 3

I thought it was incredibly subtle, but it turns out to have been quite simple: my scanner wasn't catching the second (and probably higher) close parentheses. Ouch.

Thanks everyone for your help.

Ira, I'll accept your answer for the detailed help it provides on RDP's.