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
Message-ID: <9861@megaron.arizona.edu>
Date: 23 Mar 89 22:04:21 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 32

In article  <9165@claris.com> hearn@claris.com (Bob Hearn) writes:
>Good idea.  Although I think this whole argument is founded on
>misunderstandings.  It all depends on what you mean by "context-free
>grammar."  If you follow the technical definition, then there is no
>question that C's grammar (as specified in K&R) is context-free.

I agree, that this is founded on misunderstandings, but I think you've
got the wrong misunderstanding.  I believe that C's grammar is _not_,
in fact context free, though the grammar in K&R is.  How can this be?
I'm glad you asked.  The grammar given in K&R isn't technically
correct.  Don't take offense, I'm not making a judgement on this
practice, just pointing it out.

One inaccuracy is in the production

	typedef-name : identifier

I don't know if there are others.  "typedef-name" occurs in the production

	type-specifier: ... | typedef-name

and a mechanical reading of this implies that _any_ identifier can
occur as a type-specifier.  This is not the case.  In fact, an
identifier can only be a type-specifier if it has previously been
declared with a typedef.  I can't prove it, but I believe you need a
context-sensitive grammar to specify this.

So both claims made in this argument are correct:

(1) the grammar of C is not context free
and
(2) the grammar given in K&R is context free