Programming Forums - Small compiler in Haskell

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Show Off Your Open Source Projects (http://www.programmingforums.org/forum52.html)

- - Small compiler in Haskell (http://www.programmingforums.org/showthread.php?t=14559)

Small compiler in Haskell

This is just something I hacked on for fun but I thought some people might find interesting.

Over the past 2 days or so I've written a small compiler for numeric expressions (i.e. "1 + 12 *42 - (4/2)") in haskell that compiles them to assembly. I just finished the initial code and it seems to be working nicely; the code generated is awful, however. The input is first lexed, and the tokens are then fed into a parser which does the shunting yard algorithm to turn things into RPN. At this point, generating code is really easy, but pretty inefficient. Either way I thought it was cool.

The code can be downloaded from here; I also blogged about the code here. While I doubt this will get me a turing award, I figured a couple people here might be interested. :]

* Edit, here's a trial run for those who don't want to compile, but see some output:

[austin@continuum calc]$ ./calc -rpn

Expression: 52 * 5 - 123 + (14/7)

[EInt 52,EInt 5,Multiply,EInt 123,Minus,EInt 14,EInt 7,Divide,Add]

[austin@continuum calc]$ ./calc -compile

Expression: 52 * 5 - 123 + (14/7)

Disassembly:

08184668  55                            push   ebp

08184669  8b ec                         mov    ebp,esp

0818466b  6a 34                         push   34H

0818466d  6a 05                         push   5H

0818466f  5b                            pop    ebx

08184670  58                            pop    eax

08184671  0f af c3                      imul   eax,ebx

08184674  50                            push   eax

08184675  6a 7b                         push   7bH

08184677  5b                            pop    ebx

08184678  58                            pop    eax

08184679  2b c3                         sub    eax,ebx

0818467b  50                            push   eax

0818467c  6a 0e                         push   0eH

0818467e  6a 07                         push   7H

08184680  5b                            pop    ebx

08184681  58                            pop    eax

08184682  8b d0                         mov    edx,eax

08184684  c1 fa 1f                      sar    edx,1fH

08184687  f7 fb                         idiv   eax,ebx

08184689  50                            push   eax

0818468a  5b                            pop    ebx

0818468b  58                            pop    eax

0818468c  03 c3                         add    eax,ebx

0818468e  50                            push   eax

0818468f  58                            pop    eax

08184690  8b e5                         mov    esp,ebp

08184692  5d                            pop    ebp

08184693  c3                            ret

Result: 139

[austin@continuum calc]$

Re: Small compiler in Haskell

Is there any reason why you didn't use Parsec?

Re: Small compiler in Haskell

Quote:

Originally Posted by Arevos (Post 137592)

Is there any reason why you didn't use Parsec?

I looked at Parsec, which, don't get me wrong is nice (used it for my IRC parser and although I scrapped it the BNF transfered to actual code quite nicely,) but I figured I'd get more in a pedagogical sense if I had the chance to implement a parser just using pure, standard haskell98 (I made sure the Parser.hs file is in fact, haskell98. So far it compiles with GHC and NHC, it should be compilable then with both JHC and YHC. It would perhaps be interesting to look over it for pattern match errs) with as little fuss as possible, with the code generator being simple as well.

(Actually, now that I think of it, the original version was actually written utilizing both Alex and Happy...)

The parser is pure and actually works nicely which is what I was hoping for. By any reasonable standard, there was *no* reason to use Shunting yard or my trivial implementation instead of Parsec. It would allow better code to be generated, probably be more robust and portable, etc. etc.. I suppose you can just chalk it up to wanting a somewhat different approach. In any case, my next project looks like it'll be using harpy and haskell to write a Forth, which will allow me to generate better code and get better with stack-oriented languages. :)

Re: Small compiler in Haskell

I get what you're saying - I recently wrote a basic Lisp interpreter in Python, and I deliberately avoided all of the parsing libraries.

By the way, the way your program compiles into assembly is pretty neat :)

Re: Small compiler in Haskell

Quote:

Originally Posted by Arevos (Post 137850)

By the way, the way your program compiles into assembly is pretty neat :)

I too, like my code generator even if it is somewhat inefficient. It is simple enough to the point I think anybody who wanted to look at it could, and understand with minimal hassle.

Luckily, harpy provides much and it is quite useful, in all honesty. Monadic x86 assembly, all for free. :) If you're interested in runtime code generation, it's really worth a look.