Re: Why context-free?

"Lasse =?ISO-8859-1?Q?Hiller=F8e?= Petersen" <lhp+news@toft-hp.dk>
23 Oct 2005 00:34:20 -0400

          From comp.compilers

Related articles
[17 earlier articles]
Re: Why context-free? anton@mips.complang.tuwien.ac.at (2005-10-14)
Re: Why context-free? darius@raincode.com (Darius Blasband) (2005-10-19)
Re: Why context-free? nmm1@cus.cam.ac.uk (2005-10-19)
Re: Why context-free? nmm1@cus.cam.ac.uk (2005-10-19)
Re: Why context-free? nmm1@cus.cam.ac.uk (2005-10-20)
Re: Why context-free? find@my.address.elsewhere (Matthias Blume) (2005-10-23)
Re: Why context-free? lhp+news@toft-hp.dk (Lasse =?ISO-8859-1?Q?Hiller=F8e?= Petersen) (2005-10-23)
Re: Why context-free? stephen@dino.dnsalias.com (2005-10-23)
Re: Why context-free? nmm1@cus.cam.ac.uk (2005-10-26)
Re: Why context-free? wyrmwif@tsoft.org (SM Ryan) (2005-10-26)
Re: Why context-free? henry@spsystems.net (2005-10-26)
Re: Why context-free? nmm1@cus.cam.ac.uk (2005-10-27)
Re: Why context-free? dot@dotat.at (Tony Finch) (2005-10-27)
[3 later articles]
| List of all articles for this month |

From: "Lasse =?ISO-8859-1?Q?Hiller=F8e?= Petersen" <lhp+news@toft-hp.dk>
Newsgroups: comp.compilers
Date: 23 Oct 2005 00:34:20 -0400
Organization: No Organization
References: 05-10-053 05-10-055
Keywords: parse
Posted-Date: 23 Oct 2005 00:34:20 EDT

  Chris F Clark <cfc@shell01.TheWorld.com> wrote:


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


...


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


I'm not sure I understand how your argument supports preferring (LL)
context-free grammars to context-sensitive grammars or two-level
grammars, although I share your preference for LL grammars.


Wouldn't it be possible to combine the advantages of an LL grammar with
the power of two-level grammars? As I understand it (if I do at all) a
VWG can be viewed as a finite specification of an infinite CFG. So I
would assume, given a string to parse, you would generate as much of the
CFG as is necessary to parse the string.


Would it be wrong to say that for a given VWG and a finite string W in
the language, it is possible to produce a finite subset (of the
generated "infinite" CFG generated by the VWG), which parses W?


Is there anything that prevents adding a requirement that the generated
grammar be LL? And how much would this restriction "cost"? Would a
restricted VWG (LLVWG?) be less powerful than a full VWG?


I believe this is the method used by A. J. Fisher in _Practical
LL(1)-Based Parsing of van Wijngaarden Grammars_ (1985).


Nick Maclaren was looking for a comprehensible description of VWG,
perhaps I may recommend J. Craig Cleaveland & Robert C. Uzgalis:
_Grammars for Programming Languages_ (1977)? (As I still am quite unsure
of my understanding of VWG, my recommendation of the book probably isn't
worth much, though.)


-Lasse


Post a followup to this message

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