Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!purdue!decwrl!megatest!djones
From: djones@megatest.UUCP (Dave Jones)
Newsgroups: comp.lang.misc
Subject: Re: Language Design
Message-ID: <2970@goofy.megatest.UUCP>
Date: 21 Mar 89 03:09:34 GMT
References: <9122@claris.com>
Organization: Megatest Corporation, San Jose, Ca
Lines: 47

From article <9122@claris.com>, by hearn@claris.com (Bob Hearn):
...
> 
> Now, before anyone else wants to tell me that K&R's grammar for C is not
> context-free, will you *please* go and look up the definition of context-free
> grammar???  Hint: anything that can be expressed in BNF is context-free!!
> 
> Bob Hearn
> hearn@claris.com
>  

Bob, Bob, Bob.

Chill out, Dude. You're going to blow a brain vain if you're not
careful.

Now then.

The term "context-free", as Chomsky defined it is not very useful
to us computer types, because no one ever, ever writes grammars any
other way.  To him, "context-free" meant that a rule could only
have one symbol on the left-hand side. "Context-sensitive" meant that
production rules could have strings of symbols on the left:

       a X b <= a x y b

In the above, the a and b form a "context" for the reduction
X <= xy.

I haven't been following the discussion, but I suspect that the
correspondents were not alluding to the unuseful Chomsky definitions,
but instead were using the terms quite literally: "context-free" meaning
"context-free".  I think that is a perfectly reasonable thing to
do, especially if one is unfamiliar with the confusing Chomsky
definition.  (I never did like the practice of "defining" something
that already had a meaning in normal English.)

The grammar as published in K&R (both additions) requires
that the lexical analyzer must use left-context to determine whether
or not a token is recognized as a type-name identifier or a regular
identifier.  In that sense, it is not "context-free".

I seem to remember that I once figured out that it is possible to
modify the grammar so that the scanner and parser do not have to know
about left-context.  But I think I remember that such a parser would
require a two token-lookahead, making it impossible to use with most
compiler-compilers.