Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!ig!arizona!gudeman
From: gudeman@arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Language Design, or: is C's Grammar Context Free
Message-ID: <10186@megaron.arizona.edu>
Date: 11 Apr 89 22:15:24 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 50

In article  <10152@megaron.arizona.edu> kwalker@arizona.edu (Kenneth Walker) writes:
>In article <10148@megaron.arizona.edu>, gudeman@arizona.edu (David Gudeman) writes:
>> There is no context free grammar that recognises all valid C programs.
>> ...  By my definition of syntax, ... C's syntax is not context free.
>
>"Context free grammar" and "recognize" have precise technical definitions;
>look them up. By those definitions, there are context free grammars which
>will recongnize any valid C program.

Ken, did you notice who you were responding to?  I think you know that
I could give the technical definitions of "context free grammar" and
"recognize" without looking them up.

>...The statement you want is: there is no unambiguous context free grammar
>which will generate a parse which matches your syntax for all C programs.
>That may be rather long winded, but at least it is accurate.

No, that's not the statement I want.  I think the argument revolves
around one's definition of "C's syntax".  Let CF-C be the context free
language recognized by the C grammar in K&R.  Here is the argument you
seem to be making:

(1)   the syntax of C is CF-C
(2)   CF-C is context free
(3)   therefore, the syntax of C is context free.

Here is the argument _I_ am making:

(1)  the syntax of C is a proper subset of CF-C, called CS-C.
(2)  there is no context free grammar which recognizes exactly the
     language CS-C.
(3)  therefore, the syntax of C is not context free.

Both arguments are sound, and the point of disagreement is statement
(1).  Of course I can't claim that your definition of C's syntax is
_wrong_, but I claim that it is not useful.

I think the most useful definition of the syntax of a programming
language is:

   Definition: the set of strings that do not produce syntax errors
   when compiled by a correct compiler for the language.

This is not unambigous since different correct compilers may produce
slightly different sets of syntax errors.  But it hard to imagine a C
compiler that does not give a syntax error for the declaration:

  newtype x;

where "newtype" has not been declared with a typedef.