Larry Evans wrote:
I'd be very interested. I'm thinking about using a sparse matrix where T is symbol_set, where symbol_set is the set of terminal and non-terminal symbols in a grammar. This could be used by spirit in deriving LL(k) parser as described in:
Larry, I've recently experimented on perfect hashing (minimal and non-minimal) where the input is a char or wchar_t or int. What's interesting is that, based on my tests, I exceeded the speed of C++'s switch-case. I did a test on perfect hashing of integers and tested it against a switch in a loop: int test(int i) { switch (i) { case 1: return 0; case 4: return 1; case 9: return 2; case 16: return 3; case 25: return 4; case 36: return 5; case 49: return 6; default: return -1; } } vs. a corresponding perfect hash table. I got 6.6 secs (switch) vs. 0.422 (perfect hash) secs on VC7.1. G++'s switch was faster (i got 2.2) but still 4X slower than the perfect hash. The perfect hash generation can be done at runtime using metaprogramming. I based the algorithms on Bob Jenkin's perfact hash stuff: http://burtleburtle.net/bob/hash/perfect.html I think I've got the makings of an extremelely fast LL(1) engine. See attached test. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net