Interesting quote from Roman Redziejowski:
"...should we simply learn to think in terms of Parsing Expressions?
Does BNF seem easier to understand because it better reflects the
working of human mind, or because we are just used to it?"
I think BNF seems easier to understand because of CFG brainwashing in
university. Even today, left recursive grammars smell bad to me because
although you can readily understand what it seems to mean it can be
quite difficult to understand how it works in a given grammar. Whereas
PEGs - which, as Redziejowski notes, describe a parser not a language -
read like a novel. Hey, I'm a programmer.
Bob
Ian Piumarta wrote:
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
