kdev-pg: lookahead implementation

Jakob Petsovits jpetso at gmx.at
Tue Feb 7 15:24:04 UTC 2006


On Tuesday, 7. February 2006 14:49, Roberto Raggi wrote:
> I'll try to explain my point of view. Don't take it too seriosly I will
> simplify a bit.
>
> java_lookhead is an hack to implement backtracking. Backtracking is a
> *very* powerful tool, but it can decrease *a lot* the performance of the
> recognizer. If it's possible you should use a *fixed* set of tokens (e.g. K
> tokens) to disambiguate the rule. Sometimes you don't know exactly the
> length of these tokens(K), but you know that this set is finite. In this
> case you can *try* to parse the rule and then merge the resulting AST and
> advance the parser(in case of success) or try with another rule.

Ok, so in summary that is:
- Backtracking is parsing without consuming the tokens.
- Real LL(k) lookahead does not need to simulate parsing because it already 
knows which tokens may occur when, and can generate relatively simple 
conditions out of that knowledge.
Thanks for explaining.

> > Also, would such an implementation make sense for the question item
> > (after all, it does lookahead-parsing with LL(1) characteristics too, and
> > can do lookahead-in-lookahead) or do we want to go for a more complicated
> > solution?
>
> well I want to improve it quite a bit.

alright, I leave that up to you, I don't feel qualified to do good enough for 
that at the moment.

> > I'd like to put all user-specified instance variables (and constructor)
> > into a common superclass which is then subclassed by the parser class and
> > the lookahead helper class. I think it should be possible to copy those
> > variables to the lookahead class and keep the ones from the parser class
> > untouched by using the assign operator. Of course, that only works if the
> > variables are only values, not pointers, or if the user also provides an
> > operator=() method. What do you think about that?
>
> hmm, i don't know.. it looks a bit hacky :-) let's think a bit about it.

If we don't go for the java_lookahead approach, that point is moot anyway.
Dismissed for now.

> > Finally, I'd like to extend the syntax to "?[int]( items )" so that
> > "?[2]( RBRACE )" would do a LA(2).kind == RBRACE check and
> > "?( LBRACE )" means "?[1]( LBRACE )".
>
> this is not necessary. We'll have LL(K) at some point. ?[int] will be
> automagically handled by kdev-pg

mmkay

ciao jakob




More information about the KDevelop-devel mailing list