Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!bionet!agate!ucbvax!tut.cis.ohio-state.edu!osu-cis!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
Summary: C syntax not context free
Keywords: BNF, Grammars, Silliness
Message-ID: <913@m10ux.ATT.COM>
Date: 4 Apr 89 04:39:26 GMT
References: <5200040@m.cs.uiuc.edu> <12443@watdragon.waterloo.edu> <16559@mimsy.UUCP>
Organization: AT&T Bell Laboratories
Lines: 51

In article <16559@mimsy.UUCP>, chris@mimsy.UUCP (Chris Torek) writes:
> Incidentally, now that I have said all that (some might say `too much'
> :-) ), the only real difference between a C grammar that accepts
> undeclared typedef names and a Pascal grammar that accepts undeclared
> variable names is that, for some reason, people like to think of type
> declarators as keywords and variables as identifiers.  At least, this
> is the only explanation I can see that we never argue whether Pascal's
> grammar is context free.  (If you require the parser to catch undeclared
> variables, it is not, just as C's is not if you require the parser to
> catch undeclared typedef names.)
> -- 
> In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
> Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris

No, I think there is a real difference in "context-freeness" between
Pascal and C.  In C compilers that are widely considered to conform to
K&R, the syntax accepted by the parser is actually modified when a typedef
is encountered and, furthermore, there is no better way to handle the
typedefs.  To elaborate:

In Pascal, there is only one way to interpret a given statement or declaration,
regardless of any previous declarations.

Consider the following in C, however:

	. . . { T (x); . . . }

How should the construct be parsed?  Is it the declaration of
a variable x of type T (where T is a previously typedef'd identifier)?
Or is it a call to the function T with argument x?

We can't even distinguish between an executable statement and a declaration
in C without resorting to context.  This makes C fundamentally
less context-free than Pascal (or FORTRAN or Ada, for that matter).  The
difference can be put in practical terms by noting that it is impossible to
write a processor for C that accepts exactly those programs that would not
be considered a "syntax error", unless you put a symbol table into the
program, to remember the context of typedefs.  No such requirement holds for
Pascal.  For example, a program that counts executable statements in C
programs must have a symbol table for typedefs, with all the extra complexity
that implies.  The corresponding program for counting statements in Pascal
is much simpler.  The same would hold for a cross-reference program and any
number of other program analyzers.

To summarize, the only way you can parse C with a context-free parser is if
you don't care whether a declaration is confused with an executable statement.
This utterly destroys the usefullness of such a parse, as far as I'm concerned.
-- 
Michael Condict		{att|allegra}!m10ux!mnc
AT&T Bell Labs		(201)582-5911    MH 3B-416
Murray Hill, NJ