Path: utzoo!utgpu!utstat!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!bionet!agate!ucbvax!tut.cis.ohio-state.edu!rutgers!att!ulysses!mhuxo!mhuxu!m10ux!mnc
From: mnc@m10ux.ATT.COM (Michael Condict)
Newsgroups: comp.lang.misc
Subject: Re: Language Design, or: is C's Grammar Context Free
Summary: context-free grammars exist for any language if you allow supersets
Keywords: BNF, Grammars, Silliness
Message-ID: <931@m10ux.ATT.COM>
Date: 11 Apr 89 05:44:50 GMT
References: <5200040@m.cs.uiuc.edu> <12443@watdragon.waterloo.edu> <16807@mimsy.UUCP>
Organization: AT&T Bell Laboratories
Lines: 45

In article <16807@mimsy.UUCP>, chris@mimsy.UUCP (Chris Torek) writes:
> In article <920@m10ux.ATT.COM> mnc@m10ux.ATT.COM (Michael Condict) writes:
> >What you are ignoring is that very few parsers stand alone by themselves.
> 
> We are not ignoring this.  The topic was `context free grammars', not
> `compilers and parsers'.  If you want to argue that one cannot build
> a useful compiler using a CFG approximation for C, that is fine (since
> we have seen that this is true).  Just do not do it by saying that
> there is no context free grammar that recognises all valid C programs.
> -- 
> In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
> Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris

I never said "there is no context free grammar that recognises all valid C
programs", because this is a vacuous statement, without further explanation.
What do you mean by "all"?  Do you mean "exactly all" or "all plus more"?
What do you mean by valid?  Do you mean the programs that have no "syntax
errors"?  What's a syntax error?  Avoid being circular when you reply.  Or
do you mean the ones that pass through compilers that conform to the ANSI
(proposed) standard without any error messages?  Or the ones that not only
make it through the compiler, but execute in a valid fashion (e.g., do not
attempt to divide by 0)?

If you mean the language consisting of all and only those C programs that meet
the last criterion, clearly such a language is not only not context-free,
but is not even computable.  If you go to the other extreme (as you seem to be
doing) and allow the grammar to accept more than the set of syntactically
valid C programs, then of course such a language is context-free, as is 
the language consisting of an arbitrary sequence of tokens from the
vocabulary of C tokens.

But so what?  I attempted to inject parsers and language-analysis programs
into the discussion because otherwise the discussion has no point.  If you
don't allow me to talk about what sort of use I might want to make of the
parse information, then I can't say whether I think you have a grammar for
a useful superset of the C language.  If the grammar is context-free and
accepts all correctly executing, legal C programs, then it must also accept a
superset of this set, so the crucial issue is: what superset?  E.g., what
errors are you failing to reject and which distinct constructs are you failing
to distinguish between (such as declarations vs. executable statements, in
"T (x);").
-- 
Michael Condict		{att|allegra}!m10ux!mnc
AT&T Bell Labs		(201)582-5911    MH 3B-416
Murray Hill, NJ