Re: [Caml-list] Parallelized parsing

[Mike Lin <nilekim@gmail.com>]

There is certainly a reasonable body of basic CS research on
parallelizing CFG algorithms such as CYK, the Earley parser, and to a
lesser extent the more practical LALR strategy used by yacc etc. (In
the latter case it seems to get easier if you're willing to trade off
determinism when parsing ambiguous grammars.)

I know some people who use some of this stuff in very specific
contexts (RNA folding), but I haven't seen any practical
general-purpose tools like a parallel yacc...

Overall, I don't actually know much more than you could figure out
from Google Scholar in an hour but hopefully these were some useful
search terms.

On Mon, Apr 20, 2009 at 5:15 PM, Jon Harrop <jon@ffconsultancy.com> wrote:
>
> 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
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>