Compilers - Am I writing one?

Levi Pearson levi at cold.org
Sun Jun 29 23:01:42 MDT 2008


"Jacob Fugal" <lukfugl at gmail.com> writes:

> To clarify on Levi's comment, eliminating left recursion and the other
> optimizations you need to make recursive descent parsing work nicely
> involves tweaking the *grammar*, not the *language*. The language is
> the set of strings that are valid under the grammar. The tweaks
> involved to make your grammar more RD-friendly should not change the
> language at all, just the manner of defining the language. And in my
> opinion, it's really not *that* bad. But it does require a more robust
> understanding of CFGs (context-free grammars).

To clarify Jacob's comment, you've got to eliminate left-recursion in
the grammar before recursive descent parsing will work *at all*.
Consider the following grammar rule:

        <foo>: <foo> + <bar>

In a recursive descent parser, you move through the productions in a
rule from left to right and call the parsers for those productions.
So, when you hit a 'foo', you call the 'foo' parser.  The first
production is 'foo', so you call the 'foo' parser, et voila, infinite
recursion.

But aside from that point, he's absolutely correct; it's just a matter
of tweaking the grammar in a well-defined manner.  The actual language
that is matched by the grammar is the same after the transformation.
I don't like doing it because, when you're embedding semantic actions
into your grammar rules, things get more complex as you break simple
left-recursive rules into multiple other rules that need to have their
semantic actions combined later on.  

                --Levi



More information about the PLUG mailing list