Re: tsearch in core patch, for inclusion

Hi,

Tom Lane wrote:
> You mean four different object types.  I'm not totally clear on bison's
> scaling behavior relative to the number of productions

You really want to trade parser performance (which is *very* 
implementation specific) for ease of use?

Bison generates a LALR [1] parser, which depend quite a bit on the 
number of productions. But AFAIK the dependency is mostly on memory 
consumption for the internal symbol sets, not so much on runtime 
complexity. I didn't find hard facts about runtime complexity of LALR, 
though (pointers are very welcome).

Are there any ongoing efforts to rewrite the parser (i.e. using another 
algorithm, like a recursive descent parser)?

Regards

Markus

[1]: Wikipedia on the LALR parsing algorithm:
http://en.wikipedia.org/wiki/LALR_parser