Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!mailrus!uunet!crdgw1!underdog!volpe
From: volpe@underdog.crd.ge.com (Christopher R Volpe)
Newsgroups: comp.lang.c
Subject: Re: Summary: 'C', is it's grammar context sensitive ?
Message-ID: <11581@crdgw1.crd.ge.com>
Date: 3 Sep 90 22:50:04 GMT
References: <1990Aug30.223440.7377@NCoast.ORG> <11508@crdgw1.crd.ge.com> <1990Sep2.012002.7004@basho.uucp>
Sender: news@crdgw1.crd.ge.com
Reply-To: volpe@underdog.crd.ge.com (Christopher R Volpe)
Lines: 40

In article <1990Sep2.012002.7004@basho.uucp>, john@basho.uucp (John
Lacey) writes:
|>In article <11508@crdgw1.crd.ge.com> of comp.lang.c
|>    volpe@underdog.crd.ge.com (Christopher R Volpe) writes:
|>} Let's clarify some terminology here: First, all context free languages
|>} are context sensitive and all context free grammars are context sensitive.
|>} There is a hierarchy involved here. The concepts are not mutually
|>} exclusive, but rather the former is a superset of the latter. When you
|>} say "context sensitive", you really mean "non context free". 
|>
|>This seems hardly a clarification.  You say all A are B and all B are A,
|>then claim there is a hierarchy in the next sentence.

Ok, I made an error in saying "superset" when I should have said 
"subset". That was a mistake. But, I believe that the rest of what
I said is correct. In addition, I never said anything of the form
"all A are B and all B are A". Where did I ever say the relationship
was commutative? What I *did* say was that the relationship applied
to both *grammars* and *languages*. 

|>
|>There *is* a hierarchy.  But "context sensitive" is not the same as
|>"non context free".  The set of context-sensitive grammars is a superset
|>of the set of context-free grammars.  This implies that all context-free
|>grammars are context-sensitive, but not all context-sensitive grammars
|>are context-free. 

That was (almost) my whole point!

|>The correct statement, then, is that C (as a complete
|>language) is context-sensitive but not context-free.

The rest of my point was that even though the *language* is 
context-sensitive-but-not-context-free, the *grammar* given in K&RII
is truly context-free (it doesn't completely define C, though).

==================
Chris Volpe
G.E. Corporate R&D
volpecr@crd.ge.com