English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

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.