Experimental Results

We have conducted experiments based on three different classes of grammars. Our Haskell program was compiled using the Glasgow Haskell Compiler 6.6. We used a 3GHz/1Gb PC. The performance reported is the "MUT time" as generated in GHC runtime statistics, which is an indication of the time spent doing useful computation. It excludes time spent in garbage collection.

The results in test 1, test 2, and test 3 show that our algorithm exhibits low-polynomial time complexities and can accommodate massively ambiguous input involving the generation of large and complex parse forests. All the timings are in seconds, `*` denotes memory overflow and `-` denotes timings less than 0.005 seconds.