Path: utzoo!utgpu!utstat!jarvis.csri.toronto.edu!mailrus!eecae!tank!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.lang.misc
Subject: Re: Language Design, or: is C's Grammar Context Free
Keywords: BNF, Grammars, Silliness
Message-ID: <16561@mimsy.UUCP>
Date: 27 Mar 89 17:54:37 GMT
References: <5200040@m.cs.uiuc.edu> <12443@watdragon.waterloo.edu> <16557@mimsy.UUCP>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 31

Oops, in amongst all that verbiage, I forgot to answer the other
obvious question:  Why, if there is a reasonable CFG that accepts
all correct C programs (and some incorrect ones as well, that can
be rejected by the semantics instead), does PCC use something else?

Our `impure' CFG includes (among others) the following productions
(rearranged and simplified to make the problem obvious):

	statement : '{' optional-declarators statement-list '}'
	statement : expression
	declarator : typedef-name '*' identifier	// i.e., a pointer
	typedef-name : identifier
	expression : identifier '*' identifier		// i.e., multiply

Thus, there are two correct parses for the input string

	{ t * x; }

One declares the variable `x' as a pointer to the typedef'd type `t';
the other multiplies the value of `t' by the value of `x'.

It seems our impure C CFG is ambiguous.

Well, we never said otherwise....

As a practical matter, we want the compiler to choose the declarator
parse if and only if `t' is in fact an active typedef name.  Fortunately,
there are a number of ways to gimmick a parser to do this.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris