A meta approach to implementing programming languages

Published on 2018-12-02.

28 May 2019: Added link to next article in Putting it together.

How does the computer know what to do with the following expression?

1+2*3

How does it know how to recognize the sequence of characters as an arithmetic expression? How does it know that 2*3 should be computed first? How does it translate it to instructions that execute on the CPU?

In this article I present a metalanguage that I've developed that can help answer those questions.

• Metalanguages
• Interpreting expressions
• Compiling expressions
• RLMeta implementation
  • Parser
    • Grammar
    • Rule
    • Choice
    • Sequence
    • Expression
    • Expression of level 1
    • Expression of level 2
    • Host expression
    • Character related
    • Name
    • Space
  • Code generator
    • Note on target language
    • Parsing algorithm
    • Structure of code generator
    • Grammar
    • Rule
    • Or
    • Scope
    • And
    • Bind
    • Star
    • Not
    • Semantic action
    • Match rule
    • Match range
    • Match string
    • Match character sequence
    • Match any
    • Match list
    • String
    • List
    • Builder
    • Function call
    • Variable lookup
    • Final support methods
  • Putting it together
  • Bootstrapping
• Implementing programming languages
• Resources
• Code listings for RLMeta
  • parser.rlmeta
  • codegenerator.rlmeta
  • support.py
  • compile.sh

Metalanguages

Metalanguages are used to reason about languages. In metalanguages you can make statements about statements in a different language.

The metalanguage I've developed is called RLMeta. It is inspired by a metalanguage from the sixties called META II. I wanted to develop my own version of META II to understand it deeply. RLMeta is also inspired by OMeta (another META II derivative).

RLMeta is a programming language in which you write grammars. Grammars have rules that specify how to match objects from an input stream and specify what should happen when objects are matched. The RLMeta compiler translates grammars into programs that recognize the objects specified in the grammar and evaluates the semantic actions when the objects are matched.

Interpreting expressions

How can RLMeta be used to give meaning to arithmetic expressions of the kind presented in the introductory example? Here is a grammar:

Calculator {
  expression =
    | additive
  additive =
    | multitive:x '+' additive:y -> add(x y)
    | multitive
  multitive =
    | digit:x '*' multitive:y    -> mul(x y)
    | digit
  digit =
    | '0'-'9':x                  -> int(x)
}

This grammar is called Calculator. It has four rules. The first rule says that an expression is an additive. The second rule says that an additive is either a multitive followed by the character '+' followed by another additive or just a multitive. The second case is only tried if the first does not match. The third rule says that a multitive is either a digit followed by the character '*' followed by another multitive or just a digit. The fourth rule says that a digit is a character in the range 0-9. The : followed by a name binds the result of a match to a variable. The expressions to the right of -> are semantic actions. They specify what should happen on a match. They can refer to variables. In this grammar they say that whenever an additive is matched, call the host language function add with the left and right side, and whenever a multitive is matched, call the host language function mul with the left and right side, and whenever a digit is matched, call the host language function int with the digit character. The host language function int converts a digit character to an integer and the add and mul functions perform addition and multiplication.

This grammar describes how to recognize an arithmetic expression in a sequence of characters. Precedence is encoded by the order of the rules. An additive is x1 + x2 + x3 + .. where the xes are multitives. Therefore multiplication is performed before addition. It gives meaning to the expression by calling host language functions when parts are matched.

When the calculator grammar is fed to the RLMeta compiler, a program is output that is an interpreter for arithmetic expressions.

More specifically, this program is a Python class that implements interpretation of arithmetic expressions. The class depends on a support library and also on the host language functions that were called from the grammar (add, mul, and int). Host language refers to the language that grammars are compiled to. In this case Python. The pieces must be assembled to form an executable program. Here is a template for the final Python file that implements a read-eval-print loop (REPL) for arithmetic expressions:

from operator import add, mul

$support_py

$calculator_py

if __name__ == "__main__":
    calculator = Calculator()
    while True:
        line = raw_input("> ")
        result = calculator.run("expression", line)
        print(result)

First the host language functions are imported (int is always available). Then the support library and the compiled calculator grammar snippets are inserted. Finally the main method which is the REPL is implemented. Compiled grammars are used by instantiating them and calling their run method with the name of the rule and the input object. This template is rendered with a Bash script:

#!/bin/bash

set -e

cd "$(dirname "$0")"

support_py=$(python ../rlmeta/rlmeta.py --support)
calculator_py=$(python ../rlmeta/rlmeta.py < calculator.rlmeta)

cat <<EOF
<<python file template>>
EOF

First the set -e directive ensures that the script exits as soon as there is an error. Then the directory is changed to the one where the compile script lives. Then the output of two calls to the RLMeta compiler (rlmeta.py) are captured in two variables. The RLMeta compiler reads a grammar from stdin and writes a Python class to stdout. If the --support flag is given, it writes the support library to stdout instead. The command < file syntax redirects the contents of the file to the command's stdin. Finally the Python file template is rendered and written to stdout using a here document which has access to the previously captured variables.

Example usage on the command line:

$ python <(./calculator/compile.sh)
> 1+2*3
7

The compile script writes a Python file to stdout. The <(command) syntax is process substitution and turns the output of the command into a temporary file which can then be run with Python.

In this example, the input stream to the calculator becomes a list of characters:

['1', '+', '2', '*', '3']

When the calculator matches the expression, the following host language functions will be called:

add(int('1'), mul(int('2'), int('3')))

Compiling expressions

The previous example relied on host language functions to perform addition and multiplication. The meaning of an expression was defined in terms of the meaning of Python functions. To understand what an expression means, you need to understand how Python implements those functions. The next example compiles an expression down to a kind of assembly language that eliminates the need for Python.

For this compilation, two grammars are written: a parser and a code generator. The parser looks similar to the calculator grammar but instead of evaluating the expression, it creates an abstract syntax tree (AST) describing the expression:

Parser {
  expression =
    | additive
  additive =
    | multitive:x '+' additive:y -> ["add" x y]
    | multitive
  multitive =
    | digit:x '*' multitive:y    -> ["mul" x y]
    | digit
  digit =
    | '0'-'9':x                  -> ["digit" x]
}

The bracket notation in the semantic actions creates lists. Nodes in the AST are represented as lists where the first item is a string denoting the type of node.

The code generator takes as input an AST from the parser and generates assembly language code for an imaginary stack machine:

CodeGenerator {
  ast =
    | ["add" ast:x ast:y] -> { x y "add"     "\n" }
    | ["mul" ast:x ast:y] -> { x y "mul"     "\n" }
    | ["digit" .:x]       -> {     "push " x "\n" }
}

This grammar has only one rule: ast. It says that an AST is either a list that starts with the string 'add', or a list that starts with the string 'mul', or a list that starts with the string 'digit'. The add and mul cases recursively match AST nodes as their left and right side whereas the digit matches anything (.) which is the digit stored in the AST node. The semantic actions in this grammar generate string output which is denoted by the curly braces. When a digit AST node is matched, the string 'push [digit]\n' is generated. It instructs the stack machine to push the given digit to the stack. For add and mul, instructions for the operands are first output followed by an 'add\n' or 'mul\n' instruction. They instruct the stack machine to pop two numbers off the stack, add or multiply them, and push the result.

This grammar describes how to recognize and AST in a sequence of objects. It gives meaning to the AST by generating assembly language code when AST nodes are matched.

When the expression grammars are fed to the RLMeta compiler, programs are output whose combination is a compiler for arithmetic expressions.

Here is a template for the final Python file that implements a REPL for arithmetic expression compilation:

import sys

$support_py

$parser_py

$codegenerator_py

if __name__ == "__main__":
    parser = Parser()
    codegenerator = CodeGenerator()
    while True:
        line = raw_input("> ")
        ast = parser.run("expression", line)
        assembly = codegenerator.run("ast", ast)
        sys.stdout.write(assembly)

First the sys module is imported because the main method needs it. Then the support library, compiled parser grammar, and compiled code generator grammar snippets are inserted. Finally the main method which is the REPL is implemented. The output of the parser is fed to the code generator and its output is finally written to stdout. This template is rendered with a Bash script:

#!/bin/bash

set -e

cd "$(dirname "$0")"

support_py=$(python ../rlmeta/rlmeta.py --support)
parser_py=$(python ../rlmeta/rlmeta.py < parser.rlmeta)
codegenerator_py=$(python ../rlmeta/rlmeta.py < codegenerator.rlmeta)

cat <<EOF
<<python file template>>
EOF

First the set -e directive ensures that the script exits as soon as there is an error. Then the directory is changed to the one where the compile script lives. Then the output of three calls to the RLMeta compiler are captured in three variables. Finally the Python file template is rendered and written to stdout.

Example usage on the command line:

$ python <(./expression/compile.sh)
> 1+2*3
push 1
push 2
push 3
mul
add
> 1*2+3
push 1
push 2
mul
push 3
add

In the first example, the input stream to the parser becomes a list of characters (same as for the calculator):

['1', '+', '2', '*', '3']

The input stream to the code generator becomes a list with a single object which is a list (the root AST node):

[
    [
        'add',
        ['digit', '1'],
        [
            'mul',
            ['digit', '2'],
            ['digit', '3']
        ]
    ]
]

The generated assembly language code is much closer to CPU instructions than the Python-based interpreter. A grammar could be written to convert these assembly instructions to assembly instructions of a real CPU. But I will not do that here. The point is that the meaning of an expression can be described by a series of transformations that eventually output machine instructions.

RLMeta implementation

So far I've just given informal descriptions of how RLMeta works. To fully understand how arithmetic expressions are evaluated and compiled, you need to understand how RLMeta is implemented.

The RLMeta compiler translates a grammar to a Python class. This translation is implemented in RLMeta itself. A grammar is, like an expression, translated in two steps: the parser translates grammar syntax to an AST and the code generator translates the AST to a Python class. The generated Python class depends on a support library.

The RLMeta compiler thus comprises three pieces: the parser, the code generator, and the support library.

Parser

This section defines the parser:

Parser {
  <<rules>>
}

Grammar

The top level syntactic element is a grammar. A grammar has a name followed by rules enclosed in curly braces. When this is matched, a Grammar AST node is created containing the name of the grammar and the rule AST nodes:

grammar =
  | name:x space '{' rule*:ys space '}' -> ["Grammar" x ~ys]

Throughout the parser, space is ignored. As a rule of thumb, it is inserted before matching a character sequence (and not before matching other rules).

The * operator after rule means match the preceding expression zero or more times. The result is a list.

The ~ operator in the semantic action means splice the list in-line into the enclosing list. The Grammar AST node thus has the name as element one, the first rule AST node as element two, the second rule AST node as element three, and so on.

Rule

A rule has a name followed by an equal sign followed by a choice. When this is matched, a Rule AST node is created containing the name and the choice AST node:

rule =
  | name:x space '=' choice:y -> ["Rule" x y]

Choice

A choice has sequences separated by vertical bars. Optionally the first sequence can start with a vertical bar to allow all sequence lines to look the same. When this is matched, an Or AST node is created containing the sequence AST nodes:

choice =
  | (space '|')?
    sequence:x (space '|' sequence)*:xs -> ["Or" x ~xs]

The ? operator means match the preceding expression zero or one time.

The result of xs is a list of sequences since the expression inside parenthesis returns the last match (which is a sequence).

Sequence

A sequence has one or more expressions. When this is matched, a Scope AST node is created containing an And AST node containing the expression AST nodes:

sequence =
  | expr:x expr*:xs -> ["Scope" ["And" x ~xs]]

Expression

An expression is one of the following sequences:

expr =
  | expr1:x space ':' name:y -> ["Bind" y x]
  | expr1

The first sequence is an expression of level 1 followed by a colon followed by a name. When this is matched, a Bind AST node is created containing the name and the expression AST node.

The second sequence is an expression of level 1.

Expression of level 1

An expression of level 1 is one of the following sequences:

expr1 =
  | expr2:x space '*' -> ["Star" x]
  | expr2:x space '?' -> ["Or" x ["And"]]
  | space '!' expr2:x -> ["Not" x]
  | expr2

The first sequence is an expression of level 2 followed by an asterisk. When this is matched, a Star AST node is created containing the expression AST node.

The second sequence is an expression of level 2 followed by a question mark. When this is matched, an Or AST node is created containing the expression AST node and an empty And AST node. There is no dedicated AST node for the ? operator, but it is equivalent to matching the expression or zero expressions and'ed.

The third sequence is an exclamation mark followed by an expression of level 2. When this is matched, a Not AST node is created containing the expression AST node.

The fourth sequence is an expression of level 2.

Expression of level 2

An expression of level 2 is one of the following sequences:

expr2 =
  | space '->' hostExpr:x        -> ["SemanticAction" x]
  | name:x !(space '=')          -> ["MatchRule" x]
  | space char:x '-' char:y      -> ["MatchRange" x y]
  | space string:x               -> ["MatchString" x]
  | space charseq:x              -> ["MatchCharseq" x]
  | space '.'                    -> ["MatchAny"]
  | space '(' choice:x space ')' -> x
  | space '[' expr*:xs space ']' -> ["MatchList" ["And" ~xs]]

The first sequence is the characters '->' followed by a host expression. When this is matched, a SemanticAction AST node is created containing the expression AST node.

The second sequence is a name that is not followed by an equal sign (otherwise it would also match the start of a rule). When this is matched, a MatchRule AST node is created containing the name.

The third sequence is a character followed by a dash followed by another character. When this is matched, a MatchRange AST node is created containing the two characters.

The fourth sequence is a string. When this is matched, a MatchString AST node is created containing the string.

The fifth sequence is a character sequence. When this is matched, a MatchCharseq AST node is created containing the character sequence.

The sixth sequence is a dot. When this is matched, a MatchAny AST node is created.

The seventh sequence is an open parenthesis followed by a choice followed by a closing parenthesis. When this is matched, the choice AST node is returned.

The eighth sequence is an open bracket followed by expressions followed by a closing bracket. When this is matched, a MatchList AST node is created containing an And AST node containing the expressions.

Host expression

A host expression is one of the following sequences:

hostExpr =
  | space string:x                           -> ["String" x]
  | space '[' hostExprListItem*:xs space ']' -> ["List" ~xs]
  | space '{' buildExpr*:xs space '}'        -> ["Builder" ~xs]
  | name:x space '(' hostExpr*:ys space ')'  -> ["FnCall" x ~ys]
  | name:x                                   -> ["VarLookup" x]

The first sequence is a string. When this is matched, a String AST node is created containing the string.

The second sequence is an open bracket followed by host expression list items followed by a closing bracket. When this is matched, a List AST node is created containing the list item AST nodes.

A list item is either a host expression preceded by the ~ operator, in which case a ListItemSplice AST node is created containing the expression, or a host expression:

hostExprListItem =
  | space '~' hostExpr:x -> ["ListItemSplice" x]
  | hostExpr

The third sequence is an open curly brace followed by build expressions followed by a closing curly brace. When this is matched, a Builder AST node is created containing the expression AST nodes.

A build expression is either a greater than character, in which case an IndentBuilder AST node is created, or a less than character, in which case a DedentBuilder AST node is created, or a host expression.

buildExpr =
  | space '>' -> ["IndentBuilder"]
  | space '<' -> ["DedentBuilder"]
  | hostExpr

The fourth sequence is a name followed by an open parenthesis followed by host expressions followed by a closing parenthesis. When this is matched, a FnCall AST node is created containing the name and expression AST nodes.

The fifth sequence is a name. When this is matched, a VarLookup AST node is created containing the name.

Character related

Character related rules capture strings, character sequences, and single characters. Inside all of them a few escape codes are possible. When this is matched, the characters inside the delimiters are joined together to create the string:

string    = '"'  (!'"'  innerChar)*:xs '"'  -> join(xs)
charseq   = '\'' (!'\'' innerChar)*:xs '\'' -> join(xs)
char      = '\''  !'\'' innerChar  :x  '\'' -> x
innerChar = '\\' escape | .
escape    = '\\' -> "\\" | '\'' -> "'"
          | '"'  -> "\"" | 'n'  -> "\n"

Name

A name has at least one alphabetic character followed by any number of alphanumeric characters. When this is matched, the individual characters are joined together to create a string:

name      = space nameStart:x nameChar*:xs -> join([x ~xs])
nameStart = 'a'-'z' | 'A'-'Z'
nameChar  = 'a'-'z' | 'A'-'Z' | '0'-'9'

Space

A space is any number of space characters or newlines:

space = (' ' | '\n')*

Code generator

This section defines the code generator and the support library:

CodeGenerator {
  <<rules>>
}

<<classes>>

Note on target language

The choice of Python as the target language for code generation is an implementation detail. A different target language could easily be used. Say for example that you would like to use RLMeta in a web browser. In that case JavaScript must be used as the target language. RLMeta could be ported to JavaScript by modifying the code generator and the support library.

Parsing algorithm

The parsing algorithm that RLMeta implements is based on parsing expression grammars (PEG), but is extended to match arbitrary objects, not just characters. Another way to describe the parsing algorithm is that it is a recursive descent parser with backtracking an memoization. Details of the algorithm is shown in the remainder of this section.

Structure of code generator

The code generator has two main rules: ast and astFnBody:

ast =
  <<ast>>
  | astFnBody:x -> { "(lambda:\n" > x < "\n)" }
astFnBody =
  <<astFnBody>>

Sometimes generated code for an AST node should be wrapped in a lambda. Those AST nodes are added to the astFnBody rule. The astFnBody rule is not strictly needed, but without it, many rules would have to wrap its output in a lambda.

The greater than and less than characters in the string output expression cause an indent and a dedent like this:

(lambda:
    x
)

Grammar

When a Grammar AST node is matched, a Python class inheriting _Grammar is generated:

| ["Grammar" .:x ast*:ys] -> { "class " x "(_Grammar):\n" > ys < }

The name of the class is the same as the name of the grammar and the child AST nodes are assumed to generate methods in the class.

The _Grammar class is defined in the support library:

class _Grammar(object):

    <<_Grammar>>

Names of support classes start with underscore to not collide with generated grammar names (which can not contain underscores).

Rule

When a Rule AST node is matched, a Python method with a name prefixed with _rule_ is generated:

| ["Rule" .:x ast:y] -> { "\ndef _rule_" x "(self):\n" > "return " y "()\n" < }

The method name ends with the same name as the rule. The child AST node is assumed to generate a matcher. A matcher is a function that tries to match objects from the input stream and return a semantic action if it succeeds or raise an exception if it fails. That function is called from the generated method and the semantic action is returned.

Or

When an Or AST node is matched, a matcher that calls the built-in _or method is generated:

| ["Or" astItems:x] -> { "self._or([" x "])" }

Rules to generate a list of items:

astItems = astItem*:xs -> { "\n" > xs < }
astItem  = ast:x       -> { x ",\n"     }

The generated string is wrapped in a lambda because the code is added to the astFnBody rule and will thus look like this:

(lambda:
    self._or([
        matcher1,
        matcher2,
        ...
    ])
)

The _or method expects a list of matchers which are tried in sequence:

def _or(self, matchers):
    original_stream = self._stream
    for matcher in matchers:
        try:
            return matcher()
        except _MatchError:
            self._stream = original_stream
    original_stream.fail("no choice matched")

The result of the first succeeding matcher is returned. The input stream is stored in _stream. Streams are immutable, so resetting the stream upon failure is just a matter of saving and restoring _stream. _MatchError is the name of the exception that is raised when a match fails. Streams have a fail method that generates that exception and adds context to it that is useful for error reporting.

Scope

When a Scope AST node is matched, a matcher that creates a new scope is generated:

| ["Scope" ast:x] -> { "(lambda _vars:\n" > x < "()\n)(_Vars())" }

A scope is a set of variables that do not interfere with variables in other scopes. The name _vars is used to refer to variables in the current scope. The child AST node is assumed to generate a matcher which is called to return a semantic action. The generated string will thus look like this:

(lambda:
    (lambda _vars:
        matcher()
    )(_Vars())
)

The _Vars class is a subclass of a Python dictionary:

class _Vars(dict):

    <<_Vars>>

And

When an And AST node is matched, a matcher that calls the built-in _and method is generated:

| ["And" astItems:x] -> { "self._and([" x "])" }

The _and method expects a list of matchers which are called in sequence:

def _and(self, matchers):
    result = None
    for matcher in matchers:
        result = matcher()
    return result

The result of the last matcher is returned.

Bind

When a Bind AST node is matched, a matcher that binds the name to a value in the current scope is generated:

| ["Bind" .:x ast:y] -> { "_vars.bind(" repr(x) ", " y "())" }

The child AST node is assumed to generate a matcher which is called to make the value a semantic action.

The bind method stores and returns a value with the given name:

def bind(self, name, value):
    self[name] = value
    return value

Star

When a Star AST node is matched, a matcher that calls the built-in _star method is generated:

| ["Star" ast:x] -> { "self._star(" x ")" }

The _star method expects a matcher and calls it for as long as it succeeds:

def _star(self, matcher):
    result = []
    while True:
        original_stream = self._stream
        try:
            result.append(matcher())
        except _MatchError:
            self._stream = original_stream
            return _SemanticAction(lambda: [x.eval() for x in result])

The return value is a semantic action. When evaluated, it returns a list of all match results evaluated.

A semantic action is a wrapper for a function:

class _SemanticAction(object):

    def __init__(self, fn):
        self.fn = fn

    def eval(self):
        return self.fn()

Its eval method calls the function. The reason for wrapping semantic actions in functions is to prevent them from being evaluated before a parse is complete. If a parse fails, no semantic actions are evaluated.

Not

When a Not AST node is matched, a matcher that calls the built-in _not method is generated:

| ["Not" ast:x] -> { "self._not(" x ")" }

The _not method expects a matcher and succeeds if that matcher fails:

def _not(self, matcher):
    original_stream = self._stream
    try:
        matcher()
    except _MatchError:
        return _SemanticAction(lambda: None)
    else:
        original_stream.fail("match found")
    finally:
        self._stream = original_stream

It never consumes any input. The original stream is always reset.

Semantic action

When a SemanticAction AST node is matched, a matcher that creates a _SemanticAction is generated:

| ["SemanticAction" ast:x] -> { "_SemanticAction(lambda: " x ")" }

The child AST node is assumed to generate a Python expression that will be returned when the semantic action is evaluated.

Match rule

When a MatchRule AST node is matched, a matcher that calls the built-in _match_rule is generated:

| ["MatchRule" .:x] -> { "self._match_rule(" repr(x) ")"}

The _match_rule method expects the name of the rule to call:

def _match_rule(self, rule_name):
    key = (rule_name, self._stream.position())
    if key in self._memo:
        result, _, self._stream = self._memo[key]
    else:
        start = self._stream
        result = getattr(self, "_rule_{}".format(rule_name))()
        end = self._stream
        self._memo[key] = (result, start, end)
    return result

If the given rule has been matched at the current position before, the memoized result is returned and the input stream is changed to where the previous match ended. If there has been no previous match, the rule is matched by calling the method. The result of the match is stored in the memoization table for later retrieval.

Match range

When a MatchRange AST node is matched, a matcher that calls the built-in _match_range is generated:

| ["MatchRange" .:x .:y] -> { "self._match_range(" repr(x) ", " repr(y) ")" }

The _match_range method expects two objects defining a range to match:

def _match_range(self, start, end):
    original_stream = self._stream
    next_objext, self._stream = self._stream.next()
    if next_objext >= start and next_objext <= end:
        return _SemanticAction(lambda: next_objext)
    else:
        original_stream.fail(
            "expected range {!r}-{!r} but found {!r}".format(start, end, next_objext)
        )

If the next object from the input stream is in that range, it succeeds, otherwise it fails.

Match string

When a MatchString AST node is matched, a matcher that calls the built-in _match_string is generated:

| ["MatchString" .:x] -> { "self._match_string(" repr(x) ")" }

The _match_string method expects the string to match:

def _match_string(self, string):
    original_stream = self._stream
    next_object, self._stream = self._stream.next()
    if next_object == string:
        return _SemanticAction(lambda: string)
    else:
        original_stream.fail(
            "expected {!r} but found {!r}".format(string, next_object)
        )