Programming Forums > Projects > Show Off Your Open Source Projects

Mad_guy · Nov 22nd, 2007, 10:08 PM

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:

(Toggle Plain Text)

[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]$

Arevos · Nov 26th, 2007, 7:44 PM

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

Mad_guy · Nov 29th, 2007, 9:55 PM

Quote:

Originally Posted by Arevos

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.

Arevos · Nov 30th, 2007, 7:59 AM

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

Mad_guy · Dec 2nd, 2007, 1:36 PM

Quote:

Originally Posted by Arevos

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.

Nov 22nd, 2007, 10:08 PM	#1
Mad_guy Hobbyist Programmer Join Date: Oct 2004 Location: Sandstorm, Techno Club Posts: 239 Rep Power: 5	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: (Toggle Plain Text) [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]$ [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]$ __________________ os: mac os 10.5.4 revision control: git editor: emacs site

Nov 26th, 2007, 7:44 PM	#2
Arevos Programming Guru Join Date: Aug 2005 Location: England Posts: 1,499 Rep Power: 5	Re: Small compiler in Haskell Is there any reason why you didn't use Parsec?

Nov 30th, 2007, 7:59 AM	#4
Arevos Programming Guru Join Date: Aug 2005 Location: England Posts: 1,499 Rep Power: 5	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

Thread Tools
Show Printable Version Email this Page
Display Modes
Switch to Linear Mode Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
programming outside the compiler	TwilightProgrammers	C++	9	Jun 4th, 2006 6:21 PM
[tutorial] Simple G++ compiler tutorial	coldDeath	C++	7	Nov 27th, 2005 1:33 PM
DOS Compiler!	Starter	C++	11	Apr 15th, 2005 11:14 PM
Newbie : need help with Dev-C++ compiler	gemini_shooter	C++	16	Apr 12th, 2005 4:09 AM
C Compiler turbo C	Princeck	C++	0	Feb 24th, 2005 8:31 PM

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Projects > Show Off Your Open Source Projects

Small compiler in Haskell