Re: Writing Grammars

Thanks for your reply,


Peter H. Froehlich <pfroehli@ics.uci.edu> wrote:
:> 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.


: I am not aware of anything like that, but I would like to make a
: "position statement" instead. I don't think that these "two steps"
: should exist like you describe them. To me it seems that the "proper"
: way to do things is to decide on an abstract grammar and the
: semantics, and then design a concrete grammar for it that is suitable
: for a certain parsing method. Nothing particularly "error prone" in
: this approach. Of course it does not work that well if you implement a
: language that someone else designed/defined.


Well, lets say you are working for a language that someone else
designed. Lets say C, or lets be really bold and say C++. Now the
language is specified in a rather high level grammar that corresponds
to the semantics of the language constructs. This grammar may not be
fully specified, or may be an ambiguous grammar with some textual
rules that specify how to disambiguate it. Its also unlikely to be
parseable directly with any efficient parsign technique.


Lets say the goal is to build an AST. The AST will look very much
like a parse tree for the high level grammar used to specify the
language. So lets say you have a transduction that maps this original
grammar to an abstract syntax tree of the same shape.


So as a human, I would probably look at this grammar for a while, and
pick a parsing technique, such as LL(1) or LALR(1). I would then
spend a few months of my life trying to shoehorn the grammar into an
LL(1) or LALR(1) grammar. This would involve writing disambiguating
functions such as when an identifier represents a type name versus a
variable name. It would involve performing grammar factoring, to
avoid left recursion or right recursion in the grammar. It would
involve looking at LALR(1) states and fixing ambiguities that arise.
It would involve specifying how to resolve certain precedence
conflicts either by rewriting the grammar to take them into account,
or by specifying what the parser does when it hits an ambiguity.


Then after I had the grammar, I would spend some time to write actions
in the grammar that would generate the abstract tree from the rather
distorted parse-tree shape. In some cases, I may even opt to change
the shape of my abstract grammar to make my life easier.


At any rate, in my experience, this is neither very easy nor very fun.
Perhaps I'm just not very good at it.


But, it seems like much of what is being done could be done by a
computer, probably quicker, probably with less chances of error.
Since we have a transduction (as pointed out by the previous
response), and we can build algebras for manipulating the
transduction, why not try to manipulate the transduction until there
is a grammar that accepts the same language but is parseable by an
efficient parsing technique.


Ok, so thats the general idea. My question still remains, are there
any existing tools like this? Is there any prior art here? How
feasible would such a system be? How much could be done with pure
analytic methods? What about "what-would-a-human-do" type heuristics?


Tim N.

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