Re: 2-level grammars

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.
--

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