Filip Strömbäck

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

Extensible syntax

In the main page, I stated that I want to include custom syntax in Storm. Since this can cause all kinds of unmaintainable code, you may wonder why I still think it is a good idea. This is what I will try to explain here, along with some ideas about how to define the new syntax and semantics.

The main reason I want to include custom syntax in Storm is that I think domain specific languages (DSL) are incredible useful sometimes, even though most large languages, like Java and C++, does not allow it. Having a DSL is something that I think would be very useful in, for example, GUI creation. Currently, the options you have is to write code that either positions your UI elements manually, or write tons of code to set up the correct hierarchy for you. Another option is to write your layout hierarchy in an external language, like XML (for Android). I think that it would be a lot easier to create a simple DSL inside your regular language that generates the code for creating your UI elements from a simple representation that is easy to understand by the programmer. This also simplifies the development environment in some cases, since an external resource compiler is not needed anymore.

Aside from those use-cases, simply extending the language to fit your needs in a clean way is also very pleasant some times. This is something that is possible to some extent in C/C++ through macros. The problem using macros is that they look like functions in most cases, which can be confusing. Using custom syntax instead could improve readability, and since it is a new syntactic construction, it will not be confused with something else easily.

Currently, the Storm compiler uses a variant of EBNF to describe the syntax to use. However, it is somewhat altered from the standard form to be more extensible. The main difference is the absence of the or-operator |. Instead, one defines another rule with the same return-type to accomplish the same effect. To tie these syntax definitions to some underlying implementation, the syntax definitions can be annotated with function calls.

A simple syntax file may look like this:

// Rule for the , delimiter.
DELIMITER => void : " *";

Name => String(name) : "[A-Za-z][^ ]*" name;
Operator => String(op) : "[\+-*/]" op;

// A block.
Block(Scope parent);
Block => Block(parent) : "{", (Statement(me) -> statement, ";", )* "}";

// A statement
Statement(Scope scope);
Statement => Block(block) : Block(scope) block;
Statement => Expression(expr) : Expression(scope) expr;
Statement => Declaration(type, name) : Name type, Name name;

// Expression
Expression(Scope scope);
Expression => Operator(lhs, op, rhs) : Expression(scope) lhs, Operator op, Expression(scope) rhs;
Expression => String(name) : Name name;
Expression => Number(nr) : "[1-9][0-9]*" nr;

This may look quite complex at first glance, since it contains quite a lot of information. First, let me introduce the names for things I have chosen (may not be standard).

• Syntax token: Either a regular expression or a reference to another rule, indicates what is to be matched.
• Option: A set of tokens, this is one line in the source file. Ends with a ;. Similar to rules in BNF, but since my version disallows the OR operator, and these are commonly used to refer to one alternative of a rule I chose this name.
• Rule: A named collection of options.
• Type: Regular types in the Storm language.

Each line has the following syntax:

<rule> => <result> : <token>, ...;

Where rule indicates that this rule is to be appended to the indicated rule, result is either a function call, or a constructor invocation of a Storm type. This is what will eventually be considered the result of the parsing of this rule. Finally there is a list of tokens. These are separated by either a comma (,) or a dash (-). A comma indicates that there should be whitespace between the two tokens (uses the DELIMITER rule). A dash means that nothing is allowed between the two tokens.

To simplify repetition, regex-like syntax is used. You simply enclose the token(s) you want to repeat in parenthesises, and after the closing paren you put either: *,?,+, which has the same meaning as in regular expressions. Currently only one repeat is supported per rule.

All tokens in a rule can be bound to variables or passed to methods of the result object. To bind the matched part of a token to a variable, the variable name is simply written after the token to be matched like this: "[abc]" foo.

To pass it to a method, simply use an arrow like this: "[abc]" -> foo, which will invoke the foo method of the result object.

Each rule may also take one or more parameters. These are declared separatley, in this case always directly above the first rule. This simply means that invoking the rule requires some extra information. This variable may be used freely in all rules like a regular variable.

The execution order of these methods and function calls are sometimes important, which is why there is more than one way of doing it. The function call could be skipped, but that requires the creation of one Storm type per rule (or maybe per rule!), since the each rule will call specific methods on the object. However, this is not enough in all cases, specifically when implementing blocks.

When implementing a block, we want to be able to keep track of what we have currently found inside the block in order to be able to look at the types of expressions in the block. If we were to only use the function/constructor call, we would receive all child rules at once, already processed. Not being able to tell each child what is inside its scope so that the child rules can check the types of subexpressions. This is what is different with the second alternative, it will call a member function once for each child rule in turn, so that you can report different scope information to each of them. To clarify why this is needed, consider the following example:

{
    int a;
    a + a;
}

To be able to correctly see that the addition in the second line is legal, we need to know that the previous statement was actually a variable declaration. What happens when parsing this is that the block rule will start by running the Block(parent) constructor, then for each statement the statement method is called. Since the statement method will be provided the result that is specified in a Expression rule, we have to execute the function in that rule first. In this case the first statement will run Declaration(type, name). When this value is passed to the statement method, we can see that a variable has been declared, and remember that to when the next statement is being created. In this case it is Operator. If operator would like, it can freely look at the scope information to judge if an addition is legal in that case and act accordingly.

Comments

AlexTelon

Göran Rydqvist

Filip Strömbäck

Göran Rydqvist

Alex Telon

Filip Strömbäck

Expr => InlineSql(sql) : "SQL: ", lang.sql.Root sql, " END";

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