Writing Grammars

"Tim Newsham" <newsham@lava.net>
25 Jul 2002 23:24:25 -0400

          From comp.compilers

Related articles
Writing Grammars newsham@lava.net (Tim Newsham) (2002-07-25)
Re: Writing Grammars idbaxter@semdesigns.com (Ira Baxter) (2002-07-31)
Re: Writing Grammars whopkins@alpha2.csd.uwm.edu (Mark) (2002-07-31)
Re: Writing Grammars pfroehli@ics.uci.edu (Peter H. Froehlich) (2002-07-31)
Re: Writing Grammars newsham@lava.net (Tim Newsham) (2002-08-04)
Re: Writing Grammars parsersinc@yahoo.com (SLK Parsers) (2002-08-04)
Re: Writing Grammars vbdis@aol.com (VBDis) (2002-08-10)
| List of all articles for this month |

From: "Tim Newsham" <newsham@lava.net>
Newsgroups: comp.compilers
Date: 25 Jul 2002 23:24:25 -0400
Organization: Compilers Central
Keywords: parse, syntax
Posted-Date: 25 Jul 2002 23:24:25 EDT

It seems pretty typical in compiler (and other parsing) implementation
that you would:

        - start with a grammar of the language
        - modify the grammar to be easy to parse (ie. LALR(1))
        - add rules to build an abstract syntax tree from the
            resulting parse (either the parse tree, or as actions
            during the parse process).

Now if you use a general parsing algorithm like tomita parsing or
earley (or modified earley) parsing, you can go directly from the the
unmodified grammar.

But if you want an efficient parser, you take the time and modify the
grammar, and then build actions that basically undo some of the
ugliness of the parse (because the AST looks similar to the parse of
the original grammar).

My question is: Are there any tools or research into tools to help
automate the process of going from step 1 to step 2. It seems that
this is a very difficult and error-prone step. Basically, software
that would perform the same types of transformations that a human
would perform on the grammar. Even better, to also perform the same
type of transformation on the AST building code as it goes along, so
that the parse tree for the original grammar is built automatically in
the actions of the modified grammar.

Tim N.

Post a followup to this message

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