From: Clifford Heath <no@...>
Date: 2008-02-06T07:35:13+09:00
Subject: Re: [QUIZ] Parsing JSON (#155)

Eric Mahurin wrote:
> I definitely need to go learn about packrat/PEG stuff.  Sounds interesting
> after looking at wikipedia.  Still don't really understand LR/LALR parsers.
> My main focus has been LL/recursive-descent and PEG sounds to be
> recursive-descent.

Yes, it's a simple concept. I give a little comparison of parsing
techniques which has the flavour of how LR parsing works in my
presentation on Treetop, <http://dataconstellation.com/blog>.
you'll need to grab the audio though.

You can add packrat behaviour any recursive-descent LL parser with
backtracking simply by including, at the start of each rule, code
that says:

return m if (m = memo[location, :rule_name])
start_location = location

and before any other return statement,

return memo[start_location, :rule_name] = parse_result

I'd love to see you bend your considerable mind towards working
out how to minimise the memoization in a packrat parser. The sheer
number of objects created is clearly the performance-limiting
factor.

Clifford Heath.