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

From: Joel de Guzman (joel_at_[hidden])
Date: 2004-12-26 08:57:26

Andreas Pokorny wrote:
> Joel de Guzman wrote:
> 
>>>>An alternative scheme is to let the user switch
>>>>strategies (possibly using spirit directives).
>>>>
>>>>Another scheme, used by PCCTS, is to make the parser predictive
>>>>by default, and allow the user to use syntactic and semantic
>>>>predicates with arbitrary lookahead on specific points in
>>>>the grammar.
>>>
>>>
>>>Eewww, I smell a kludge ;-)
>>
>>Not really. There's a big problem with backtracking in general:
>>backtracking and semantic actions do not mix well (e.g. false
>>triggering). In a syntactic and semantic predicate, all actions
>>are intentionally inhibited.
> 
> 
> Thats up to now the only problem I had, when using spirit. Are there plans, 
> to allow defering of semantic actions? 

Yes.

> E.g like the phrase and character
> level directives that can be used switch the parsers behaviour at certain 
> positions within rules, maybe that could be done for semantic actions too.

Right.

> Such that all semantic actions are triggered after the rules within the
> directive returned sucess.
> 
> Maybe there are better solutions.

Defering of semantic actions to be executed later is a possibility.
Frank Birbacher worked on it sometime ago. I haven't followed up
with the latest developments. One thing to note though is that
deferred actions and auto syntax/parse tree generation is roughly
the same thing. It might be interesting to merge deferred actions
with tree generation.

To guarantee against false trigerring, you'll have to defer the
actions all the way up to the start rule. Only then shall all valid
paths be known. It is also possible to defer actions only on certain
points, but that does not guarantee false triggering if it is itself
a part of an alternative somewhere up the parser hierarchy. Providing
an explicit directive (say, defer_action[p]) is one way of doing it
and passes the responsibility of ensuring that it is placed only
in deterministic points (i.e. where we are sure that no backtracking
will happen) to the client. However, I'm not sure how error prone
that will be. It might also be interesting to let the parser
determine the deterministic points and trigger all defered actions
accumulated so far when the parse reaches such a point.

Cheers,
-- 
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net