Re: tsearch in core patch, for inclusion

Markus Schiltknecht wrote:
> 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).

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)
pairb) 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.

AFAIK the only difference between SLR, LALR and LR(1) lies in the
generation of the goto and action tables.

> 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?

greetings, Florian Pflug