Summary: 'C', is it's grammar context sensitive ?
Christopher R Volpe
volpe at underdog.crd.ge.com
Tue Sep 4 08:50:04 AEST 1990
In article <1990Sep2.012002.7004 at basho.uucp>, john at basho.uucp (John
Lacey) writes:
|>In article <11508 at crdgw1.crd.ge.com> of comp.lang.c
|> volpe at 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 at crd.ge.com
More information about the Comp.lang.c
mailing list