Compiler Implementation

Keywords of this phase

The keywords that phase 7, Implementation & Tools, adds to the core language (the core keywords are in Syntax). Each one is explained on the page in the last column.

Open Standard

A language is defined by its specification, not by one program that happens to run it. Eve keeps the two apart on purpose: the specification describes what every Eve program means, and any implementation that follows it is a valid Eve compiler.

One Language, Many Compilers

Several independent implementations make a language stronger. Each one finds unclear rules in the specification, and fixing those rules helps every other implementation. For a student, writing a compiler for a language that already has a specification and a test suite is a demanding exercise: it covers lexing, parsing, type systems, code generation and testing in one project.

• An implementation may be an interpreter, a bytecode virtual machine, a transpiler or a native compiler.
• The official implementation is the Eve virtual machine, written in Zig. It is one program: depending on how it is called, it runs a script directly (eve script.eve) or works in the other modes of the virtual machine (see EVE VM).
• It must state which specification version it implements, for example "Eve 0.1".
• It must state the conformance level it passes (see below).

Specification First

The Eve specification is written in the eve-lang repository, in the spec/ folder. It uses Markdown for rules and explanations, and JSON for the tables a compiler loads directly:

The specification is a work in progress (version 0.1-draft). Where it is not complete yet, this tutorial is the reference. When the two disagree, the specification wins.

Conformance Levels

The test/ folder of the repository holds acceptance tests in three levels. Every test is an Eve driver, so it runs as a standalone program.

Status of the Reference Implementation

The first implementation is the Eve virtual machine, written in Zig (evevm/, built to bin/eve.exe). Compiler stage: Level 1 implemented. It parses every script into a syntax tree, checks the whole tree (the static check, below), and only then executes it with a tree-walking interpreter.

Level 1 covers drivers and free scripts, new, let and set, operators and precedence, strings with placeholders and formats, if, while, loop, for, match, labels, ordinals, lists, arrays, matrices, slices and views, DataSets, DataMaps, Objects, regular expressions (a small subset), expect and assert, over, exit, panic, raise, defer, recover, finalize, and jobs with retry, resume and stop. Functions, procedures, lambdas and closures (level 2), and classes, methods, Date, Time and the operator as (level 3) are not part of level 1.

Known limitations of the reference implementation

These are the places where bin/eve.exe is simpler than the specification. The tests of level 1 pass with them; a later version removes them. Another implementation may do better, but it must pass the same tests.

• Numbers. Decimal and Float are stored as a 64-bit float, so a Decimal is not exact; Huge is a 64-bit integer, not an arbitrary-size number. The results of arithmetic on a typed number (Byte, Short, Decimal) are an Integer or a Real: the type suffix is kept only by the literal.
• Text. A value is a Text, not a String, only when it comes from a """ literal: the machine remembers the address of the literal, so type(x) may say String for a copy made by other means.
• Static types. The static check infers the type of a variable only from a literal, a declared type or a constructor call. A rule that needs a type is checked only then: the private methods of a class (c.inc() is refused when c is known to be a Counter, not when it comes from a parameter) and "a" + 1. When the check does not know, it says nothing and the interpreter raises the error when the line runs.
• Types are not enforced. A declared type gives the default value and converts a Real to an Integer or an Integer to a Real; it does not refuse a wrong assignment. A variant type {Integer | Real} accepts any value.
• Regular expressions support literals, ., ^, $, classes, \d \w \s, the quantifiers * + ?, alternatives with | and the flag i; there are no groups.
• Ranges. A range with real limits, an open end or a real step is a domain: it answers in but can't be iterated. The step of a domain is a grid that starts at 0: 4 in (1..8)(2) is true.
• Entities. The character references &name; of a string know the five marked characters and the lower case Greek letters only.
• Exit code 5 (unexpected stop: Ctrl+C, a time-out, an outage) is reserved; the machine does not set it yet, and no test checks it.
• Levels 2 to 7 (modules, aspects, imports, parallel groups, databases, the server) are not implemented.

The machine is also driven by command files. eve -x -i level1.vmc runs a .vmc file (Virtual Machine Command): one command per line, run in order from the first line. A workflow file loads one script at a time (load, parse, run, errors, ast, inspect, status), ends with stop, and leaves reports in a folder: the output, the errors, the syntax tree and an introspection report for every script. python script/workflow.py 1 runs a whole level this way and compares it with expect.json. The commands are described in manual/usage.md.

Compiler Architecture

Every Eve implementation follows the same front end. The back end is where implementations differ.

Pipeline

Keep the stages separate, even in a small project. A clean AST lets you add a second back end later without touching the parser.

Lexical Analysis

The lexer turns characters into tokens. For Eve, the difficult part is comments, because each comment marker starts with a character that is also an operator (see Delimiters):

• # and ## at column 0 start a comment line (a title or a subtitle), while # inside a line is a placeholder or a symbol of a template string.
• ** starts a comment that runs to the end of the line, while * is multiplication and the vararg mark.
• (** ... **) is an expression comment, which the lexer must tell from (*, a parenthesis followed by a vararg * as in (*args).
• /* ... */ is a block comment (it does not nest), while / is division.

Check comment markers before operators, and follow the longest-match rule. Load keywords and operators from the JSON files instead of hard-coding them, so your lexer follows the specification when it changes. Record the line and column of every token: good error messages depend on it.

For the classic hello world driver, a lexer produces a token stream like this:

# Traditional hello world demo
driver hello_world is

  ** every driver must have a process
  process main is
    print ("Hello World!");
  return;
end hello_world;

COMMENT   "# Traditional hello world demo"
KEYWORD   driver
NAME      hello_world
COLON     :
COMMENT   "** every driver must have a process"
KEYWORD   process
KEYWORD   print
LPAREN    (
STRING    "Hello World!"
RPAREN    )
SEMICOLON ;
KEYWORD   return
SEMICOLON ;
EOF

Parsing

Eve has an explicit, keyword-driven syntax: a script is one indented scope (driver … is, declarations, process, end name;) and blocks close with end, return and done keywords. This makes a hand-written recursive descent parser a good fit:

• Write one parsing function per grammar rule; the grammar in spec/syntax/grammar.md maps directly to these functions.
• Parse expressions with precedence climbing (Pratt parsing), driven by the precedence table in operators.json.
• On a syntax error, report it, skip to the next ; or region keyword, and continue, so one run reports several errors.

Parser generators (ANTLR, Lark) also work, and they are useful to check the grammar itself. Writing the parser by hand, however, teaches more and gives better error messages.

Semantic Analysis

This stage gives the program its meaning. For Eve it covers:

• Scopes: global and local names, the @ and $ sigils, and system variables (see Identifiers).
• Types: static checking with type inference, gradual typing, default values and coercion rules (see Data Types).
• Program topology: drivers, aspects and modules, and how imports resolve (see Topology).
• Numeric precision: comparisons that depend on $epsilon, and exact rational results such as 10/3.

Execution Strategies

Start with a tree-walking interpreter to validate your front end against the tests. Replace the back end later; the tests stay the same.

Recommended Languages

Any general-purpose language can implement Eve. These are the ones we recommend for students, with the reasons.

Comparison

Choosing by Goal

• First compiler, learn the concepts: Python. You spend your time on the language, not on the tools.
• Performance and systems skills: Rust or C, with a bytecode VM or native code.
• Compiler theory: OCaml. Its type system catches many compiler bugs before they run.
• Interoperability with existing libraries: Java or Kotlin on the JVM, or a C transpiler.

Pick a language you already know well. A compiler is a large program; learning a new language at the same time doubles the difficulty.

Tools and References

• Crafting Interpreters: a free book that builds a tree-walking interpreter and a bytecode VM step by step.
• ANTLR: a parser generator for Java, Python and other languages.
• Lark: a Python parser library that reads EBNF grammars; useful to check the Eve grammar.
• Tree-sitter: incremental parsing for syntax highlighting and editor support.
• LLVM and QBE: back ends for native code.

Student Project

Build the implementation in milestones. Each milestone ends with a set of programs your implementation handles correctly, so you always have working software.

Milestones

Where the reference implementation stands: M1, M2, M3, M5 and M6 are done in one tree-walking interpreter (all level 1 tests pass); M4 (type checking) and M7 (topology) are open.

What Level 1 Taught

Rules that the first implementation had to decide while running the level 1 tests. They are now part of the language, and a new implementation must follow them (the decisions are D-058 and D-063 in plan/decision_level1.md):

• Grouping is not a list. (x) is the value of x; (x,) is a list of one element. Without this rule (2 + 3) * 4 cannot be an expression.
• A Rune is one code point. 'one' is a syntax error; use "one". The lexer should reject it with a clear message, not crash later.
• One index on a matrix is absolute. m[5] counts the elements row by row; a row is m[1, *] and a column m[*, 1].
• Errors carry a code. every error has its own code (raise 4, an index error 10, a missing key 11, a division by zero 12, see Exceptions); the exit code of the process is another thing: 2 for a failed expect, 3 for a failed assert, 4 for any other unhandled error; recover catches all of them and reads $error.message, $error.code and $error.job. An unhandled error runs finalize and ends the process with the exit code of the table in Processing.
• Recover has three exits. retry runs the failed job again, resume goes on after it, and reaching the end of recover ends the process as handled. over; skips recover but runs finalize; panic; ends at once with code 1 and runs neither.
• is compares types and identity. type(x) is Real compares two types; a is b is true only for the same list or object, while == compares the contents.
• print and write. print (1, 2, 3) joins with a comma, write (1, 2) joins with nothing, and a DataSet prints as {1,2,3}.
• Parse and check first. The machine always parses a script and checks the whole tree before it runs it. A syntax error, an undefined name, a name declared twice, a let of a name that was never declared, a procedure used in an expression and a mandatory parameter given by position after optional ones are compile errors: the script does not start and the exit code is 65.
• An error code is not an exit code. The error code identifies the error ($error.code); the exit code of the process is 0, 1, 2, 3, 4 or 5 (see Processing).
• exit and over. exit; leaves the subprogram or the process it is written in, over; ends the whole process from any depth; both run finalize and defer.

After M7, choose your direction: a faster back end, level 3 features (files, databases, network), or tooling such as a formatter or a language server.

Common Pitfalls

• Parsing before lexing is solid. Most parser bugs are lexer bugs. Print the token stream first and test it on every demo.
• Hard-coded keyword lists. The specification will add and change keywords. Load them from keywords.json.
• Line endings. Source files may use CRLF or LF. Treat both as one line break, and keep line numbers correct.
• Floating point equality. Eve compares numbers with a precision setting. Do not use the host language == on floats.
• No tests of your own. Keep every program that once broke your implementation as a regression test.

Publishing Your Compiler

1. Publish the source code in a public repository with an open source license.
2. State the specification version and the conformance level your implementation passes.
3. Include the test results: the list of tests that pass and fail.
4. Announce the implementation to the Sage-Code community. Compilers verified by the community will be listed in the specification repository.

The approval process for community-verified compilers is not yet defined; it is planned together with the conformance suite.

Read next: Standard Library