Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!rutgers!apple!bionet!agate!garnet.berkeley.edu!jwl
From: jwl@garnet.berkeley.edu (James Wilbur Lewis)
Newsgroups: comp.lang.misc
Subject: Re: Complexity of syntax
Message-ID: <1991Jan6.033646.9847@agate.berkeley.edu>
Date: 6 Jan 91 03:36:46 GMT
References: <13857:Jan506:12:5891@kramden.acf.nyu.edu> <1991Jan5.081755.23488@agate.berkeley.edu> <14679:Jan509:13:1391@kramden.acf.nyu.edu>
Sender: usenet@agate.berkeley.edu (USENET Administrator)
Organization: University of California, Berkeley
Lines: 43

In article <14679:Jan509:13:1391@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
-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.

I didn't restrict you to any particular *type* of grammar!  I would accept
BNF, yacc input, a regular expression, a recursive transition network,
a context-sensitive grammar...but make no mistake, syntax IS about
*grammar*, both in linguistics and computer science!  To quote from
one of my NLP texts:

  ``Traditional notions of syntax include ideas like "part of speech" and
"phrase marker" in discussing the structure of a sentence.''  [Birnbaum
and Selfridge, from _Inside Computer Understanding_, p. 331]

It is meaningless to talk about parts of speech, phrase markers, or (I claim)
any other syntactic issues, without at least implicit reference to a grammar.

The construction "int x, y, z, x;" is an invalid C declaration not because
it violates C syntax -- it doesn't, for any reasonable grammar -- but
simply because C compilers do not assign meaning (semantics!) to a program
containing this construct (even though a reasonable interpretation exists).
And what are we to make of "int x; float x;"?  This is *clearly* a
semantic error, sort of a C version of "Colorless green ideas sleep furiously."

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

I asked for a grammar and you gave me a decision procedure.  *BZZZZZT*,
thank you for playing; your consolation prize is a one-week subscription
to sci.lang. :-)

-- Jim Lewis