Michael Torrie <[EMAIL PROTECTED]> 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 /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
