Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!mit-eddie!bloom-beacon!eru!hagbard!sunic!dkuug!diku!thorinn
From: thorinn@diku.dk (Lars Henrik Mathiesen)
Newsgroups: comp.lang.misc
Subject: Re: Complexity of syntax
Message-ID: <1991Jan6.181156.8922@odin.diku.dk>
Date: 6 Jan 91 18:11:56 GMT
References: <11883:Jan502:21:0191@kramden.acf.nyu.edu> <1991Jan5.044445.15116@agate.berkeley.edu> <13857:Jan506:12:5891@kramden.acf.nyu.edu> <1991Jan5.081755.23488@agate.berkeley.edu>
Sender: news@odin.diku.dk (Netnews System)
Organization: Institute of Computer Science, U of Copenhagen
Lines: 26

jwl@garnet.berkeley.edu (James Wilbur Lewis) writes:

>Choose any language you like, or make one up, subject to the conditions of
>the original question: that it allows a large number of identifiers to be 
>declared in a single declaration, with the restriction that each identifier 
>may appear at most once in that declaration.  I believe that you're wrong to 
>refer to that restriction as "syntactic", and am interested in seeing what 
>kind of grammar you can write that will generate all the valid declarations 
>for that language (and no invalid declarations).  Please show *all* your 
>work. :-)

Being a quite unoriginal type of person (or perhaps I'm just lazy)
I'll give a reference instead: A. van Wijngarden et al., Revised
Report on the Algorithmic Language ALGOL 68, _Acta_Informatica_ 5,
1975; reprinted Springer-Verlag, Berlin and New York, 1976.

In ALGOL 68 all context dependencies are described in a two-level (van
Wijngarden) grammar; the rest of the formal description consists of
some basic definitions and an operational semantics. The semantics
does have some restrictions, but violating them just gives undefined
runtime behaviour (it's stuff like dereferencing null pointers and
dangling pointers).

--
Lars Mathiesen, DIKU, U of Copenhagen, Denmark      [uunet!]mcsun!diku!thorinn
Institute of Datalogy -- we're scientists, not engineers.      thorinn@diku.dk