A toy compiler from scratch

The parser that implements the PEG interface listed above is built on top of a scanner that provides all the matching functions and the ones that backtracks the input cursor.

This is the interface that the matching functions depend:

• Scanner(input): Constructor that creates a new instance of the scanner taking the input as a parameter;
• Current(): Return what's under the scanner's cursor;
• EOS(): Determine if the current element is the end of the input;
• Error(): Generate a parsing error;
• Expect(e): Return the current element under the cursor if it matches e or throw an error otherwise. Doesn't move input cursor;
• Match(e): Return the current element under the cursor if it matches e and advance the cursor by the size of e;
• Next(): Advance the input cursor;

The parsing function Choice is also implemented in the scanner because it needs direct control over the input cursor in order to backtrack before a new option is attempted. E.g.:

// Part of the JavaScript implementation of the scanner
function choice(...fns) {
  const saved = cursor; // input cursor
  for (const fn of fns) {
    // Once an alternative succeeds, all the other ones
    // are discarded.
    try { return fn(); }
    // If an alternative fails, the cursor is backtracked
    // to where it was in the beginning of the choice
    // operation.
    catch (e) { cursor = saved; }
  }
  // If no alternatives succeed, the choice operation
  // fails.
  throw new Error("None of the options matched");
}

The syntactic predicate Not is implemented in the scanner as well since it backtracks the input cursor after being executed in order to provide infinite look-ahead.

The recursive descent parser generating grammar trees off PEG grammars is built on top of the scanner interface and the PEG functions (ZeroOrMore, Option, Choice, etc). The separation of the scanner interface from the implementation of the PEG functions allowed the construction of the two different scanners: one for text and another one for other data structures (lists).

To make things a bit less abstract, here's an example of each scanner in action:

After collecting the results from the matching operations and nesting them following the grammar's structure, the PEG library can also apply custom functions on the results of each rule execution. E.g.:

// JavaScript API for compiling a grammar and binding
// semantic actions to the generated parser
const grammar = `
  Additive  <- Multitive '+' Additive / Multitive
  Multitive <- Primary '*' Multitive / Primary
  Primary   <- '(' Additive ')' / Number
  Number    <- [0-9]+
`;
const parser = peg.pegc(grammar).bind({
  // The name of the action must correspond to the name
  // of the rule present in the grammar string.  The
  // function `visit` gives the control over when the
  // child nodes will be visited.  That allows executing
  // code before and after visiting happens.  This is
  // very useful during the code generation step on
  // the compiler.
  Additive: ({ visit }) => {
    const v = visit();
    // Ignore the string '+'
    return Array.isArray(v) ? v[0] + v[2] : v;
  },
  Multitive: ({ visit }) => {
    const v = visit();
    // Ignore the string '*'
    return Array.isArray(v) ? v[0] * v[2] : v;
  },
  Primary: ({ visit }) => {
    const v = visit();
    // Remove '(' and ')'
    return Array.isArray(v) ? v[1] : v;
  },
  Number: ({ visit }) => {
    const v = visit();
    const n = Array.isArray(v) ? v.join('') : v;
    return parseInt(n, 10);
  }
});

assertTrue(parser('42') === 42);
assertTrue(parser('40+2*5') === 50);
assertTrue(parser('(40+2)*5') === 210);

One of the effects of the infinite look-ahead, and the backtracking specifically, is that the entire input has to be consumed before deciding if the results are correct or not. In other words, the semantic action application happens as an entirely different traversal after matching is successful.

This is explored in depth in the article Modular Semantic Actions and the general suggestion this implementation follows is that the semantic action application only happens after parsing finishes successfully.

The first stage of the compiler is a PEG grammar that scan and parse the program text and generate an Abstract Syntax Tree (or AST for short) off the syntax I made up. The semantic actions associated with that grammar join lists of characters into words, convert lists of digits into numbers, tweak the shape of the AST to make it less verbose and easier to be traversed and lastly help overcoming two shortcomings of the PEG implementation:

1. Handle left recursion
2. Decide if a result should be wrapped into the name of its parsing rule

There are a few documented ways to handling left recursion on PEGs. The nicest one I found is via Bounded Left Recursion. That approach is described in depth in the article Left Recursion in Parsing Expression Grammars, but I didn't get to fully implement it, so I put it aside to focus on getting to a working compiler.

The second problem of wrapping captured values with the rule name or not could have been fixed by adding a new operator to the PEG implementation and resolved at the grammar level. But instead I chose to implement that using semantic actions since the code needed was simple although a bit verbose. But everything else worked out pretty smoothly. That's enough of background, let's look at an example. The following code:

fn sum(a, b) a + b
print(sum(2, 3))

should generate the following AST:

['Module',
  [['Statement',
    ['Function',
     ['sum',
      ['Params', [['Param', 'a'], ['Param', 'b']]],
      ['Code',
       ['Statement',
        ['BinOp', ['Load', 'a'], '+', ['Load', 'b']]]]]]],
   ['Statement',
    ['Call',
     [['Load', 'print'],
      [['Call',
        [['Load', 'sum' ],
         [['Value', ['Number', 2]],
          ['Value', ['Number', 3]]]]]]]]]]]

Notice that fn sum(a, b) { return a + b } outputs the same tree as fn sum(a, b) a + b. Code blocks accept either a single statement or a list of statements within curly brackets ({}).

After generating the AST during the text parsing phase, we need to go through an additional step before translating the AST into bytecode. The scope of every variable needs to be mapped into one of the three categories:

1. Local variables
2. Global variables
3. Free variables

Let's look at the following code snippet to talk about it:

fn plus_n(x) fn(y) x + y
plus_five = plus_n(5)
print(plus_five(2)) # Equals 7

In the example above, x is declared at the scope created by the plus_n function and must be available when it's summed to y within the scope of the anonymous function. The variable y is a local variable since it gets created and destroyed within the same scope, but x is a free variable.

Free variables are variables available in the lexical scope that must be kept around to be used when the scope that declared these variables isn't around anymore.

Global variables seem to exist in Python for performance reasons. The Python interpreter skips look ups on the local scope for names that are known to be available in the module scope or within the built-in module, like the name print in the example above.

The process of mapping variables into the aforementioned categories is done by traversing the AST using a second PEG grammar for parsing lists instead of a stream of characters. During that process, a symbol table is built and the AST is annotated with information that allows the translation phase to look up each variable in the symbol table.

The following Effigy snippet

fn plus_n(x) fn (y) x + y

generates an annotated AST that looks like this:

['Module',
  [['Statement',
    ['Function',
     [['ScopeId', 2], 'plus_n',
      ['Params', [['Param', 'x']]],
      ['Code',
       ['Statement',
        ['Lambda',
         [['ScopeId', 1],
          ['Params', [['Param', 'y']]],
          ['Code',
           ['Statement',
            ['BinOp',
             ['Load', 'x'], '+', ['Load', 'y']]]]]]]]]]]]]

The ScopeId nodes introduced within each scope are used during the compilation process to look up the nth entry within the current scope of the symbol table. Here's a simplified view of the list of fields a symbol table for the above snippet contains:

[{
  node: 'module',
  fast: [],
  deref: [],
  globals: [],
  children: [{
    node: 'function',
    fast: [],
    deref: ['x'],
    globals: [],
    children: [{
      node: 'lambda',
      fast: ['y'],
      deref: ['x'],
      globals: [],
      children: []
    }]
  }]
}]

One last thing that might be interesting to mention about scopes is that Python tries to figure out if a variable is a free variable by comparing where it was assigned and where it was used. If it is assigned in the same scope that it's being used, it is a local variable. If it is assigned in an enclosing scope, it is a free variable. If one needs to reassign a free variable in an inner scope, the nonlocal keyword is required to inform the Python compiler that the assignment isn't local.

I chose a slightly different way to allow reassigning free variables from enclosing scopes. Effigy provides the let keyword to mark variables as free variables at the outer scope:

fn f(input) {
  let c = 0
  fn next() {
    value = input[c]
    c = c + 1
    return value
  }
  return next
}
cursor = f("word")
print(cursor()) # prints "w"
print(cursor()) # prints "o"

I haven't used Effigy enough to know if that was a good choice though :)

I bet there might be a way of bundling the symbol table and generating the code in a single pass, but that wasn't the route I took. Quite a few decisions I made for handling variable scope were inspired by the beautiful write up Dragon taming with Tailbiter, a bytecode compiler for Python and that's the route that Darius Bacon took on his experiment. I highly recommend reading that post. It's enlightening and might help understanding the rest of this post since I won't get into too many details about how Python itself woks.

Once the AST is annotated by the scope traversal step, it is ready to be fed once again into the second PEG grammar to be traversed once more, but now with the intent of driving the assembler to generate code. In this step, the functions (and modules) in Effigy are assembled into bytecode instructions and bundled into Code objects.

Instances of Code objects store bytecode within the co_code attribute. They also store metadata, like the number of arguments a function receives (co_argcount) or the number of local variables (co_nlocals) for example. The other very important data Code objects store is tables with values. There's one table for literal values (co_consts), one for local variables (co_varnames), one for free variables (co_freevars) and one for global variables (co_names).

All these tables are indexed with integers and carry PyObject instances within them. And since functions themselves are PyObject instances, Code object is a recursive data type.

When the compiler enters a new scope, a Code object instance is created, bytecode is generated and tables are filled with data. When the compiler leaves a scope, the Code object instance is returned and bundled within the outer Code object, up until the module scope, which is the top one.

When code generation is done, the Code object is written into a buffer and a header with the following four 32 bit fields is built:

• magic number
• PEP-552 field (Allows deterministic builds of .pyc files)
• Modified Date
• Size of the code buffer

The last step is to write the header and the code buffer into a .pyc file.

Generating the assembly code for filling in the co_code attributes of Code objects is certainly the biggest task performed by the compiler. Let's take a look at how the compiler would generate code for the following expression result = 2 + 3 * 4.

First the following AST is generated:

['Module',
  ['Statement',
   ['Assignment',
    [['BinOp',
      ['Value', ['Number', 2]],
      '+',
      ['BinOp',
       ['Value', ['Number', 3]],
       '*',
       ['Value', ['Number', 4]]]],
     ['Store', 'result']]]]]

When the translation phase takes the above tree as input, it outputs the following Code object:

{
  constants: [2, 3, 4, null],
  names: ['result'],
  instructions: [
    ['load-const', 0],
    ['load-const', 1],
    ['load-const', 2],
    ['binary-multiply'],
    ['binary-add'],
    ['store-name', 0],
    ['load-const', 3],
    ['return-value']
  ],
}

Notice that the load-const instructions have an index of the constants table as its parameter. That's how the Python Virtual Machine figures out which constant is being referred and what value to push to the stack. The binary-multiply and binary-add instructions pop data from the stack, perform their respective operations, and then push the result back to the stack. The instruction store-name pops the value left by binary-add off the stack and save it into the variable referenced in the names table. The last load-const is there because all Code objects must return. And when a return statement isn't explicitly provided (like in module scopes), null (which represents Python's None) is returned.

It's interesting to mention that the semantic actions for AST nodes that interact with the values tables in the Code object have two jobs. They have to either save or load values from the tables and also emit instructions. The semantic action for the Number nodes is a good example to shown how it's done:

{
  Number: ({ visit }) => {
    // Visit the actual value to join the digits and
    // convert to a JavaScript integer
    const value = visit()[1];
    // Push the value to the constants table if it
    // isn't there yet
    const index = addToTable(attr('constants'), value);
    // Emit the instruction with the index of the
    // constant as the parameter to the instruction
    emit('load-const', index);
  }
}

Besides emitting instructions, the assembler has to support back-patching of values that were not known ahead of time. Three little functions on the assembler's interface allowed that to happen:

• pos(): Return the index of the current instruction;
• ref(): Push the index of the current instruction to a list of labels and return the index of the label;
• fix(label, value): Replace the instruction within label with value.

For the sake of completion, here are the other functions that comprise the assembler's interface (already mentioned on previous sections):

• enter(): Enter a new scope, creating a new Code object instance;
• leave(): Return the Code object built for the current scope and set the enclosing scope as the current one;
• emit(opcode, argument): Append instruction to the co_code attribute of the current Code Object
• attr(name, value=undefined): Helper function for reading or writing a value to one of the values tables of the current scope;

To not have to deal with binary code the whole time I worked on this toy, I wrote a dummy implementation used for debug purposes that contained actual JavaScript lists, strings and numbers.

After validating that the code generation produced what I intended, I just swapped assemblers and used the one that actually knew how to marshal JavaScript objects into the format that the Python Virtual Machine could understand.

The part of the assembler that marshals JavaScript objects into the binary format that the Python Virtual Machine can read is mostly a translation of the code under Python/marshal.c to JavaScript.