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

Kris <kryptech@acm.org>
3 Feb 2006 18:39:31 -0500

          From comp.compilers

Related articles
Using a top-down parser to parse a left recursive grammar kryptech@acm.org (Kris) (2006-02-03)
Re: Using a top-down parser to parse a left recursive grammar DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-06)
| List of all articles for this month |

From: Kris <kryptech@acm.org>
Newsgroups: comp.compilers
Date: 3 Feb 2006 18:39:31 -0500
Organization: Compilers Central
Keywords: parse, question
Posted-Date: 03 Feb 2006 18:39:31 EST

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


Post a followup to this message

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