----- Original Message ----- From: "Larry Evans" <cppljevans@cox-internet.com> To: <boost@lists.boost.org> 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