Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!ncar!gatech!rutgers!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Complexity of syntax
Message-ID: <14679:Jan509:13:1391@kramden.acf.nyu.edu>
Date: 5 Jan 91 09:13:13 GMT
References: <1991Jan5.044445.15116@agate.berkeley.edu> <13857:Jan506:12:5891@kramden.acf.nyu.edu> <1991Jan5.081755.23488@agate.berkeley.edu>
Organization: IR
Lines: 18

In article <1991Jan5.081755.23488@agate.berkeley.edu> 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).

One of the failures of the modern computer science curriculum is that it
teaches people to think that ``syntax'' refers to a certain type of
formal grammar.

To answer the (trivial) challenge: Parse each declaration into its
multiset of identifiers. If the multiset contains any duplicates, the
declaration is illegal. Otherwise it passes this stage of parsing. Done.

---Dan