SQL Parsing and Left Recursion

classic Classic list List threaded Threaded
1 message Options
RJ
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

SQL Parsing and Left Recursion

RJ
I am trying to construct an AST that I can generate sql from.

The part that is giving me trouble are and/or expressions. My rules are written as follows:


    public Rule Parse() {
        return Sequence(
                Expression(),
                push(new Query(pop()))
        );
    }
 
    public Rule Expression() {
        return FirstOf(
                LogicalExpression(),
                EqualsExpression()
        );
    }
 
    public Rule LogicalExpression() {
        return Sequence(
                Expression(),
                "AND",
                Expression(),
                push(new AndExpression(pop(), pop()))
        );
    }
 
    public Rule EqualsExpression() {
        return Sequence(
                OneOrMore(
                     TestNotAnyChar("= "),
                     ANY
                ),
                "=",
                OneOrMore(
                     TestNotAnyChar("= "),
                     ANY
                ),
                push(new EqualExpression(pop(), pop()))
        );
    }

The string I'm trying to parse is "val = 1 AND val2 = 1 OR val2 = 0 AND val3 = 0"

The tree should start with an OR Expression with a left expression of "val = 1 AND val2 = 1" and a right expression of "val2 = 0 AND val3 = 0"

I'm not sure of the best way to get the following structure. The recursive call "LogicalExpression() -> Expression() -> LogicalExpression()" is where the issue stems.

Any thoughts/help with how to eliminate the left recursion would be great.
Loading...