* Re: [Caml-list] CFG's and Camlp4
2004-08-13 18:11 [Caml-list] CFG's and Camlp4 David McClain
@ 2004-08-13 18:48 ` Paul Snively
0 siblings, 0 replies; 2+ messages in thread
From: Paul Snively @ 2004-08-13 18:48 UTC (permalink / raw)
To: David McClain; +Cc: caml
-----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
<http://www.venge.net/graydon/talks/mkc/html>. :-)
> 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
^ permalink raw reply [flat|nested] 2+ messages in thread