Re: Why context-free?

  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

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