[Computer Science & Software Engineering]
Minutes of the FPU, Wednesday 29 September, 1999

Minutes of the FPU, Wednesday 29 September, 1999


Attendees

David Jeffery, Kevin Glynn, Bernie Pope.

Minutes

Bernie presented some recent work on making Parser Combinators efficient [1]. The authors take a standard set of parser combinators (such as those in [2]) and show that on one example they run about 5000 times slower and use 10 times more memory than a direct implementation of the same parser.

They then show how various transformations of the combinators can improve the speed and memory consumption to be only 4 times slower and use 50% more memory. The important transformations which we looked at in the meeting were:

The authors of the paper use clean to demonstrate their new combinators. We felt that the presentation would be clearer using Haskell's monads and do notation.

However, these results do show that parser combinators can be tractable for non-trivial parsing.

References

[1] Pieter Koopman and Rinus Plasmeijer: Efficient Combinator Parsers. LNCS 1595: 120-136, IFL '98

[2] J. Fokker: Functional Parsers. LNCS 925: 1-23, 1st Advanced Functional Programming Workshop 1995


Minutes by Kevin Glynn.
Previous meeting Return to the minutes index page Next meeting
Return to the FPU homepage

Kevin GLYNN
Last Modified: Fri Sep 1 12:15:46 EST 2000