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@xxxxxxxxxxxxx
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)
.

Relevant Pages

  • O(n) Parsing For General Context-Free Grammars & Transductions
    ... a theory and calculus generalizing the "regular expressions" ... of translation based on a context-free or syntax-direct specification. ... grammars (i.e. the grammar that describes the entire set of possible ... translations corresponding a given input); ...
    (comp.theory)
  • Re: resolving ambiguities while parsing a c expression
    ... one can rewrite a "real" language expressed in some ... original grammar into a new form as ... sub-grammar for expressions. ...
    (comp.lang.c)
  • Re: Why LL(1) Parsers do not support left recursion?
    ... languages are ambiguous and don't use deterministic language theory.) ... expressed using either left or right recursion in a grammar. ... the rest of what I said implying accepting ambiguity, ... I would write regular expressions if I wanted to emphasize the fact ...
    (comp.compilers)
  • Re: Constructibility of X -> X^2 bijection
    ... Consider the mapping from the ... enumerates exactly the elements of X (or a grammar that enumerates ... the first two characters in the alphabet. ... characters, changing the ordering of the expressions, thus changing ...
    (sci.math)
  • Re: (expression)++
    ... Is it impossible to define the java syntax such that ++ is not ... The grammar would be context sensitive or unrestricted, ... between expressions that represent variables and expressions that don't. ... additional rule "The result of the postfix expression must be a variable ...
    (comp.lang.java.programmer)