Re: Why context-free?

Nick Maclaren wrote about using something to express type restrictions
in a new language he was designing, to which our esteemed moderator
John, wisely suggested:


> Use attributes. That's what they're for.


John, suggestion has a lot of merit, irrespective of error processing.


Atrributes (i.e. little expressions one adds to the grammar that
compute some context sensitive information) are a really good solution
to the problem of adding well-typed expressions to a grammar.


Trying to put types directly into a grammar is a disaster. It makes
the grammar grow exponentially. That's the general failure of VW
grammars--such grammars are a way of succinctly describing the
explosion. Unfortunately, when one is actually parsing with them, one
has to explode them.


In contrast, attribute expressions effectively become another pass.
One parses the grammar for some rough syntactic correctness using the
CFG. Then once, one has identified the expressions and their
syntactic structure, one walks the resulting tree (or dag) and
computes whether the types can be consistently applied. If one can,
one proceeds to the next step in compilation. If one can't, one can
issue a diagnostic that says, "This part of the expression looked like
it wanted to be this type (or set of types), but this part of the
expression wanted to be this type (or set), and the types are not
compatible, because the following rule is violated...."


The notation of attributes are even correct for expressing type
calculations. They really are calculations and generally form some
form of functional programing language. And, what one wants, as
described above is to "unify" two expressions. Unify meaning, can we
find a setting of the not yet defined values which makes this
expression consistent. This can be used to insert the implied
promotions, conversions, coercions, and/or casts which are used to
make the expression consistent. (And, if it were my language, I would
add a step (compiler output) which gave the fully disambiguated
expressions, so the user could verify that the right interpretation
was made, but that's another topic.)


Enough advice for one day.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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