Compilers - Am I writing one?

Levi Pearson levi at cold.org
Mon Jun 30 10:35:48 MDT 2008


Michael Torrie <torriem at gmail.com> writes:
> I am curious about your easy rote exercise to create BNF from a syntax
> diagram.  How do you do it?  How do you properly convert an iterative
> diagram into the recursive productions that BNF requires?  It's not
> always correct to convert an iterative production into right-recursive
> format, yet left-recursive is problematic.  How do you deal with this?

Left-recursive grammars are only an issue if you're using a parser
that's based on standard recursive descent techniques.  You can always
rewrite a left-recursive grammar into a right-recursive one, but you
can run into semantic issues like unintentionally changing the
associativity of your operators.  You can deal with this by creating a
bunch of new nonterminals to force the correct precedence and
associativity, or you can ignore the created parse tree and use
something like a semantic action stack to build a different structure
to use for semantic analysis than your parse tree.

While I think syntax diagrams are a great way of visualizing the
grammar, I don't think they actually add any expressiveness.  In fact,
the translation between the two looks very straightforward to me.

Anyway, here's a paper that discusses removal of left-recursion:
http://research.microsoft.com/users/bobmoore/naacl2k-proc-rev.pdf

There are a couple of new techniques for doing top-down parsing of
left-recursive grammars, which I personally find very interesting.  I
think this is really the future of parsers for ad-hoc domain specific
languages and file formats, though it may still make sense to fall
back on traditional techniques where time and space performance is a
primary concern.  Here are some links:

http://www.vpri.org/pdf/packrat_TR-2007-002.pdf

http://www.cs.uwindsor.ca/~hafiz/pc.html

The first is a variant of packrat parsing, which is typically
associated with the Parsing Expression Grammars that Hans mentioned
earlier.

The second is associated with Parser Combinators, which create an
embedded domain specific language for recursive descent parsing within
your favorte language (assuming your favorite language is flexible
enough to support them).  It specifically deals with Parser
Combinators in Haskell, which AFAIK is where they first gained
popularity (though I think they may have first been implemented in
Miranda, the predecessor to Haskell).

                --Levi



More information about the PLUG mailing list