Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!sdd.hp.com!spool2.mu.edu!uunet!mcsun!ukc!warwick!nott-cs!piaggio!anw
From: anw@maths.nott.ac.uk (Dr A. N. Walker)
Newsgroups: comp.lang.misc
Subject: Re: Complexity of syntax
Message-ID: <1991Jan8.173302.14624@maths.nott.ac.uk>
Date: 8 Jan 91 17:33:02 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>
Reply-To: anw@maths.nott.ac.uk (Dr A. N. Walker)
Organization: Maths Dept., Nott'm Univ., UK.
Lines: 69

In article <1991Jan5.081755.23488@agate.berkeley.edu>
jwl@garnet.berkeley.edu (James Wilbur Lewis) writes:

	[I asked ...]
>-> ->		is the restriction that you can't declare the same identifier
>-> -> twice in the same declaration syntactic or semantic?

	[and Dan Bernstein replied ...]

>-> -Syntax. It has no effect on semantics.

>Perhaps the poster who asked the above question can verify that he was
>referring to C.

	Not particularly.  My point was simply that it's a grey area.
When I was learning to program, we were taught [this was in the days
when BNF was the greatest thing since sliced bread] that (the moral
equivalent of)

	main () { int i, i; exit (0);}

was "syntactically correct" ('cos it was produced by the BNF), but
"semantically incorrect" (there was a section labelled "semantics"
after each bit of syntax that described what the syntax meant, and
what conditions had to be attached).  It was "impossible to prevent
such programs syntactically" (ie, using BNF).  There you are, then;
it's semantics.

	Well, I've loaned out my Algol 68 Report, but the Draft (MR93)
refers instead to "context conditions" -- the (moral equivalent of the)
above is a "program" but not a "proper program" (one that satisfies
conditions such as "No proper program contains a reach containing
two defining occurrences of a given identifier"), and even less a
"meaningful program" (one whose elaboration is defined by the Report).
MR93 makes it clear that whether the distinction between programs and
proper programs is syntactic or not is a matter of taste.

	By the Revised Report, the above text isn't even a "program" --
it can't be generated by the syntax --, and therefore the restriction is
clearly syntactic (though in a real compiler, it will be checked by
exactly the same piece of code that it always was:  "is this identifier
already in the current chunk of the symbol table?").

	Later work with 2-level grammars (or with attribute grammars, as
others have pointed out) makes it clear that even the "meaningful" programs
can be described completely by syntax, and there is thus no need for
semantics at all.  However, you will find no trace of this in most
definitions of more recent languages (including C, Modula-N and Pascal);
almost universally, there is a syntax that generates improper programs,
and a set of statements in natural language about proper and meaningful
programs.  Even the use of denotational semantics seems to be confined
to formalising this natural language;  in this model, a language is
defined by its semantics, and the syntax is sugar for the reader.

	Since both extremes are espoused by reasonable people, I deduce
that, like so much else, it's a matter of taste.

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

	As others have pointed out, this is easy with a two-level grammar.
For details, see the Revised Report, or [better!] "Grammars of Programming
Languages" by Cleaveland and Uzgalis (Elsevier, 1977).

-- 
Andy Walker, Maths Dept., Nott'm Univ., UK.
anw@maths.nott.ac.uk