Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!zephyr.ens.tek.com!uw-beaver!cornell!hilfingr
From: hilfingr@rama.cs.cornell.edu (Paul N. Hilfinger)
Newsgroups: comp.lang.misc
Subject: Re: Complexity of syntax
Message-ID: <50360@cornell.UUCP>
Date: 6 Jan 91 20:19:44 GMT
References: <13857:Jan506:12:5891@kramden.acf.nyu.edu> <1991Jan5.081755.23488@agate.berkeley.edu> <14679:Jan509:13:1391@kramden.acf.nyu.edu> <1991Jan6.033646.9847@agate.berkeley.edu>
Sender: nobody@cornell.UUCP
Reply-To: hilfingr@cs.cornell.edu (Paul N. Hilfinger)
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 43

In article <1991Jan6.033646.9847@agate.berkeley.edu> jwl@garnet.berkeley.edu (James Wilbur Lewis) writes:
>In article <14679:Jan509:13:1391@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) 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!

Context-sensitive and type-0 grammars are indeed capable of expressing scope
rules (e.g., "identifiers must be declared in an enclosing scope
before use", "an identifier may only be declared once") and other
static restrictions (such as type restrictions).  The Algol 68
grammar, for example, completely describes what we generally call the
"static semantics" of that language.  Attribute grammars have similar
capabilities.  As a result, the term "syntax" really is used by some
to include static semantic properties.

Of course, the extensive use of context-free grammars of languages
augmented with semi-formal English text has resulted in the imprecise
use of the term "syntax" or "grammar" to refer to "context-free
syntax".  However, since Mr. Lewis appears not to be committing that
particular imprecision, I must disagree with his conclusion.

The distinction between "syntax" and "semantics" is fuzzy.  Syntax is
supposed to be "structure" and semantics is supposed to be "meaning".
However, one can explain the incorrectness of an undeclared identifier
either by saying "it is nonsense to use an identifier that has no
defined meaning"---a semantic explanation---or "an identifier that
forms a primary-expression must be textually identical to a preceding
direct-declarator immediately within an enclosing translation-unit, or
compound-statement"---which makes no reference to the meaning of
anything and is structural or syntactic.  As an even more concrete
example of this fuzziness, consider the description of a language that
has only a fixed number of possible identifiers, but requires
definition before use.  It is possible, in principle, to define the
scope rules in this language either in (context-free) BNF or with
(context-sensitive) traditional English semantics.

Paul Hilfinger