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 UAA25720; Fri, 13 Aug 2004 20:49:16 +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 UAA26330 for ; Fri, 13 Aug 2004 20:49:15 +0200 (MET DST) Received: from smtpout.mac.com (smtpout.mac.com [17.250.248.47]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i7DInDRM000364 for ; Fri, 13 Aug 2004 20:49:14 +0200 Received: from mac.com (smtpin07-en2 [10.13.10.152]) by smtpout.mac.com (8.12.6/MantshX 2.0) with ESMTP id i7DInCIV018960; Fri, 13 Aug 2004 11:49:12 -0700 (PDT) Received: from [192.168.1.100] (dsl081-080-123.lax1.dsl.speakeasy.net [64.81.80.123]) (authenticated bits=0) by mac.com (Xserve/smtpin07/MantshX 4.0) with ESMTP id i7DIn9Q4028176; Fri, 13 Aug 2004 11:49:10 -0700 (PDT) In-Reply-To: <006b01c48160$f932dc40$0401000a@dylan> References: <006b01c48160$f932dc40$0401000a@dylan> Mime-Version: 1.0 (Apple Message framework v619) Content-Type: text/plain; charset=US-ASCII; format=flowed Message-Id: <64CBEAE9-ED59-11D8-946B-000A27DEEC20@mac.com> Content-Transfer-Encoding: 7bit Cc: caml From: Paul Snively Subject: Re: [Caml-list] CFG's and Camlp4 Date: Fri, 13 Aug 2004 11:48:40 -0700 To: David McClain X-Pgp-Agent: GPGMail 1.0.2 X-Mailer: Apple Mail (2.619) X-Miltered: at concorde with ID 411D0D29.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 camlp:01 hash:01 mcclain:01 camlp:01 extensible:01 rescue:99 graydon:01 lalr:01 lalr:01 pragmatic:01 context-free:99 dependencies:01 overkill:01 dynamically:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi David! On Aug 13, 2004, at 11:11 AM, David McClain wrote: > Actually, after having put off learning Camlp4 for quite some time > because > it seemed so arcane, I now decided at the urging of several people to > dig > into it. > > I have to say that I am quite impressed. Camlp4 represents a kind of > paradigm shift that I was hoping to see when pleading for more modern > approaches. In fact it seems so modern that I'm still trying to wrap my > brain around it. > Heh. Yes, having an actual AST-based "preprocessor," especially in a language with a proper module system, opens up a whole new set of possibilities. The only reason I thought you might not want to use it is because its support for going beyond single-token lookahead isn't any better than ocamlyacc's. On the other hand, other of its terrific qualities likely overcome that single objection, so have fun with it! > Already I have several other uses for this preprocessing. But the idea > of an > extensible grammar, on the fly, is very appealing. I do huge amounts > of Lisp > macrology and came to miss that. I thought to myself that OCaml at > least > made up for it by being so darned convenient to use at the functional > level > that macros just seemed nonessential. But that isn't quite true, and > now > Camlp4 comes to the rescue. > Your path to O'Caml and mine sound very, very similar. If you really want to see some magic using Camlp4, let me highly recommend . :-) > The difficulty I have been having with YACC seems to be caused by the > reduction from LL(1) to LALR(1), where tables have shrunk by > coalescing what > appear to be common productions. That is in fact true for expressions > and > patterns. However, we (Inria and myself) both expect to use different > semantic actions on these two similar syntactic breeds. That becomes > problematic when the parser folds the two cases together. What I'm > doing > would probably work just fine in LL(1), but not entirely correctly in > LALR(1). > Right. Whether we like it or not, our grammars do generally have to be expressed in a way that exposes a reduction-order dependency, which is really just a more pragmatic way of saying that they are not context-free (are you sick of hearing me say that yet)? Once you have a non-context-free grammar, by definition you have order-of-reduction dependencies, and therefore whether your parser generator is Left-Left or Left-Right matters. This is why GLR is so interesting: it adopts the philosophy of "when I encounter an ambiguity I'll just keep all possible interpretations of it in mind until I have enough information to see which interpretation is the correct one." In simple cases, e.g. where operator precedence resolves the ambiguity, you don't need to do anything more that specify that precedence. In more complex cases, you, the grammar author, must specify how to "merge" the possible interpretations. It's quite clever, but perhaps either overkill for your needs, or even if not, again, Camlp4's awesome range of features outweighs the difference. > [I studied the "Dragon Book" many years ago, and was ever so grateful > when > that came to an end. I see now that many of my misconceptions about > language > grammar compilers were never properly reoriented during that period. I > must > also say that I much prefer the arcane new world of Camlp4. Perhaps I > just > like new ideas. I certainly do like new ideas that both work, and > force my > brain onto an entirely new plane. YACC was a great idea at the time. I > know > it still has heavy use -- I use it myself. But dynamically extensible > grammars seem like a neat new idea.] > I would have to agree that the venerable Dragon Book is showing its age, and that parsing, in particular, has come a long way since then. Ironically, though, the Dragon Book talks about a lot more than parsing, but you rarely hear anyone talk about what the Dragon Book has to say about intermediate compiler representations or code-generation issues. My frank thesis is that that means that the parsing stuff was trivial and hence easy to remember, but also therefore the first thing to fall to progress, whereas the meatier material on the rest of a compiler still holds up eh-reasonably-well, although really modern research into formal semantics-based compiler development makes me wonder how on earth we ever did it any other way. > David McClain > Senior Corporate Scientist > Avisere, Inc. > > +1.520.390.7738 (USA) > david.mcclain@avisere.com > > > > ------------------- > 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 > Best regards, Paul -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.4 (Darwin) iEYEARECAAYFAkEdDSIACgkQbot1wzHBQBVKMACglqEmymfPr25M8VNOkouHrW1E XKwAn2u2a3l4m+iYrl4SS6yL368DkgF+ =2Rss -----END PGP SIGNATURE----- ------------------- 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