|Re: 2-level grammars amdcad!amd!mipos3!omepd!max@ames.UUCP (1987-08-18)|
|Date:||Tue, 18 Aug 87 17:26:52 PDT|
|From:||amdcad!amd!mipos3!omepd!max@ames.UUCP (Max G. Webb)|
|Organization:||Intel Corp., Hillsboro|
In article <652@ima.ISC.COM> harvard!ut-sally!utah-cs!shebs (Stanley Shebs) writes:
>... which should be a warning signal that
>you're no longer dealing with strings of tokens, except in a purely
>formal sense, and that other general computational mechanisms are worth
>thinking about (recursive functions, logic, term rewriting, etc).
>Of course, the fact that I've been hacking Lisp for the past five years
>has nothing to do with this view of grammars. :-)
The stream of tokens has no known structure for you to use as an
aid to parsing. This is, after all, the point of parsing, yes?
The only information you have available is the ordered sequence
of tokens coming in. Sounds like a stream of tokens to me.
In fact, it is the structure we are looking for that "exists only
in a formal sense" - and given the probability of errors, may not
exist at all.
Of course, any real lisp hacker forgets that not all languages
guarantee a pair of parenthesis around every nonterminal. ;)
>Two-level grammars have the same problem that attribute grammars do -
>they are based on the belief that the world is linear strings of tokens.
>Sooner or later, simple grammars don't work, so people have introduced
>some pretty bizarre schemes to patch things up. (My first response to
>attribute grammars was the word "kludge".) The schemes inevitably go all
>the way to Turing equivalence,
There are well defined classes of AG's with reduced power, and which are
more easily treated theoretically, and which can be translated into a
(at least asymptotically) efficient executable form.
These subclasses are based on restrictions of evalution order of attributes
(ie. left-attributed grammars are a reasonably useful compromise).
But in Van Wijngaarten (2-level) grammars you can add arbitrary productions
at evaluation time (this is right isn't it? Researchers lost interest in
W-grammars before I got into the field -- 1/2 :) )- How do you adjust the
power of this technique? And it isn't enough to lame the feature - the
result needs to be able to be treated formally more easily than turing
machines, or at least automatically translated/interpreted.
My guess is that this is the question (problem) that noone could answer,
and that this is the reason for the demise of W-grammars. No one could
ever automate their use, let alone efficiently.
So the chief problem of W grammars is _not_ in fact shared by AG's.
Return to the
Search the comp.compilers archives again.