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

From: Andreas Pokorny (dieMumiee_at_[hidden])
Date: 2004-12-26 13:43:16

Joel de Guzman wrote:
> 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.
Ah yes the ast. I once wrote a parser using spirit, that parsed dependency
strings for a currently delayed linux package management system. Due to 
possible false triggering of semantic actions I had to reiterate over 
the ast output. At that time i found the ast generating syntax not 
intuitive, only with the help of the debugging features, I was able to 
figure out how the tree was built. I would like to see either a more 
transparent interface, or a better documentation. 
  Also, I had problems to make the tree create user defined tree nodes. I
wanted to have at least three different tree node types to be generated in 
the parsing process. One to reflect an if-else-clause, one for a 
boolean expression and another one for a block of packages. But the tree
generating code only works with a single type. I think it might be 
possible to define a base tree template node class, that knows its 
descendant, a type list of possible child nodes, and which defines basic
tree storing and access operations. Thus the user only has to derive from 
that strucuture. 

> 
> 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.
Sometimes the user knows synchronizing symbols, e.g. ";" in C, which
could trigger all delayed actions. But a parser that evaluates such stuff 
would of course be much nicer.  
   Also one needs semantic actions within the parsing process to redefine
the
behaviour of dynamic parsers, which is a really cool feature of spirit.

Regards
Andreas Pokorny 

-- 
Psssst! Mit GMX Handyrechnung senken: http://www.gmx.net/de/go/mail
100 FreeSMS/Monat (GMX TopMail), 50 (GMX ProMail), 10 (GMX FreeMail)