From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id LAA11157; Tue, 10 Jun 2003 11:03:59 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA11098 for ; Tue, 10 Jun 2003 11:03:58 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h5A93vH16841 for ; Tue, 10 Jun 2003 11:03:57 +0200 (MET DST) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.9/jtpda-5.4) with ESMTP id h5A93vZA090868 for ; Tue, 10 Jun 2003 11:03:57 +0200 (CEST) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id LAA18666 for ; Tue, 10 Jun 2003 11:03:08 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id LAA1204232 for ; Tue, 10 Jun 2003 11:03:07 +0200 Date: Tue, 10 Jun 2003 11:03:06 +0200 (DST) From: Diego Olivier Fernandez Pons To: caml-list@inria.fr Subject: Re: [Caml-list] Ocamlyacc vs stream parser In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Spam: no; 0.00; pons:01 etu:99 caml-list:01 michal:01 moskal:01 camlp:01 recognizes:01 lalr:01 appel's:01 incorrectly:01 fernandez:01 ecrit:01 compilers:01 dragon:98 writes:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, Michal Moskal a =E9crit : > Sorry, I thought camlp4 recognizes LL(1) languages, and my dragon > book copy states that LR(1) > LL(1) (I'm not sure about LARL(1) > though. Well... I must admit remembering that LL(1) < LALR(1) was almost true. Which means that I knew from the beginning you weren't so far :-) I found in comp.compilers an example by Terence Parr of a LL(1) grammar which is not LALR(1) - I have not checked it ! - http://compilers.iecc.com/comparch/article/93-09-025 He says 'there is at least one LL(1) grammar which is not LALR(1)' Same comment in the Errata page of Andrew Appel's book, edition of 1997 (the figure of that edition was incorrect) http://www.cs.princeton.edu/~appel/modern/basic/ml/errata.html 'Figure 3.26 incorrectly shows LL(1) as a subset of SLR. In fact, LL(1) is not even a subset of LALR(1): there is an LL(1) grammar that is not LALR(1)' And a lot of people state that LL(1) < LALR(1) is 'essentially' true. Wim Pijls writes in his paper 'unifying LL and LR' that LL(1) is a subclass of LALR(1) but he seems to have removed the problematic cases. (Once more, I have not checked the proofs since it wasn't the point I was interested in when reading that paper). Diego Olivier ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners