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.
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.