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=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id E5C4ABC6B for ; Fri, 22 Jun 2007 01:26:51 +0200 (CEST) Received: from sccmmhc91.asp.att.net (sccmmhc91.asp.att.net [204.127.203.211]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5LNQptI013287 for ; Fri, 22 Jun 2007 01:26:51 +0200 Received: from [192.168.0.104] (12-208-242-210.client.mchsi.com[12.208.242.210]) by sccmmhc91.asp.att.net (sccmmhc91) with SMTP id <20070621232649m9100d3q3le>; Thu, 21 Jun 2007 23:26:49 +0000 In-Reply-To: <200706220014.39510.jon@ffconsultancy.com> References: <200706220014.39510.jon@ffconsultancy.com> Mime-Version: 1.0 (Apple Message framework v752.3) Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <569CF4E8-052D-4DA7-B75E-2F8DB24469C1@valdosta.edu> Cc: caml-list@yquem.inria.fr Content-Transfer-Encoding: 7bit From: Jonathan Bryant Subject: Re: [Caml-list] Parsing Date: Thu, 21 Jun 2007 19:26:37 -0400 To: Jon Harrop X-Mailer: Apple Mail (2.752.3) X-Miltered: at concorde with ID 467B093B.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; parsing:01 recursive:01 parsing:01 recursion:01 lalr:01 ocamlyacc:01 parser:01 camlp:01 syntax:01 parsers:01 grammars:01 ocaml:01 parser:01 'int:01 expr:01 It's because with Streams you're doing recursive descent parsing which is LL, so rules can't contain left recursion. It's one of the disadvantages of using LL over LALR, such as OCamlYacc (not saying that LL doesn't also have it's advantages). --Jonathan On Jun 21, 2007, at 7:14 PM, Jon Harrop wrote: > > I'm not a parser junkie, so please bear with me if this is silly... > > The camlp4 stream parsing syntax extension is a very cool way to write > efficient parsers for simple grammars: > > http://www.ffconsultancy.com/ocaml/benefits/parsing.html > > # let rec parse_atom = parser > | [< 'Int n >] -> Num n > | [< 'Kwd "("; e=parse_expr; 'Kwd ")" >] -> e > > and parse_factor = parser > | [< e1=parse_atom; stream >] -> > (parser > | [< 'Kwd "*"; e2=parse_factor >] -> e1 *: e2 > | [< >] -> e1) stream > > and parse_expr = parser > | [< e1=parse_factor; stream >] -> > (parser > | [< 'Kwd "+"; e2=parse_expr >] -> e1 +: e2 > | [< 'Kwd "-"; e2=parse_expr >] -> e1 -: e2 > | [< >] -> e1) stream;; > val parse_atom : Genlex.token Stream.t -> expr = > val parse_factor : Genlex.token Stream.t -> expr = > val parse_expr : Genlex.token Stream.t -> expr = > > However, you must factor heads in the pattern matches. So instead of: > > and parse_expr = parser > | [< e1=parse_factor; 'Kwd "+"; e2=parse_expr >] -> e1 +: e2 > | [< e1=parse_factor; 'Kwd "-"; e2=parse_expr >] -> e1 -: e2 > | [< e1=parse_factor >] -> e1 > > you must write: > > and parse_expr = parser > | [< e1=parse_factor; stream >] -> > (parser > | [< 'Kwd "+"; e2=parse_expr >] -> e1 +: e2 > | [< 'Kwd "-"; e2=parse_expr >] -> e1 -: e2 > | [< >] -> e1) stream > > Why is this? Is it because the streams are destructive? Could the > camlp4 macro > not factor the pattern match for me? > > Are there other parser tools that integrate into the language and > do a better > job? > > -- > Dr Jon D Harrop, Flying Frog Consultancy Ltd. > The OCaml Journal > http://www.ffconsultancy.com/products/ocaml_journal/?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