Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!osu-cis!netsys!rutgers!okstate!norman
From: norman@a.cs.okstate.edu (Norman Graham)
Newsgroups: comp.lang.misc
Subject: Re: Language Design
Summary: Two-level grammars (was Re: Language Design)
Message-ID: <4549@okstate.UUCP>
Date: 1 Apr 89 00:36:09 GMT
References: <5200040@m.cs.uiuc.edu> <12443@watdragon.waterloo.edu> <125@ixi.UUCP>
Organization: Oklahoma State Univ., Stillwater
Lines: 25

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