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

Hans-Peter Diettrich <DrDiettrich@compuserve.de>
6 Feb 2006 00:06:49 -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: Hans-Peter Diettrich <DrDiettrich@compuserve.de>
Newsgroups: comp.compilers
Date: 6 Feb 2006 00:06:49 -0500
Organization: Compilers Central
References: 06-02-023
Keywords: parse

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


Post a followup to this message

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