Compiler Internals

Compiler Architecture

                           Source Code
                                +
                                |
                          +-----v------+
                    +-----+  Tokenizer |
                    |     +------------+
                    |
      Token Stream  |
                    |     +------------+
                    +----->   Parser   +------+
                          +------------+      |
                                              | Abstract Syntax Tree
                                              |     (no types)
                          +------------+      |
                     +----+  Semantics <------+
                     |    +------------+
       AST with type |
        Information  |
                     |    +------------+
                     +---->  Validator +------+
                          +------------+      |
                                              |   Validation
                                              | (types, syntax)
                          +-------------+     |
                     +----+  Generator  <-----+
                     |    +-------------+
   Intermediate Code |
     Representation  |
                     |    +-------------+
                     +---->   Emiter    |
                          +-------------+
                                 |
                                 v
                              Binary

Walt uses a traditional compiler architecture, the pipeline is seen above. Each step in the pipeline is a pure function, transforming the input into a new object representing the program. The validator is a minor exception as it performs no transforms on the AST. The parser is a top-down LL(1) parser.

Notes

• WebAssembly spec https://github.com/WebAssembly/wabt
• WebAssembly Text format semantics. https://github.com/WebAssembly/design/blob/master/Semantics.md
• WebAssembly semantics test suite https://github.com/WebAssembly/spec/tree/master/test/core
• WebAssembly Binary Toolkit https://github.com/WebAssembly/wabt.
• S-syntax https://github.com/WebAssembly/spec/tree/master/interpreter#s-expression-syntax
• WAS Syntax experiment from Mozilla https://github.com/mbebenita/was

Reference Grammar

Not an exhaustive grammar but helps to understand how the compiler works. Was done as an exercise to get the parser off the ground. Pretty out of date by now.

stmt -> let id ;

stmt -> let id = expr ;

stmt -> const id = expr ;

stmt -> export stmt ;

stmt -> import { id : typedef } from string ;

stmt -> if ( expr ) stmt

stmt -> if ( expr ) stmt else stmt

stmt -> while ( expr ) stmt

stmt -> do stmt while ( expr )

stmt -> function id ( arglist ) : returntype stmt

returntype -> type | void

stmt -> { stmts }

stmts -> stmts stmt | e

arglist -> arglist arg | e

arg -> id : type | arg , arg

type -> i32 | i64 | f32 | f64

typedef -> type | anyfunc

expr -> expr + term

expr -> expr - term

expr -> term

expr -> id ( paramlist )

paramlist -> e | paramlist

paramlist -> param , param | param

pram -> id | string | expr

term -> term * factor

term -> term / factor

term -> factor

factor -> (expr)

factor -> number

number -> number integer

number -> number . number | number | e

integer -> 0|1|2|3|4|5|6|7|8|9

string -> ' chars '

chars -> chars char | char | e

char -> UTF-8