johnl@ima.UUCP (08/19/87)
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. Max Webb. -- Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.ARPA Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | cca}!ima Please send responses to the originator of the message -- I cannot forward mail accidentally sent back to compilers. Meta-mail to ima!compilers-request