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