Nim0, a subset of Nim language, with a compiler to a 32-bits RISC CPU and a runtime emulator

Pierre Métras


So you want to hack the Nim compiler but you are afraid by the complexity of the project? Look at Nim0 first to understand compiler basis. Try to add a new feature on your own, and then jump on the real project.

Nim0 is a toy compiler for a limited subset of Nim language, all in 5 heavily documented source files (less than 4k LOC) so that you can understand them. It is a port of Niklaus Wirth’s Oberon-0 compiler. You can read Wirth’s book Compiler Construction provided in the misc directory and follow in the code.

The compiler can translate Nim0 source code to RISC 32 bits machine instructions (yes, that’s a 32 platform and it makes the Nim code a bit more complex). A RISC emulator lets you run the resulting code, and you can even display and follow the content of the registers and RISC assembler instructions.

Nim0 language is a tiny subset of Nim, but the goal is that Nim0 code is valid Nim code. Just change the .nim0 extension to .nim to run it with a serious compiler (You’ll probably need to write a few templates to adapt Nim0 I/O procedures to Nim)!

Nim0 features

Compared with Nim, Nim0 implements only minimal features to understand compiler construction:

Can you write real programs with such limited features? Have a look at the examples


nim0 compiler and runtime.
Usage: nim0 action [options]* source [args]*

action    comp  Compile Nim0 source
          run   Excute source object file

options   -s    Show generated assembler after compilation.

source          When compiling, Nim0 source code. Assume .nim0 extension.
                When execution, RISC object file. Assume .rsc extension

args            Command to be executed and parameters.


Nim0 has been developed and tested on Linux with Nim 1.5. I don’t know if it works on Windows or other environments. It’ll probably require small adjustments. If you have a Nim compiler on your Linux machine, you can try it right now!


Let’s try it by yourself. First compile is to create the Nim0 compiler (look at config.nims for the project’s other tasks).

nim0$ nim build

It creates the nim0 executable in the current directory.

Now, write your first Nim0 program and name it examples/Alpha0.nim0 (You’re lucky, I typed it for you; look into the examples folder).

## My first Nim0 program: print integer squares in range 0 ... 10.

  i: int
  r: int

proc sqr(x: int; sqrX: var int) =
  # Square the value of `x` and return it in `sqrX`.
  sqrX = x * x

for i in 0 .. 10:
  sqr(i, r)

You can compile your first Nim0 program now:

nim0$ ./nim0 comp examples/Alpha0
Nim0 Compiler v1.0
  compiling examples/Alpha0.nim0
code generated examples/Alpha0, PC=40, dc=8, key=-1973735804

If you want to see the generated RISC assembler code, add the -v option.

nim0$ ./nim0 comp -v examples/Alpha0
Nim0 Compiler v1.0
  compiling examples/Alpha0.nim0
code generated examples/Alpha0, PC=40, dc=8, key=-1973735804
                                        # 001 ## My first Nim0 program: print integer squares in range 0 ... 10.
                                        # 002 
                                        # 003 var
                                        # 004   i: int
                                        # 005   r: int
                                        # 006 
                                        # 007 proc sqr(x: int; sqrX: var int) =
0000 4EE9000C        SUB SP, SP, 12
                                        # 008   # Square the value of `x` and return it in `sqrX`.
                                        # 009   sqrX = x * x
0001 AFE00000        STW LNK, SP, 0
0002 A0E00004        STW R0, SP, 4
0003 A1E00008        STW R1, SP, 8
                                        # 010 
0004 80E00004        LDW R0, SP, 4
0005 81E00004        LDW R1, SP, 4
0006 000A0001        MUL R0, R0, R1
0007 81E00008        LDW R1, SP, 8
0008 A0100000        STW R0, R1, 0
0009 8FE00000        LDW LNK, SP, 0
0010 4EE8000C        ADD SP, SP, 12
0011 C700000F        B LNK
0012 4EE90004        SUB SP, SP, 4
0013 AFE00000        STW LNK, SP, 0
0014 40000000        MOV R0, 0
0015 A0D00000        STW R0, SB, 0
                                        # 011 for i in 0 .. 10:
0016 80D00000        LDW R0, SB, 0
0017 4009000A        CMP R0, 10
0018 EE000012        BGT 18
0019 80D00000        LDW R0, SB, 0
                                        # 012   sqr(i, r)
0020 41D80004        ADD R1, SB, 4
0021 F7FFFFEA        BL -22
                                        # 013   write(i)
0022 80D00000        LDW R0, SB, 0
0023 A00FFFFC        writeInt <- R0
                                        # 014   write('*')
0024 4000002A        MOV R0, 42
0025 A00FFFFB        writeChar <- R0
                                        # 015   write(i)
0026 80D00000        LDW R0, SB, 0
0027 A00FFFFC        writeInt <- R0
                                        # 016   write('=')
0028 4000003D        MOV R0, 61
0029 A00FFFFB        writeChar <- R0
                                        # 017   write(r)
0030 80D00004        LDW R0, SB, 4
0031 A00FFFFC        writeInt <- R0
                                        # 018   writeLine()
0032 A00FFFFA        writeLine
0033 80D00000        LDW R0, SB, 0
0034 40080001        ADD R0, R0, 1
0035 A0D00000        STW R0, SB, 0
0036 E7FFFFEB        B -21
0037 8FE00000        LDW LNK, SP, 0
0038 4EE80004        ADD SP, SP, 4
0039 C700000F        B LNK

OK. Now let’s run the compiled code:

nim0$ ./nim0 run examples/Alpha0

You can even trace program execution and see the content of the RISC registers. Before program execution, Nim0 dumps the RISC assembler after code relocation in memory, showing the areas for global variables, code and execution stack. As it is quite verbose, I dump only the most representative parts in the truncated dump below.

nim0$ ./nim0 run -v examples/Alpha0
Global variables in memory adresses Mem[0 .. 1]
Module code in memory adresses      Mem[2 .. 41]
Runtime stack in memory adresses    Mem[42 .. 2047]

Resulting RISC assembler
0002 4EE9000C        SUB SP, SP, 12
0003 AFE00000        STW LNK, SP, 0
0004 A0E00004        STW R0, SP, 4
0005 A1E00008        STW R1, SP, 8
... truncated ...

Starting execution...
                                        PC=14, R0=0, R1=0, R2=0, R3=0, R4=0, R5=0, R6=0, R7=0, R8=0, R9=0, R10=0, R11=0, R12=0, SB=0'u32, SP=8152'u32, LNK=0'u32, N=false, Z=false
000001        0014 4EE90004        SUB SP, SP, 4
                                        PC=15, R0=0, R1=0, R2=0, R3=0, R4=0, R5=0, R6=0, R7=0, R8=0, R9=0, R10=0, R11=0, R12=0, SB=0'u32, SP=8148'u32, LNK=0'u32, N=false, Z=false
000002        0015 AFE00000        STW LNK, SP, 0
                                                        Mem[2036 | 8144]=2863311530 -> AAAAAAAA
                                                        Mem[2037 | 8148]=2863311530 -> AAAAAAAA <
                                                        Mem[2038 | 8152]=2863311530 -> AAAAAAAA
                                                        Mem[2036 | 8144]=2863311530 -> AAAAAAAA
                                                        Mem[2037 | 8148]=0 -> 00000000 <
                                                        Mem[2038 | 8152]=2863311530 -> AAAAAAAA
                                        PC=16, R0=0, R1=0, R2=0, R3=0, R4=0, R5=0, R6=0, R7=0, R8=0, R9=0, R10=0, R11=0, R12=0, SB=0'u32, SP=8148'u32, LNK=0'u32, N=false, Z=false
000003        0016 40000000        MOV R0, 0
                                        PC=17, R0=0, R1=0, R2=0, R3=0, R4=0, R5=0, R6=0, R7=0, R8=0, R9=0, R10=0, R11=0, R12=0, SB=0'u32, SP=8148'u32, LNK=0'u32, N=false, Z=true
000004        0017 A0D00000        STW R0, SB, 0
... truncated ...

To compile all Nim0 supplied examples, run the Nim task buildExamples. Look at the example source to see how to invoke it: some of them use the notion of Oberon command as defined in Wirth’s documents, while others are more like Nim scripts.

nim0$ nim buildExamples
Nim0 Compiler v1.0
  compiling examples/Hello.nim0
code generated examples/Hello, PC=59, dc=0, key=1338925179
Nim0 Compiler v1.0
  compiling examples/Factorial.nim0
code generated examples/Factorial, PC=49, dc=8, key=982993432
Nim0 Compiler v1.0
  compiling examples/MagicSquares.nim0
code generated examples/MagicSquares, PC=116, dc=0, key=-90451726
Nim0 Compiler v1.0
  compiling examples/Maths.nim0
code generated examples/Maths, PC=386, dc=44, key=201681063
Nim0 Compiler v1.0
  compiling examples/PrimeNumbers.nim0
code generated examples/PrimeNumbers, PC=235, dc=0, key=1527623905
Nim0 Compiler v1.0
  compiling examples/Sudoku.nim0
code generated examples/Sudoku, PC=492, dc=328, key=-2053649788

Nim0 EBNF syntax

We use EBNF to provide the syntax of the Nim0 language.

As a quick reminder, “|” is used to define alternatives. “{ … }” describes terms that can be omitted or repeated. “[ … ]” is used for optional terms. Terminal strings are presented between quotes.

In Nim0 like in Nim, spaces are part of the grammar. Indentation is represented using the IND>, IND= and DED pseudo terms with a context value (see Nim documentation for detailed explanation):

ident = letter {letter | digit}.
integer = digit {digit}.
comment = "#" {chars ignored to the end of the line}

selector = {"." ident | "[" expression "]"}.
number = integer.
factor = ident selector | number | "(" expression ")" | "not" factor.
term = factor {("*" | "div" | "mod" | "and") factor}.
simpleExpression = ["+" | "-"] term {("+" | "-" | "or") term}.
expression = simpleExpression [("=" | "!=" | "<" | "<=" | ">" | ">=") simpleExpression].
assignment = ident selector "-" expression.
actualParameters = "(" [expression {"," expression}] ")".
procedureCall = ident [actualParameters].
ifStatement = "if" expression ":" IND> statementSequence {IND= "elif" expression ":" IND> statementSequence} [IND= "else:" IND> statementSequence] DED.
whileStatement = "while" expression ":" IND> statementSequence DED.
untilStatement = "until" expression ":" IND> statementSequence DED.
forStatement = "for" ident "in" expression ".." expression ":" IND> statementSequence DED.
blockStatement = "block" ":" IND> statementSequence DED.
statement = [assignment | procedureCall | ifStatement | whileStatement | untilStatement | forStatement | blockStatement].
statementSequence = statement {IND= statement}.
identList = ident {"," ident}.
arrayType = "array" "[" expression "," type "]".
fieldList = [identList ":" type].
objectType = "object" IND> fieldList {"," fieldList} DED.
type = ident | arrayType | objectType.
fpSection = identList ":" ["var"] type.
formalParameters = "(" [fpSection {";" fpSection}] ")".
procedureHeading = "proc" ident [formalParameters].
procedureBody = [declaration | statementSequence].
procedureDeclaration = procedureHeading "=" IND> procedureBody DED.
declarations = ["const" IND> {IND= ident "=" expression} DED] | ["type" IND> {IND= ident "=" type} DED] | ["var" IND> {IND= identList ":" type} DED] | {procedureDeclaration}.
module = declarations [statementSequence].

The until control structure does not exist in Nim but is present in Oberon-0 and was kept in the code because it can be useful sometimes (it is used a few times in the Nim0 compiler). It can be easily defined in Nim as:

template until*(cond, body: untyped): untyped =
  ## Reproduces Oberon-0 `REPEAT body UNTIL cond;`
  while true:
    if cond:

The source files

The sources are available on the project repository:

All source files are cross-indexed with Wirth’s Compiler Construction book. Reference like [CC13] refers to page 13 of this document. Procedure and variable names are based on Wirth’s original names, but a module prefix has been appended for public names and procedures. For instance, ossId is defined in module OSS.nim in Nim0 while the original name is id.

Differences with Wirth’s compiler

Major differences between Nim0 and Nim

Nim0 is really a toy language based on Niklaus Wirth’s Oberon-0 with a nim-like syntax. Don’t expect too much! But it can be used to write small programs and understand how they are compiled to RISC machine instructions.

Bugs and TODO

There are a few bugs, of course, as debugging a compiler is not a simple operation and I did not construct a complete test suite. Here are some bugs that you can try to correct…

How to extend it?

Of course, you can add more features to make Nim0 more Nim compatible… Wirth lists exercises at the end of each chapter of Compiler Construction, to add new types or control structures, or even standard procedures. You just have the choice.

I’ve left some parts of Wirth’s code that can be used to relocate code if you want to support a non fixed-address memory model and play with code relocation or modules, like a system linker. You can decide also to produce better RISC code: there are many parts where you can generate better assembler, without resorting to a syntax tree (AST) like in Nim.

Also, you can make the language safer. For instance, there are no checks that a variable is initialized before use nor that an index is within bounds of an array. Or you can check for overflows when doing calculations.

I haven’t completed the for loop to support automatic variable declaration as I was short for time. You can find a draft in function ospForStatement2.


Nim0 is created under the MIT license.