Re: tsearch in core patch, for inclusion

Hi,

Florian G. Pflug wrote:
> According to http://en.wikipedia.org/wiki/LR_parser processing one
> token in any LR(1) parser in the worst case needs to
>  a) Do a lookup in the action table with the current (state, token) pair
>  b) Do a lookup in the goto table with a (state, rule) pair.
>  c) Push one state onto the stack, and pop n states with
>     n being the number of symbols (tokens or other rules) on the right
>     hand side of a rule.
> 
> a) and b) should be O(1). Processing one token pushes at most one state
> onto the stack, so overall no more than N stats can be popped off again,
> making the whole algorithm O(N) with N being the number of tokens of the
> input stream.

Looks correct, thanks. What exactly is Tom worried about, then?

>> Are there any ongoing efforts to rewrite the parser (i.e. using 
>> another algorithm, like a recursive descent parser)?
> Why would you want to do that?

I recall having read something about rewriting the parser. Together with 
Tom being worried about parser performance and knowing GCC has switched 
to a hand written parser some time ago, I suspected bison to be slow. 
That's why I've asked.

Regards

Markus