From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: ** X-Spam-Status: No, score=2.8 required=5.0 tests=AWL,DNS_FROM_RFC_POST, SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id E531FBBAF for ; Mon, 20 Apr 2009 23:35:58 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: As8BABeI7ElKfS4eimdsb2JhbACCHYsEiFw/AQEBCgkMBw8FqnKBCY8CAQMBA4N6Bg X-IronPort-AV: E=Sophos;i="4.40,219,1238968800"; d="scan'208";a="26542205" Received: from yw-out-2324.google.com ([74.125.46.30]) by mail3-smtp-sop.national.inria.fr with ESMTP; 20 Apr 2009 23:35:33 +0200 Received: by yw-out-2324.google.com with SMTP id 9so1298299ywe.27 for ; Mon, 20 Apr 2009 14:35:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=sZ+va02cO//s3nCvzCGBec+uVNKG4sZiul1P2W+pqCA=; b=Mdk9rM940eZh25NqhXqP5HDAs6bud7yVXnsky2j6mALTqWi12djgeQMOy1SmgLwm5V J4NPfFliZRjT8JMw0mfIyG1NLwk1atMDTxsSqMAf0V/pEviSvJKSEtB9UO55AuM4WSl6 9fC2fcnD/nPeWRYtdiR4/n0/QHRaVOfaeRr8A= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=KdmEX86K5J5jVgw2UF8jwbevJwlK5eSxNpcpMSAanS4f/XdLJVmnvPuZ7m7JUr23RL dIwYKuZqZApVhpDQ9ugDFhrXqnlmCzhXfP6tSXsfK8djI1r69mGSdQL0x3luWrJJovk1 I0rqmkWQrVwUiiBFi56KpviDosLFET9Mw1wos= MIME-Version: 1.0 Received: by 10.150.133.18 with SMTP id g18mr7081560ybd.208.1240263332181; Mon, 20 Apr 2009 14:35:32 -0700 (PDT) In-Reply-To: <200904202215.27735.jon@ffconsultancy.com> References: <200904202215.27735.jon@ffconsultancy.com> Date: Mon, 20 Apr 2009 17:35:32 -0400 Message-ID: <2a1a1a0c0904201435y12e36603t60fb40fd1a7d8260@mail.gmail.com> Subject: Re: [Caml-list] Parallelized parsing From: Mike Lin To: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Spam: no; 0.00; parser:01 lalr:01 grammars:01 ocaml:01 parsers:01 grammars:01 syntax:01 integers:01 lexing:01 tokens:01 beginner's:01 ocaml:01 bug:01 rna:98 20,:98 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 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 b= een > done on parallelized parsers and/or parallel-friendly grammars? > > For example, Mathematica syntax for nested lists of integers looks like: > > =A0{{{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 fro= m a > file) to build a tree of where the tokens { , and } appear by index and t= hen > 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 >