Re: tsearch in core patch, for inclusion

From: Markus Schiltknecht <markus(at)bluegap(dot)ch>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: Bruce Momjian <bruce(at)momjian(dot)us>, Oleg Bartunov <oleg(at)sai(dot)msu(dot)su>, Alvaro Herrera <alvherre(at)commandprompt(dot)com>, Teodor Sigaev <teodor(at)sigaev(dot)ru>, Pgsql Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: tsearch in core patch, for inclusion
Date: 2007-02-21 11:04:47
Message-ID: 45DC274F.3020905@bluegap.ch
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers pgsql-patches

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

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Magnus Hagander 2007-02-21 12:30:32 Re: pg_proc without oid?
Previous Message Magnus Hagander 2007-02-21 10:03:17 Re: msvc failure in largeobject regression test

Browse pgsql-patches by date

  From Date Subject
Next Message Adriaan van Os 2007-02-21 11:06:01 Re: [BUGS] BUG #2977: dow doesn't conform to ISO-8601
Previous Message Tom Lane 2007-02-21 05:49:11 Re: tsearch in core patch, for inclusion