Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Parallelized parsing
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2009-04-20 (21:08)
From: Jon Harrop <jon@f...>
Subject: Parallelized parsing

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.