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

Kris wrote:
>
> 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>


Sorry, this grammar is incomplete or wrong. At least it should also
contain:
E := T
T := F


>
> typedef struct tree {
> int value; /* integer value */
> int operator; /* character operator */
> }
>
> Tree Parse_E() {
> Tree S0 = Parse_T();
[...]


You realize that your code doesn't reflect the above grammar? In a
direct implementation, you'd have to call Parse_E for the evaluation of
S0, with obvious infinite recursion. In fact you implement the
non-recursive grammar:


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


BTW, this notation hides the left/right aspect of possible recursion.
Such a distinction has to be made only, when the grammar is transformed
into BNF, where the repetition has to be expressed by either left or
right recursive productions. Perhaps you found intuitively the superior
feature of EBNF, which allows to write grammars with (almost?) no
implied left or rigth recursion.


DoDi

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