Proto for Boost mailing list page: [proto] van Wijngaarden grammars (was: talking proto)

Subject: [proto] van Wijngaarden grammars (was: talking proto)
From: Eric Niebler (eric_at_[hidden])
Date: 2010-07-18 14:00:02

On 7/17/2010 2:20 AM, joel falcou wrote:
> Eric Niebler wrote:
>> Someone on the dev list brought up Van Wijngaarden grammars. I haven't
>> tried to implement them yet (mostly
>> because I don't understand them). There are probably lots of other good
>> ideas out there.
>   
> Basically VW grammar are "template grammars" aka  grammar that match
> parametric rules for which the set of acceptable parameter are
> themselves defined by a rule.

So I've read, but I haven't yet succeeded in wrapping my head around this.

> An example can be:
> 
> definition ::= T varid;
> T ::= {bool,integer}
> 
> This grammar match
> 
> bool a;
> integer b;
> 
> but fail on
> 
> float c;

How is this any different than straight BNF:

definition ::= type varid
type :: bool | integer

Is it that a vW evaluator is free to try *any* rule in the grammar in
place of the T? If so, that seems FAR too powerful to be useful. Indeed
the wikipedia entry says as much. Instead, it points to CDL
(http://en.wikipedia.org/wiki/Compiler_Description_Language) and affix
grammars as more practical for defining programming languages.

> Basically in proto, it is a template grammar which is coupled with a
> meta-function validating the parameter of said grammar.

What is the "parameter" of a grammar? Do you mean the expression against
which you're evaluating the grammar?

> I use some for our SIMD grammar to:
> 1/ have different grammar based on the SIMD base type and control their mix
> 2/ restrict said grammar to types that make sense on given platform to
> be vectorized.
> 
> so i have a grammar:
> 
> template<class T> struct simd_grammar : proto::or_< ... > {};

OK. What is T?

> and a meta-function:
> 
> template<class T> struct is_vectorizable;

What is T, and how is this implemented?

> Currently I replaced all match call by our own match that take a type
> and a grammar and see if it fits both the grammar and the metafunction
> but I guess it could be done better.

Maybe once I understand what you're doing we can find a better way.

I already know how difficult it is to, for instance, ensure that all
terminals in an expression have the same type. That's the problem the
poster who suggested vW grammars had. It doesn't sound like your
technique can help in instances like this.

-- 
Eric Niebler
BoostPro Computing
http://www.boostpro.com