SlopeJ8 - Parser Construction for Java 8 and above

- A quick tutorial

1. Introduction

Despite the fact that several compiler compilers are available, it is not that trivial to define a new language using such tools. The reason for it is, that such tools require an additional tool chain that needs to be integrated into the development environment and some understanding how such tool chains work.

Slope's goal of is to define formal languages - i.e. parsers - in a relatively simple way: directly within your programming language. Thereto, Slope defines a set of classes and a set of idioms how these classes should be used.

Note: Slope's goal is to be easy to use, not to be fast. I.e. there is no way that a parser definition using Slope is able to compete with a parser definition based on a tool such as ANTLR.

2. Getting Slope

You can download SlopeJ8 from bitbucket: https://bitbucket.org/shanenberg/slope_j8.

The code of this tutorial can be found under: slope.j8.lib.toyexamples.TestLangParsing, respectively slope.j8.lib.toyexamples.TestLangParsingWithParseTree.

3. Parser Construction using Slope

In order to define a parser, two things need to be done: first, you define the scanner, second you define the parser.

3.1 Defining a Scanner

The first step in a parser definition is the scanner definition. The scanner's task is

1. to divide the characters from the incoming stream into a number of tokens, and
2. to define separators, i.e. tokens that are used to separate other tokens.

In slope, a scanner is something that uses a class that extends the class slowscane.Tokens. Typically, you start defining a scanner by defining the separators and then the other tokens.

    public class TestLangTokens extends slowscane.Tokens {

        // here appear additional lines for separators, keywords and other tokens

    }

@Keyword public TokenReader<String> Int() { return lib.KEYWORD_Int; }

@Token public TokenReader<String> JAVA_IDENTIFIER() { return lib.JAVA_IDENTIFIER; }

@Token public TokenReader<?> OBRACKET() { return lib.OPEN_BRACKET; }

@Token public TokenReader<?> CBRACKET() { return lib.CLOSED_BRACKET; }

3.1.2 Using (and Testing) the Scanner

Slope's convention for testing is, that the test class is an outer class for the scanner (and the parser) - however, it is not necessary to follow this guideline if you consider it annoying. Following Slope's convention, you define the test class as an outer class and the scanner as a static inner class (make it static in order to make it extensible).

You can use the scanner by creating an instance of slowscane.Scanner. The constructor expects a tokens object (such as the one that has just been created) and a position stream. It is quite likely that you will test your scanner first with a simple String object. In that case, you create an instance of slowscane.streams.StringBufferStream by passing a String object to it.

Now it is possible to read the tokens from the tokenstream and define some tests on them.

public void testScan() {

TokenStream<?> ts = scan("( \n ( (Int ) )");

assertEquals("(", ts.get(0).getValue().toString());

assertEquals("(", ts.get(1).getValue().toString());

assertEquals("(", ts.get(2).getValue().toString());

assertEquals("Int", ts.get(3).getValue().toString());

}

The previous tests check, whether the tokens are as expected: three opening brackets followed by the keyword "Int" (two more brackets appear, but this is not tested in the code).

Ok, that's it for the scanner definition. Now we need to define a parser.

3.2 Defining a Parser

In slope a parser is a inner class of the previously defined tokens definition class. The parser's task is to describe rules about the ordering of the tokens in the tokenstream as returned by the scanner.

Traditionally, languages defined by parsers are described using context-free grammars. For example, the language that is to be defined in this small tutorial is defined by the grammar

<Expression> -> "Int" | JavaIdentifier | <BracketExpression>⁺

    <BracketExpression> -> "(" <Expression> ")" 

The start symbol of this grammar is <Expression> (Note: What exactly a JavaIdentifier is, is not defined in the grammar. Also, the grammar does not say a word about possible separators). The grammar defines a language that consists either of the keyword "Int", a Java identifier or a bracket expressions that is allowed mulitple times. A bracket expression consists of an opening bracket, an expression and a closing bracket.

3.2.1 Defining the Parser Class

The parser class is a subclass of slope.Parser<TOKENS extends Tokens>. The class consists of a number of methods that describe the rules of the grammar to be implemented by the parser. Each method has the following characteristics:

1. The return type of a rule method is slope.j8.Rule,
2. The body of the method creates and returns a lambda expression.
3. The body makes use of predefined methods from the parser (each of them return rule objects themselves)
   1. TOKEN: The method takes a token method as parameter which must match the following token from the stream.
   2. AND: The method AND combines all rules passed as parameters via concatenation (i.e. all passed rules must match one after another)
   3. OR: The method OR combines each passed rule via a union (i.e. at least one of the passed rules much match)
   4. NFOLD: The passed rule (one rule!) matches at least one time, but can also match multiple times.
   5. set: This method is required to define parse trees and will be explained later.

The class declaration of the parser can already be done as follows:

// This is the outer testing class in the example

public class TestLangParsing extends TestCase {

    // This is the tokens class which is the outer class for the parser

    public static class TestLangTokens extends slowscane.Tokens {

        // This is the parser class

        public class TestLangParser extends Parser<TestLangTokens> {

            // Here appear the rule methods

        }

    }

}

3.2.2 Using TOKEN()

In case we want to define a rule that says that the token as previously defined by the method Int() should be accepted (and if we want to call this method KEYWORD_INT()), we write the following method in the parser class:

Rule KEYWORD_Int() { return () -> 

TOKEN(Int());

}

The interesting part of the body is the use of TOKEN() with parameter Int(). The rule says that the next token from the stream must be something as defined by the token method Int(). The rule method has the name KEYWORD_Int() and can be used by other rule methods in the parser class. Note that the rule method returns a lambda expression (the body of the method starts with "return () ->").

We create a similar rule method for the identifier:

Rule IDENTIFIER() { return () ->

TOKEN(JAVA_IDENTIFIER());

}

3.2.3 Using OR()

In order to define a rule <Expression>, we define a method in the same way. The rule says, that a simple expression is either the keyword "Int", an identifier or a N_TIMES_BRACKET_EXPRESSION. What a bracket expression is, isn't defined yet, but the other two parts (KEYWORD_Int and IDENTIFIER) are already known:

Rule EXPRESSION() { return () ->

OR(KEYWORD_Int(), IDENTIFIER(), N_TIMES_BRACKET_EXPRESSION());

}

3.2.4 Using AND()

The rule <BracketExpression> concatenates an opening bracket (which is a token), an expression, and a closing bracket (which is a token).

Rule BRACKET_EXPRESSION() { return () ->

AND(TOKEN(OBRACKET()), EXPRESSION(), TOKEN(CBRACKET()));

}

3.2.5 Using NFOLD()

We still haven't defined the rule N_TIMES_BRACKET_EXPRESSION(). For defining this rule, we use the method NFOLD. The method NFOLD takes a single rule as a parameter (which might be an AND or an OR rule) and says that the passed rule might appear multiple times (but at least once).

Rule N_TIMES_BRACKET_EXPRESSION() { return () ->

NFOLD(BRACKET_EXPRESSION());

}

In our example, the passed rule is BRACKET_EXPRESSION(). Hence, this rule might appear multiple times.

3.2.6 Using and Testing the Parser

Again, for testing the parser, slope's guideline is to define an outer class (which already should have been defined before) and define the inner Tokens class as a static class. And again, we assume to test the parser first with a string.

Parsing is achieved by a slope.Parsing object that is instantiated with a tokens object and the string to be parsed (alternatively, a stream can be passed). Then, the method parse() needs to be invoked with the rule that should be used as the start symbol. First, we define in our test class a method check that receives the string to be tested in the following way:

public TreeNode check(String s) {

}

Note that the start rule is passed by instantiating the parser object first and then invoking the rule on it. Now, it is possible to use the method check to test whether a certain word is part of the language defined by the parser.

In fact, check() already returns a parse tree. However, this parse tree is not really useful for the developer. Instead, it is more likely that developers will define their own, customized parse tree which will be explained next. Before defining the parse tree, we copy the file TestLangParsing.java and rename the containing class (and the file) to TestLangParsingWithParseTree.

3.3 Defining a Parse Tree

The convention in Slope is that if a customized parse tree is required (which is probably always the case), that the rule method contains one parameter which is a SetCmd object.

3.3.1 Defining Custom Parse Tree Classes

Before defining how the the parse tree is constructed, we need to define the data structure for the parse tree.

abstract class Expression {}

class IntExpression extends Expression {}

class IdentifierExpression extends Expression { public String identifier; }

class BracketExpression extends Expression { public Expression childExpression; }

class NFOLDBracketExpression extends Expression { public ArrayList<BracketExpression> bracketExpressions = new ArrayList<BracketExpression>();}

The parse tree should return an expression, which is either an IntExpression, an IdentifierExpression, a BracketExpression, or an NFOLDBracketExpression. The class Expression is abstract, because no object should be directly instantiated from it. The IntExpression represent the keyword "Int", i.e. no additional data needs to be stored. The IdentifierExpression should store the identifier. The BracketExpression needs to store the child expression.

3.3.2 Using SetCmd , Cmd, and resultSetting()

If a rule object needs to return a parse tree (respectively a sub-tree), three things are required:

1. the rule method needs a final SetCmd object as parameter (which we call the result setter object),
2. a result object needs to be created,
3. the result object needs to be passed to the result setter

We start with the rule method KEYWORD_Int:.

Rule KEYWORD_Int(SetCmd<Expression> resultSetter) { return () ->

// defines that after a successful parsing, a new IntExpression is delivered to the resultSetter.

TOKEN(Int(), () -> resultSetter.set(new IntExpression()));

}

A SetCmd object provides a method set that receives the value to be set as the result. The type parameter of SetCmd defines the type to be set. Since the rule method KEYWORD_Int is expected to return an expression, the type of the parameter is SetCmd<Expression>. There is a method TOKEN that receives two parameters: the first one is the token to be read, the second is a lambda expression that is executed when the rule method was fulfilled. This lambda expression has the named type Cmd object: a function without any parameter.

Instead of creating a lambda-expression for setting the result, the parser provides a method resultSetting (which requires a result setter and a value as parameters). Using this method, the previous method can be written in different way:

Rule KEYWORD_Int(SetCmd<Expression> resultSetter) { return () ->

// defines that after a successful parsing, the resultSetter receives a new IntExpression.

TOKEN(Int(), setResult(resultSetter, new IntExpression());

}

3.3.3 Passing Token Values to a Parse Tree Node

When we want to do a similar thing for the rule method IDENTIFIER(), we need to create a SetValue object on our own, because the value of the token to be parsed should be assigned to the identifier field of an IdentifierExpression object. We do that by a lambda expression that receives a String as a parameter (because the token reader JAVA_IDENTIFIER() receives a String value) .

3.3.4 Adding Parse Tree Nodes to Collections

A special situation is given for the rule method N_TIMES_BRACKET_EXPRESSION because each time a bracket expression appears it should be added to the collection bracketExpressions within NFOLDBracketExpression. We do that by passing a lambda expression to BRACKET_EXPRESSION that adds the expression to the list. Finally, we set the result by passing the created object expr to the result setter if the rule method has been successfully applied (for which a method NFOLD exists that receives an additional parameter).

Rule N_TIMES_BRACKET_EXPRESSION(SetCmd<Expression> result) {

NFOLDBracketExpression expr = new NFOLDBracketExpression(); return () ->

NFOLD(

BRACKET_EXPRESSION((value) -> expr.bracketExpressions.add(value)),

() -> result.set(expr));

}

It occurs quite often that an object should be added to a list via a set command. Because of that, Slope provides in the parser class a special method that constructs such a set command and receives a list to which a value should be added. Using this method, the code above can be written in a different way:

Rule N_TIMES_BRACKET_EXPRESSION(SetCmd<Expression> resultSetter) {

final NFOLDBracketExpression expr = new NFOLDBracketExpression();

return () ->

NFOLD(

BRACKET_EXPRESSION(addResultSetter(expr.bracketExpressions)),

setResult(resultSetter, expr));

}

3.3.5 Using set()

The rule method that's left is BRACKET_EXPRESSION. It receives the resultSetter, creates a BracketExpression, sets the expressions child and sets the result. A special situation here is, that AND does not support directly a Cmd object as parameter. Instead, we use the method set() defined in the parser that invokes the command object when the rule is applicable.

Rule BRACKET_EXPRESSION(SetCmd<BracketExpression> result) {

BracketExpression expr = new BracketExpression();

return () ->

AND(

TOKEN(OBRACKET()), EXPRESSION((value)-> {expr.childExpression = value;}),

TOKEN(CBRACKET()), set(resultSetting(result, expr));

}

3.3.6 Finally...

The rule method EXPRESSION() now needs to be fixed. It receives an additional SetCmd parameter and simply passes it to it's sub rules.

Rule EXPRESSION(SetCmd<Expression> result) { return () ->

OR(KEYWORD_Int(result), IDENTIFIER(result), N_TIMES_BRACKET_EXPRESSION(result));

}

Now, we are done and need to test the parser.

3.3.7 Testing the Parse Tree

For testing the parser, we now need to pass a result setting object to the expression rule method. We do that by creating a class ResultObject which has an expression as field and creating a SetCmd that receives an expression and sets it to the field.

public class ResultObject {

public Expression expression;

}

public Expression check(String s) {

final ResultObject res = new ResultObject();

SetCmd<Expression> expr = new SetCmd<Expression>() {public void set(Expression value) {

res.expression = value;

}};

TestLangTokens tokens = new TestLangTokens();

Parsing p = new Parsing(tokens, s);

p.parseWithParseTreeConstruction(tokens.new TestLangParser().EXPRESSION(expr));

return res.expression;

}

To make the code above slightly simpler, Slope provides a default ResultObject (with a corresponding result setter). Using such methods, the code above can be reduced to:

public Expression check(String s) {

final ResultObject<Expression> res = new ResultObject<Expression>();

TestLangTokens tokens = new TestLangTokens();

Parsing p = new Parsing(tokens, s);

p.parseWithParseTreeConstruction(tokens.new TestLangParser().EXPRESSION(res.setter));

return res.result;

}

Now, we can run some tests on the parse tree:

public void testParse() {

Expression ex = check("Int");

assertTrue(ex instanceof IntExpression);

ex = check("(Int)");

assertTrue( ex instanceof NFOLDBracketExpression);

NFOLDBracketExpression nbex = (NFOLDBracketExpression) ex;

assertEquals(1, nbex.bracketExpressions.size());

assertTrue(nbex.bracketExpressions.get(0) instanceof BracketExpression);

BracketExpression bex = (BracketExpression) nbex.bracketExpressions.get(0);

assertTrue(bex.childExpression instanceof IntExpression);

}

The code of this tutorial can be found under: slope.j8.lib.toyexamples.TestLangParsing, respectively slope.j8.lib.toyexamples.TestLangParsingWithParseTree.

4 Some final notes

4.1 How Slope works / problems with OR

Slope works in a greedy way: whenever from Slope's perspective a rule is fulfilled, it just assumes that this rule matches and Slope does not try any alternative. This is important to understand when a rule such as

    <something> -> ("x" "y") | ("x" "y" "z")

will be checked: if the first two letters are x and y, Slope will not try the second branch (because the first branch can be read from the token stream). To overcome such a problem, simply changing the ordering in the rule solves the problem:

<something> -> ("x" "y" "z") | ("x" "y")

4.2 Never assign values directly

For the parse tree construction, there is hardly any case where a value can be directly set without using a command object. Slope first constructs the internal parse tree and then walks over it in order to evaluate the command objects. I.e. setting an object directly will not wait until the parse tree is constructed.

5 Etc.

If you have any questions or comments, just leave a message or write a mail to me (stefan.hanenberg@gmail.com).