From: | "Florian G(dot) Pflug" <fgp(at)phlo(dot)org> |
---|---|
To: | Markus Schiltknecht <markus(at)bluegap(dot)ch> |
Cc: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, 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 13:37:46 |
Message-ID: | 45DC4B2A.7080309@phlo.org |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers pgsql-patches |
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) 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.
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
From | Date | Subject | |
---|---|---|---|
Next Message | Alvaro Herrera | 2007-02-21 13:54:07 | Re: Column storage positions |
Previous Message | Oleg Bartunov | 2007-02-21 12:36:57 | Re: 8.3 patches hold queue empty |
From | Date | Subject | |
---|---|---|---|
Next Message | Alvaro Herrera | 2007-02-21 13:59:30 | Re: --enable-xml instead of --with-libxml? |
Previous Message | Adriaan van Os | 2007-02-21 11:06:01 | Re: [BUGS] BUG #2977: dow doesn't conform to ISO-8601 |