John, On May 19, 2007, at 9:06 AM, John Leuner wrote:
I haven't implemented the full PEG grammar and haven't paid any attention to efficiency (eg there is no memoization of parse results).
I'd be very interested to hear of your experiences if/when you try to add memoization.
It's probably just my ineptitude at optimisation but when implementing the peg/leg parser generators for C, every single optimisation I tried to incorporate ended up slowing down the generated parsers. I paid some attention to making the input buffer, backup, and the paths through conditionals as efficient as possible. After that I think it came down to the speed at which I could match strings and character classes.
I fed a C99 grammar (copied from the standard, with left-recursion rewritten) through 'leg' and then pointed the generated parser at a huge pile of C source; it parsed about 3 megabytes (4600+ function definitions and external declarations, 95000 lines of code) per second, with no optimisations whatsoever. (2.16 GHz Core 1 Duo running Darwin.) The 'basic' example (included in the 'peg' source) interprets Tiny BASIC by (re-)parsing every line as source as it executes, putting the execution machinery in semantic actions, and it manages over 1/2 million lines per second (same hardware as above).
Roman Redziejowski wrote a paper (linked from Bryan's packrat page) about backtracking with little or no optimisation that I am tempted to read for possible insights into my 'degrading experiences' with optimisations.
Cheers, Ian _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
