Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!bionet!agate!ucbvax!tut.cis.ohio-state.edu!rutgers!att!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
Keywords: BNF, Grammars, Silliness
Message-ID: <920@m10ux.ATT.COM>
Date: 7 Apr 89 04:20:53 GMT
References: <5200040@m.cs.uiuc.edu> <12443@watdragon.waterloo.edu> <6541@bsu-cs.UUCP>
Organization: AT&T Bell Laboratories
Lines: 49

In article <6541@bsu-cs.UUCP>, dhesi@bsu-cs.UUCP (Rahul Dhesi) writes:
> In article <913@m10ux.ATT.COM> mnc@m10ux.ATT.COM (Michael Condict) writes:
> >Consider the following in C, however:
> >
> >	. . . { T (x); . . . }
> >
> >How should the construct be parsed?
> 
> The parsing is always the same, from the point of view of a
> context-free grammer.  It's the semantics that are different.  That you
> assign a different meaning to the language construct based on what has
> come before has nothing to do with its context-free grammar.
>   . . .
> Rahul Dhesi         UUCP:  <backbones>!{iuvax,pur-ee}!bsu-cs!dhesi
>                     ARPA:  dhesi@bsu-cs.bsu.edu

Everyone seems to have missed my point on this, because I used a bad example.
Consider instead the one that someone else posted:

	{ T * x; . . . }

In this case (which could be the declaration of a var x of type (T *) or
could be the expression "T multiplied by x"), the parsing most certainly should
not be the same for either case, at least not if you intend to do anything
useful with the parse.  One of the following two different parse trees
should be produced:

		  *                   decl
		/  \                 /    \
	       T    x		    T      *
					   |
					   x

What you are ignoring is that very few parsers stand alone by themselves.  They
are used in a program that wants to do something with the language.  The
fundamental difference between C and other languages is that because of the
above bogosity, there is much less you can do with the language without
including a symbol table for typedefs.  I can't believe this is even open
for argument.  Try writing programs for C and Pascal that delete all executable
statements, printing only the declarations.  The C version will have to have
a symbol table -- the Pascal version will not.  Isn't that perfectly clear?

Of course we all know that no useful programming language, including C,
Pascal, FORTRAN, Ada or LISP, is context-free when we consider the exact
set of programs that are accepted by the compiler, but that was not my point.
-- 
Michael Condict		{att|allegra}!m10ux!mnc
AT&T Bell Labs		(201)582-5911    MH 3B-416
Murray Hill, NJ