Using a top-down parser to parse a left recursive grammar

After reading an Article in the January 2006 Dr. Dobbs ("Recursive
Descent, Tail Recursion, & the Dreaded Double Divide."), I became
slightly interested in how you could parse a left recursive grammar
using a sort of top-down parser. I came up with something like this
(sorry for my poor pseudocode):


(simple example grammar)
E := E ('+' T)*
T := T ('*' F)*
F := <integer>


typedef struct tree {
        int value; /* integer value */
        int operator; /* character operator */
}


Tree Parse_E() {
        Tree S0 = Parse_T();
        while(cur_token == '+') {
                cur_token++; /* move the token stream up one */
                Tree S1 = Parse_T();
                Tree S2 = /* allocate memory for tree */
                S2.operator = '+';
                S2.left_subtree = S0;
                S2.right_subtree = S1;
                S0 = S2;
        }
        return S0;
}


Tree Parse_T() {
        Tree S0 = Parse_F();
        while(cur_token == '*') {
                cur_token++;
                Tree S1 = Parse_F();
                Tree S2 = /* alloc memory... */
                S2.operator = '*';
                S2.left_subtree = S0;
                S2.right_subtree = S1;
                S0 = S2;
        }
        return S0;
}


Tree Parse_F() {
        Tree S0 = /* alloc memory */
        S0.value = get_token();
        cur_token++;
        return S0;
}


This is just a rough example of the idea I had, I have not found a name
for it anywhere, and I would like to see if anyone knows what this method
of parsing is called (I have been in compiler design for a short amount of
time). I would be very interested to hear anyones comments on this method.


        --Kris, kryptech@acm.org

Return to the comp.compilers page.
Search the comp.compilers archives again.