Writing A Compiler In Haskell (Compiler Series Part I)

My goal is to write a series of posts on creating a compiler for a restricted subset, NewL, of the Java language in Haskell. My tools are Haskell, Alex for scanning, and Happy for parsing.

Alex and Happy are basically the Haskell equivalent of Lex and Yacc. I know most of my compiler theory and practices from the Dragon book so I’ll be making references to it for the techniques used in semantic analysis and code generation. I’ve learned everything I know about Haskell from the really good book “Real World Haskell“, I cannot recommend it highly enough.

I plan to cover the following topics with Haskell source code and make files included.

1. Go over the grammar of NewL (this post).
2. Scanner for NewL using Alex.
3. Parser for NewL using Happy.
4. Error recover and reporting for the scanner and parser (I’m keeping it simple and abort on the first error and print the line and column number)
5. Symbol table and how it’s used in semantic analysis and code generation.
6. Revised NewL language and more symbol tables.
7. Type checking.
8. Intermediate code generation.
9. Machine code generation.
10. Garbage collection.

As you can see that’s a lot of stuff to cover. I’m warning you ahead of time that I’m very much a newbie when it comes to writing Haskell. I don’t even understand monads, so be forewarned the code get ugly compared to a true Haskell programmer.

With the above out of the way I’d like to go over the grammar of NewL. Please note that the semantics of NewL are similar to Java so if there’s any question about what some operation should do, we follow what Java does.

Terminal symbols are bolded and single character ones are in double quotes.

NewL Grammar

1. Program ::= MainClass { ClassDecl }
2. MainClass :== class Ident “{” public static void main “(” String “[" "]“ Ident “)” “{” Statement “}” “}“
3. ClassDecl ::= class Ident “{” {VarDecl} {MethodDecl} “}“
4. VarDecl ::= Type Ident “;“
5. MethodDecl ::= public Type Ident “(” FormalList “)” “{” {VarDecl} {Statement} return Exp “;” “}“
6. FormalList :== Type Ident { FormalRest } | ε
7. FormalRest :== “,” Type Ident
8. Type :== int “[" "]“ | boolean | int | String | Ident
9. Statement :== “{” { Statement } “}” | if “(“ Exp “)” Statement else Statement | while “(” Exp “)” Statement | System.out.println “(” Exp “)” “;” | Ident = Exp “;” | Ident “[" Exp "]” “=” Exp “;“
10. Exp ::= Exp Op Exp | Exp “[" Exp "]” | Exp “.” length | Exp “.” Ident “(” ExpList “)” |
Integer_Literal | String_Literal | true | false | Ident | this | new int “[" Exp "]” | new Ident “(” “)” | “!” Exp | “(” Exp “)“
11. ExpList :== Exp { ExpRest } | ε
12. ExpRest ::= “,” Exp
13. Ident ::= Letter { Letter | Digit | “_” }
14. Integer_Literal ::= Digit { Digit }
15. String_Literal ::= ““” { Character } “““
16. Op ::= && | < | +| - | *

The classic Hello World for NewL

class HelloWorld {
    public static void main(String[] a) {
        System.out.println(new Hello().World());
    }
}
class Hello {
    public String World() {
        return "Hello World";
    }
}

About these ads