Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!ig!arizona!kwalker
From: kwalker@arizona.edu (Kenneth Walker)
Newsgroups: comp.lang.misc
Subject: Re: Language Design, or: is C's Grammar Context Free
Summary: grammar vs syntax
Message-ID: <10152@megaron.arizona.edu>
Date: 9 Apr 89 18:29:16 GMT
References: <10148@megaron.arizona.edu>
Organization: U of Arizona CS Dept, Tucson
Lines: 27

In article <10148@megaron.arizona.edu>, gudeman@arizona.edu (David Gudeman) writes:
> There is no context free grammar that recognises all valid C programs.
> Several people have pointed out that your artificial definition of
> syntax (anything that can be described with a context free grammar)
> begs the issue.  By my definition of syntax, and aparently that of
> most other posters, 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. The fact that the grammar may
not produce a parse which matches your definition of the syntax of the
program does not invalidate the truth of that statement. As you point
out, one should not confuse grammar and syntax.

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.

As far as I know, "context free syntax" does not have a widely recognized
meaning (can anyone come up with a reference to disprove this?). Clearly
you can define it in such a way that it would be correct to say that
C does not have a context free syntax. However, people will confuse the term
with "context free grammar", so I wouldn't suggest using it. It is better
to make a long winded explaination of the problem with C's syntax.

   Ken Walker / Computer Science Dept / Univ of Arizona / Tucson, AZ 85721
   +1 602 621 2858  kwalker@Arizona.EDU   {uunet|allegra|noao}!arizona!kwalker