Filip Strömbäck

• Start
• Research
• C++ puzzles
• Code size

It's alive!

Since I just got the parser working properly in the compiler, I thought I would explain a little more in depth how the parsing works, and how it interacts with the rest of the compiler.

The first thing that happens when the compiler tries to make sense out of an input string is to load one or more syntax files. The idea is that the compiler will look at the file extension and load syntax from the lang.<ext> package and use the information found in this package to parse the file. This is not automated yet, so the exact structure is not fixed. It should for example be possible for a language implementation to intervene before the parser is called, and optionally implement the entire parsing itself instead of relying on the default implementation. But like I said, this is something that is yet to be planned.

What happens next is that the input string is passed to the parser together with the loaded syntax. The parser will then output an abstract syntax tree. What is unusual with my approach is that this abstract syntax tree is not exposed outside the parser itself, instead the syntax rules are annotated with function calls. These functions will be called by the compiler to ultimatley build a syntax tree out of user-defined types.

Type preprocessor

Since the runtime has to call functions defined in the syntax definitions, we need some way of looking up functions from a string. Unfortunatley, C++ does not provide any reflection features that we can use to look up functions from strings. Ie, we need a function like this:

void *lookupFunction(const string &str);

This can be implemented by having a big lookup-table somewhere. But it is tedious to keep this updated manually. Therefore, I have written a small pre-processor that generates this table for me based on which classes and functions are marked in the C++ source code. Then we can simply parse this table at program startup and fill in the type information in the internal representation of loaded packages.

For example: The functions supporting the syntax in lang.simple looks like this:

// Tells the pre-processor which package to place the types in.
STORM_PKG(lang.simple);

class SExpr : public Object {
    STORM_CLASS;
public:
    STORM_CTOR SExpr(Type *t);
};

class SScope : public Object {
    STORM_CLASS;
public:
    STORM_CTOR SScope(Type *t);
    void STORM_FN expr(SExpr *expr);
};

SExpr *STORM_FN sOperator(SExpr *lhs, SExpr *rhs, Str *op);
SExpr *STORM_FN sVar(Str *op);
SExpr *STORM_FN sNr(Str *op);

Here, STORM_PKG tells the preprocessor that all subsequent types and function declarations are to be placed in the package lang.simple in this case. All these keywords are macros in C++ that expand to nothing, or some small boilerplate. STORM_FN will for example expand to __cdecl to ensure that the correct calling convention for functions is used.

The pre-processor will then generate something like this:

{ Name(L"lang.simple"), L"SScope", Name(L"SScope"), L"__ctor", list(1, Name(L"Type")), address(&create1<storm::SScope>) },
{ Name(L"lang.simple"), L"SScope", Name(), L"expr", list(1, Name(L"SExpr")), address(&storm::SScope::expr) },
{ Name(L"lang.simple"), null, Name(L"SExpr"), L"sNr", list(1, Name(L"Str")), address(&storm::sNr) },
{ Name(L"lang.simple"), null, Name(L"SExpr"), L"sOperator", list(3, Name(L"SExpr"), Name(L"SExpr"), Name(L"Str")), address(&storm::sOperator) },
{ Name(L"lang.simple"), null, Name(L"SExpr"), L"sVar", list(1, Name(L"Str")), address(&storm::sVar) },

Which is a simple initializer list for a struct containing the package, member-of-type name, result type, name of the function, parameters to the function and finally the function pointer to the actual function to call.

An interesting note about function pointers in C++ is that pointers to member functions cannot be casted to void * without some tricks. In Visual Studio it will actually work to cast it to a void *& first. Don't ask why... Anyway, that is exactly what the address function is doing.

The parser

Now that we have a way of calling functions, we can start to examine the connection with the actual grammar. Let's consider the following grammar:

DELIMITER => void : " *";

// Expression
SExpr => sOperator(lhs, rhs, op) : SExpr lhs, "\+" op, SExpr rhs;
SExpr => sOperator(lhs, rhs, op) : SExpr lhs, "-" op, SExpr rhs;
SExpr => sVar(v) : "[a-z]+" v;
SExpr => sNr(v) : "[0-9]+" v;

// Root rule with repetitions.
Root => SScope() : "{", (SExpr -> expr - ";",)+ - "}";

And say we want to parse the expression "{ a + b; }", which will produce this abstract syntax tree:

Root => SScope (
  expr -> SExpr (
    lhs -> SExpr (
      v -> a
    ),
    op -> +,
    rhs -> SExpr (
      v -> b
    )
  )
)

The next step is to take another look at the syntax rules and call the functions present there. In this step, think of each rule as a function that will return some value. Each option is then one possible implementation of the function, and which one is used is determined by the result of the pattern matching.

For the root element, the syntax option reads:

Root => SScope() : "{", (SExpr -> expr - ";",)+ - "}";

The part => SScope() : means that the the return value of the function is the result of the expression SScope(). Expressions here are extremely simple, they may only contain function calls or calls to a constructor. In this case we call the constructor of SScope as seen above with no parameters (the Type is added automatically as that is an implementation detail). This object is then bound to the variable me during the rest of the evaluation of the rule.

Since the Root rule contains SExpr -> expr, it means that for each SExpr-rule we found, we should call me.expr(v), where v is the result of the SExpr match. So first we have to evaluate that!

The option in question reads:

SExpr => sOperator(lhs, rhs, op) : SExpr lhs, "\+" op, SExpr rhs;

In the same way as for the root rule, this means that we should call sOperator(lhs, rhs, op) to find the result of this rule. In this case, however, we also have parameters. These have to be evaluated before we can call sOperator. The op parameter is simple, that is just the matched string. But lhs and rhs has to be evaluated first. These are simple rules, we just have to call sVar(v) where v is the string found (a and b in this case).

When we have evaluated lhs and rhs, we can finally call sOperator and since this rule does not contain any ->, we can return the result of sOperator back to the root rule, which can call the me.expr(v) and return to whoever called the parser.

This parsed string is equivalent to the following code:

SScope me = new SScope();
me.expr(
  sOperator(
    sVar("a"),
    sVar("b"),
    "+"
  )
);

What is interesting about this is that you can use this to write programs that are executed when your program is compiled. But now no code can be generated, so you can only run code during compile-time! Not very usefull, but quite cool!

Comments

Alex Telon

Filip Strömbäck

Expr => assignment(lhs, rhs) : Expr lhs, "=", Expr rhs;

Expr => addition(lhs, rhs) : Expr lhs, "\+", Expr rhs;

Expr *createExpr(SyntaxNode &node) {

    if (node is assignment) {

        return assignment(node.lhs, node.rhs);

    } else if (node is addition) {

        return addition(node.lhs, node.rhs);

    }

    // ...

}

Rule : Expr a, "=", Expr b {

    // code here

    return r;

}

Alex Telon

Filip Strömbäck

New comment

You can use GitHub flavored markdown here. Parsed by Parsedown, which does not support all of GitHub's features. For example, specifying the language of code listings is not supported.

© 2014 Filip Strömbäck | Design by www.mitchinson.net | Licensed under a Creative Commons Attribution 3.0 License