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
---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?
http://archives.postgresql.org
