Re: Why context-free?

torbenm@app-4.diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
7 Oct 2005 21:46:20 -0400

          From comp.compilers

Related articles
Why context-free? nmm1@cus.cam.ac.uk (2005-10-06)
Re: Why context-free? cfc@shell01.TheWorld.com (Chris F Clark) (2005-10-07)
Re: Why context-free? torbenm@app-4.diku.dk (2005-10-07)
Re: Why context-free? rsc@swtch.com (Russ Cox) (2005-10-07)
Re: Why context-free? bobduff@shell01.TheWorld.com (Robert A Duff) (2005-10-07)
Re: Why context-free? nmm1@cus.cam.ac.uk (2005-10-08)
Re: Why context-free? vidyut.vidyut@gmail.com (2005-10-08)
Re: Why context-free? gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-10-09)
Re: Why context-free? mpah@thegreen.co.uk (2005-10-09)
[24 later articles]
| List of all articles for this month |

From: torbenm@app-4.diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
Newsgroups: comp.compilers
Date: 7 Oct 2005 21:46:20 -0400
Organization: Department of Computer Science, University of Copenhagen
References: 05-10-053
Keywords: parse, design
Posted-Date: 07 Oct 2005 21:46:20 EDT

nmm1@cus.cam.ac.uk (Nick Maclaren) writes:


> I have been thinking about a programming language, and have good
> reasons to abandon context-free grammars completely. So what I am
> asking is what reasons are there to favour them - I know of the
> following:
>
> 1) Dogma. Let's skip that.
>
> 2) Efficient, easy to write parsers. That is no longer a major
> issue, and I can deliver that in other ways.
>
> 3) Diagnosability of errors. I can deliver that in other ways.
>
> So WHY should I use a context-free grammar? Good reasons appreciated.


> [The best argument I've heard is that to a first approximation, CFGs
> match languages that people can understand. Of course, since I write
> everything in perl these days, I suppose I don't believe that, either.
> -John]


I agree with John that CFG's are relatively easy for humans to
understand, and using a stronger class of grammars can make programs
harder for people (as well as compilers) to parse.


An advantage of CFG's is also reasonably compact definitions.
Depending on what you want to replace them with, you might lose that.


A third advantage is orthogonality: It is fairly easy to add new
constructions to your language without destroying old ones. This is
more or less the definition of being context-free I suppose. In
practice, though, this isn't entirely true due to requirements of
non-ambiguity in addition to context-freeness. And I suppose that
this may be another reason for using CFG's: You can get automatic
"proofs" of non-ambiguity from your parser generators. And absence of
ambiguity is certainly an important property of a language definition
(at least where the ambiguity leads to several observably different
behaviours).


                Torben


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.