🚀 go-pugleaf

From article <125@ixi.UUCP>, by clive@ixi.UUCP (Clive):
> This approached this problem by defining the grammar using another (context-free)
> grammar (hence the term 'two-level grammar'). This meant that things like not using
> a variable before it was defined were specified in the *grammar* - very nifty.


Of course these two-level grammars are *substantially* more powerful
than context-free grammars.  Two-level grammars are capable of generating
recursively-enumerable sets (ie. those things that can be recognized only
by something with the power of a Turing machine).  This class of languages
is much larger than both the Context-Free and Context-Sensitive languages.

However, Two-level grammars can also be used to generate the Context-Free
and Context-Sensitive languages that we use for programming.  Two-level
grammars provide a compact and elegant (some would say 'cryptic' :-)
notation for the description of programming language syntax without
the need to escape to a natural language.  Personally, I would love
to see more language designers take advantage of this tool.


-- 
Norman Graham                            Oklahoma State University
  Internet:  norman@a.cs.okstate.edu     Computing and Information Sciences
      UUCP:  {cbosgd, rutgers}           219 Mathematical Sciences Building
              !okstate!norman            Stillwater, OK  74078-0599