Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!clyde.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!hsdndev!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: <23854:Jan619:36:3291@kramden.acf.nyu.edu>
Date: 6 Jan 91 19:36:32 GMT
References: <1991Jan5.081755.23488@agate.berkeley.edu> <14679:Jan509:13:1391@kramden.acf.nyu.edu> <1991Jan6.033646.9847@agate.berkeley.edu>
Organization: IR
Lines: 40

In article <1991Jan6.033646.9847@agate.berkeley.edu> jwl@garnet.berkeley.edu (James Wilbur Lewis) writes:
> -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:

See, this is exactly what I'm talking about.

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

By that argument, every syntactic restriction is a semantic restriction,
because C compilers won't assign meaning to things that aren't
syntactically correct. What does this have to do with standard
definitions of ``syntax''?

> And what are we to make of "int x; float x;"?  This is *clearly* a
> semantic error,

What does this have to do with the question at hand?

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

This is an effective parsing procedure independent of semantics, so by
Minsky's definitions it has to do with syntax. You have heard of Minsky,
I hope? Anyway, syntax does *not* mean any particular type of formal
grammar, or even a combination of such types.

---Dan