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

From: christopher diggins (cdiggins_at_[hidden])
Date: 2004-12-24 11:25:46

----- Original Message ----- 
From: "Larry Evans" <cppljevans_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Friday, December 24, 2004 8:42 AM
Subject: [boost] Re: Interest in a Recursive Descent Parsing Library

> On 12/24/2004 12:13 AM, christopher diggins wrote:
> [snip]
>> I would not say YARD is a better parser than Spirit, it is designed with 
>> quite different goals. YARD is designed to be compact and flexible. 
>> Concerning "first/follow set kind of things" I am not sure what you mean.
>
> They're used to determine the next non-terminal to parse by looking
> ahead 1 terminal symbol (for LL[1] parser).
[snip]

In YARD lookahead can be easily be done by hand. Consider the following 
grammar (which is in fact a complete and legal YARD grammar)

struct StartRule : public re_or<RuleAB, RuleCD> { /* empty */ };
struct RuleAB : public re_or<RuleA, RuleB> { /* empty */ };
struct RuleCD : public re_or<RuleC, RuleD> { /* empty */ };
struct RuleA : public re_and<re_plus<MatchChar<'a'> > { /* empty */ }; // 
matches a a*
struct RuleB : public re_and<re_plus<MatchChar<'b'> > { /* empty */ }; // 
matches b b*
struct RuleC : public re_and<re_plus<MatchChar<'c'> > { /* empty */ }; // 
matches c c*
struct RuleD : public re_and<re_plus<MatchChar<'d'> > { /* empty */ }; // 
matches d d*

The straightforward way to implement a look-ahead rule in YARD would be to 
rewrite the StartRule as:

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.

Christopher Diggins
http://www.cdiggins.com