Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!shadooby!eecae!tank!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.lang.misc
Subject: Re: Language Design
Message-ID: <16714@mimsy.UUCP>
Date: 4 Apr 89 04:32:37 GMT
References: <5200040@m.cs.uiuc.edu> <12443@watdragon.waterloo.edu> <16674@mimsy.UUCP>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 33

In article <16674@mimsy.UUCP> I wrote:
>(And no, it does not take a nondeterministic automaton to parse C. ...
[gimmick A deleted; gimmick B:]
>associate a function (predicate) with each rule, and allow the
>predicate to abort the rule.

gvcormack points out (as I conveniently forgot to mention) that this
is actually an affix grammar, and affix grammars are not context free.

I think this is a good point for a summary.

	- There is no context free grammar that recognises only valid
	  C programs (but this is true of many languages).

	- There is a trivial context free grammar that recognises all
	  valid C programs, along with a number of invalid ones, but it
	  is ambiguous.  There is probably no unambiguous CFG for C
	  (consider arbitrarily many parentheses around an id: is it a
	  cast or a value?).

	- There is a trivial affix grammar (gimmick B above) that
	  recognises all valid C programs, along with a number of
	  invalid ones, which is not ambiguous and can be handled with
	  a modified yacc (you would have to augment yacc's output
	  tables and parser to retain both reductions and to know what
	  to call to select which is to occur).

and of course,

	- There is always the wrong way. :-)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris