Re: Why context-free?

> 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 ....


The best reason I know of is correctness. The argument proceeds like
this.


Recursive descent parsers have a 1-1 correspondence with LL grammars.
That is, if you can write the rules for your language looking at only
a fixed number of tokens ahead, then you can write that down as an LL
grammar (or a recursive descent parser) and you can derive the other
one mechanically.


Next, if you have an LL grammar and if you use a tool, your tool can
(and any good tool will) detect when you make mistakes and make
certain your grammar is still LL. As long as that is true, one can
simply read the grammar and know exactly what language it parses.


To me that's a pretty strong guarantee.


A fairly similar guarantee holds for LR languages. The only thing one
loses from the guarantee with LR is that you can't look at the first
tokens of a rule and tell whether it (or some other similar rule)
applies. If one isn't careful, then losing that guarantee can be too
much, which is why I recommend striving for an LL grammar.


Now, if you have good reasons to abandon context-free grammars, can
you be certain your programming language description describes what
you want? If so, go for it.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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