From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p053Oq20016195 for ; Wed, 5 Jan 2011 04:24:52 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApgAAFxOI02AcIhIkWdsb2JhbACVX45OFQEBAQEJCwoHEQUftjqGOoVKBIRoiTw X-IronPort-AV: E=Sophos;i="4.60,275,1291590000"; d="scan'208";a="71965794" Received: from redflag.cs.princeton.edu ([128.112.136.72]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 05 Jan 2011 04:24:46 +0100 Received: from [192.168.1.101] (ool-4355b7a4.dyn.optonline.net [67.85.183.164]) (authenticated bits=0) by redflag.CS.Princeton.EDU (8.13.8/8.13.8) with ESMTP id p053OfXS017950 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT); Tue, 4 Jan 2011 22:24:44 -0500 Mime-Version: 1.0 (Apple Message framework v1082) Content-Type: text/plain; charset=iso-8859-1 From: Yitzhak Mandelbaum In-Reply-To: <4D238B3D.2090903@gmail.com> Date: Tue, 4 Jan 2011 22:24:41 -0500 Cc: caml-list@inria.fr Message-Id: <6A25DBD6-126B-4C9F-A13D-4E2753C0AE2F@cs.princeton.edu> References: <4D23353C.8020803@gmail.com> <1259991756.440008.1294155536392.JavaMail.root@zmbs2.inria.fr> <20110104174545.GA1535@yquem.inria.fr> <1263353434.442766.1294169448342.JavaMail.root@zmbs2.inria.fr> <20110104203152.GA3828@yquem.inria.fr> <4D238B3D.2090903@gmail.com> To: =?iso-8859-1?Q?T=F6r=F6k_Edwin?= X-Mailer: Apple Mail (2.1082) X-Proofpoint-Virus-Version: vendor=nai engine=5400 definitions=6216 signatures=655448 X-Proofpoint-Spam-Reason: safe Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p053Oq20016195 Subject: Re: [Caml-list] Array.make exception and parser Good question -- its languages fall into neither of LL(k) or LR(k). It uses a form of priority parsing, with one token lookahead and a few grammar transformations (assuming camlp4 shares the same parsing technology as camlp5, and nothing has changed since I last took a look at the docs and source code). In more detail: Its basic operation is to try each branch in a series of branches until one is found which successfully parses beyond one token. So, it uses only 1 token of lookahead, and it decides which branch to take at the beginning of set of branches. These characteristics make it similar to LL(1). However, it does not ensure that branches do not conflict. So, if two branches share the same token (see more on this below), then the second one will never be taken. IIRC, the parsec parser combinator library has similar semantics for its standard branch combinator. Furthermore, it performs a number of transformations: First, it does a (shallow) left factoring. So, if a set of branches are defined, it will left factor them without looking into any of the nonterminals. Second, it supports a certain amount of left-recursion through dynamic tracking of the current nonterminal. --Yitzhak On Jan 4, 2011, at 4:03 PM, Török Edwin wrote: > On 2011-01-04 22:40, Lukasz Stafiniak wrote: >> On Tue, Jan 4, 2011 at 9:31 PM, Francois Pottier >> wrote: >>> On Tue, Jan 04, 2011 at 08:30:48PM +0100, Daniel Bünzli wrote: >>>> So everybody trades developer convenience for end user convenience -- >>>> I mean, the syntax errors produced by LR parsers are just terrible, >>> >>> It is true that ocamlyacc (and Menhir) offer essentially no support for >>> explaining parse errors. >> >> But Menhir's support for grammar debugging is very nice and already a >> strong enough argument to switch over from ocamlyacc! >> > > How about camlp4, what kind of parser is it? LL/LR? > I found its error messages more helpful than ocamlc's (for example just > running my source code through camlp4o), though it could be better > (it could say ; expected insteam of [semi]). > > Best regards, > --Edwin > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > ----------------------------- Yitzhak Mandelbaum