Re: VW Grammar help req from Beginner

Alex Gittens wrote:


> I just started reading a book which claims to explain parsing
> techniques in a non-mathematical manner: "Parsing Techniques: a
> practical guide." So far, it has done an ok job of explaining
> languages and grammars, and the different levels of grammars. But when
> it started explaining how CF grammars can be used to emulate CS
> grammars, I got lost. I get the general idea, but what is the *point*?


It's more the case that as a two-level grammar notation such as van
Wijngaarden can describe context-sensistive languages therefore it is
also capable of describing context-free languages.


> Isn't having to generate usable rules from the hyperrules just as
> inefficient, if not more, as having a long list of alternatives in a
> one-level CF grammar?


No because an equivalent one-level grammar (after expanding the hyper
nothion and notions) would result in an infinite number of rules, which
is probably longer than you invisioned.


> Any help in understanding why VM grammars are
> actually useful would be much appreciated by this nonmathematical
> type; if you could point me to working code (any language) using VM
> grammars in action, I'd be much obliged.


I always recommend Cleveland and Uzgalis "Grammars for Programming
Languages". Sadly long out of print. :-( Published by Elsevier in its
Computer Science Library in 1977. (The same series included that other
complier seminal works as Wulf et al's "The Design of an Optimising
Compiler". Shame that Elsevier can't be persuaded to reprint these
foundational books.)


Cleaveland and Uzgalis describe not only a context senstitive language
using a van Wijngaarden two level grammar. But also successed in using a
VWG2 to describe the run-time state of a program.


Regards, Trevor
[Wulf et al is available in a print-on-demand edition from University
Microfilms, but as far as I can tell, C&U isn't. -John]

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