Parallelized parsing

[Jon Harrop <jon@ffconsultancy.com>]

I'm desperately trying to prepare for the imminent drop of a rock-solid 
multicore-friendly OCaml implementation and was wondering what work has been 
done on parallelized parsers and/or parallel-friendly grammars?

For example, Mathematica syntax for nested lists of integers looks like:

  {{{1, 2}}, {{3, 4}, {4, 5}}, ..}

and there are obvious divide-and-conquer approaches to lexing and parsing that 
grammar. You can recursively subdivide the string (e.g. memory mapped from a 
file) to build a tree of where the tokens { , and } appear by index and then 
recursively convert the tree into an AST.

What other grammars can be lexed and/or parsed efficiently in parallel?

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e