[Haskell-cafe] looking for alex+happy examples that uses location annotated tokens and location information in err msgs
Ömer Sinan Ağacan
omeragacan at gmail.com
Sun Mar 9 22:07:20 UTC 2014
> Are you rewriting Eijiro Sumii's MinCaml in Haskell?
> I did the same a couple of years ago, though I used Parsec for parsing
> and only implemented the higher transformations (beta reduction,
> inlining, constant folding, useless variable elimination). As I have
> no access to a Sparc machine, I didn't go as far as closure conversion
> and code generation.
At first I also used Parsec, but I wasn't happy with the parser. The
original grammar has 4 left-recursive productions and I had to
manually eliminate them(I guess you also did that). But after that the
grammar was still not LL(1) so I had to place some `try`s very
carefully. It worked fine, but resulting parser was parsing nested
lets in exponential time. For example, this program took about a
minute to parse:
https://github.com/esumii/min-caml/blob/master/test/spill.ml . So I
rewrote it in Happy and now it works great. (I still need to work on
error messages though. Also, I did not resolve all ambiguities so
Happy reports lots of shift-reduce conficts) I guess that problem with
Parsec parser could also be fixed but I just prefer implementation to
be similar to original definitions. (also, I always wanted to learn
Happy since GHC is using it and I want to start contributing to GHC in
I love starting with some tutorials and then improving final product
by adding more features etc. I started learning Haskell 3 years ago
with "write yourself a Scheme" tutorial and then I added
continuations/call-cc, exceptions and several other features. It
helped me a lot and it was very fun way to learn. I'm currently
planning to do something similar, I want to implement more features
once I have compiler for the original language working.
I also don't have a Sparc machine, so I'm planning to compile to
x86-64. I only know basics of x86-64, so I want to first compile to C.
After I have that working correctly, by looking to generated ASM from
the generated C sources, I want to implement x86-64 code generator. So
I also aim to learn x86-64 assembly.
At some point I also want to implement a garbage collector.. AFAIK no
heap allocation is done in the original language, so I may need some
more data types.. Maybe sum-types or records like in Haskell.
> The code was only for my personal learning as MinCaml was the nicest /
> smallest real compiler I could find. Code is in my Google repository -
> it might be useful for reference, obviously for a learning exercise
> you'd want to do-it-yourself:
> https://code.google.com/p/copperbox/source/browse/ >> trunk >>
> compiler >> HMinCaml
Thanks! I may give it a look if I get stuck at some point.
Ömer Sinan Ağacan
More information about the Haskell-Cafe