Re: [boost] Re: Interest in a Recursive Descent Parsing Library

From: christopher diggins (cdiggins_at_[hidden])
Date: 2004-12-24 23:47:00

----- Original Message ----- 
From: "Joel de Guzman" <joel_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Friday, December 24, 2004 6:21 PM
Subject: [boost] Re: Interest in a Recursive Descent Parsing Library

> christopher diggins wrote:
>
>> struct StartRule {
>>  template<typename Elem_T>
>>  static bool Accept(ParserInputStream<Elem_T>& in) {
>>    switch (in.GetChar()) {
>>      case 'a' : return match<RuleA>(in);
>>      case 'b' : return match<RuleB>(in);
>>      case 'c' : return match<RuleC>(in);
>>      case 'd' : return match<RuleD>(in);
>>      default : return false;
>>    }
>>  }
>> }
>>
>> This approach requires the programmer to figure out the FIRST(N) table by 
>> hand. I have found that there are typically only a couple of performance 
>> bottlenecks where lookahead is actually needed, and that generating these 
>> tables by hand to be easy. Perhaps other's experience is different.
>>
>> I would be curious how to express the above grammars in Spirit, with and 
>> without the hand-rolled lookahead rule.
>
> See: http://www.boost.org/libs/spirit/doc/switch_parser.html.

I think this does a good job of illustrating the difference between Spirit 
and YARD. Spirit would require the following code, for the grammar 
production written above using YARD:

    rule<> rule_overall =
            switch_p
            [
                case_p<'a'>(parser_a),
                case_p<'b'>(parser_b),
                case_p<'c'>(parser_b),
                case_p<'d'>(parser_b),
                default_p(parser_default)
            ]
        ;

With Spirit there is an arbitrary upper bound on the number of case 
statements, which defaults to 3(!?). I would think that it is safe to say 
that the YARD parser is easier to use, and has fewer arbitrary constraints 
*BUT* does not provide dynamic rule expressions, and is more verbose.

Is this balance of features in a CFG parsing library something that 
interests anyone in the Boost community?

Christopher Diggins
http://www.cdiggins.com
http://www.heron-language.com