QuickParse: a Java library to quickly build parsers

QuickParse is a single-jar library that allows to programmatically define parsers for formal languages. Differently from parsers generators, or compilers compilers, QuickParse allows to maintain and change grammars directly in the code, without starting external generation processes. The parser is built at runtime, at the moment the program requires it, precisely.

QuickParse exposes some Java classes and interfaces that define the main components of a compiler:

• Grammar: a class that represents a grammar and describes the language constructs and tokens.

• Parser: an interface that must be implemented to provide different parsing strategies. The user can provide its own parser implementation.

• RecursiveDescentParser: The default implementation of the Parser interface, which provides a scanner-less, top-down, recursive parsing strategy, optimized through an LRU (Least Recently Used) cache.

• SyntaxTreeVisitor: interface used to visit the full syntax tree generated by a parser. The user can directly implement this interface to do semantics analysis of a syntax tree.

• Interpreter: a simple interface that can be implemented to provide different and high-level interpretation strategies of syntax trees, beyond and alternatively to syntax tree visitor.

• SimpleInterpreter: a default implementation of Interpreter that allows to build an interpreter by using Lambda Expressions.

• TypedInterpreter: the highest-level interpreter implementation provided by QuickParse. It allows to create classes with annotated methods to analyze syntax trees. It allows a strong dynamic type checking for the objects produced during the analysis process.

Documentation

For more details about classes and their usage, see the JavaDoc.

Example use case

The following class implements a very simple expressions evaluator that supports addition, subtraction, multiplication, division and negation. The example, which uses the SyntaxTreeVisitor interface for semantics analysis, can be found in the "QuickParse-Examples" module.

package example.quickparse;

import quickparse.grammar.Grammar;
import quickparse.grammar.Rule;
import quickparse.parsing.Parser;
import quickparse.parsing.RecursiveDescentParser;
import quickparse.parsing.exception.ExpectedSymbolsException;
import quickparse.parsing.exception.UnexpectedSymbolException;
import quickparse.parsing.syntaxtree.ConstructNode;
import quickparse.parsing.syntaxtree.SyntaxTreeVisitor;
import quickparse.parsing.syntaxtree.TokenNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ExpressionsWithVisitor {
    private static Grammar grammar = Grammar.create()
            .ignorePatterns("\\s") // ignore white space characters
            .addRule(Rule.head("expression").produces("level1"))

            // level 1 of operator precedence: addition, subtraction
            .addRule(Rule.head("level1").produces("level1-tail"))
            .addRule(Rule.head("level1-tail").produces("level2", "level1-operator:[\\+\\-]", "level1-tail"))
            .addRule(Rule.head("level1-tail").produces("level2"))

            // level 2 of operator precedence: multiplication, division
            .addRule(Rule.head("level2").produces("level2-tail"))
            .addRule(Rule.head("level2-tail").produces("level-final", "level2-operator:[\\*\\/]", "level2-tail"))
            .addRule(Rule.head("level2-tail").produces("level-final"))

            // final level of operator precedence
            .addRule(Rule.head("level-final").produces("term"))

            // expression term definition
            .addRule(Rule.head("term").produces("number:[\\+\\-]?[0-9]*\\.?[0-9]+([eE][\\+\\-]?[0-9]+)?"))
            .addRule(Rule.head("term").produces(":\\(", "expression", ":\\)"))
            .addRule(Rule.head("term").produces("unary-operation"))

            // unary operations
            .addRule(Rule.head("unary-operation").produces("negative"))
            .addRule(Rule.head("unary-operation").produces("positive"))
            .addRule(Rule.head("negative").produces(":\\-", "term"))
            .addRule(Rule.head("positive").produces(":\\+", "term"))

            .build();

    private static Parser parser = new RecursiveDescentParser(grammar);

    private static class ExpressionVisitor implements SyntaxTreeVisitor{
        LinkedList<List<Object>> stack = new LinkedList<>();
        List<Object> currentLevel = new ArrayList<>();
        double value;

        public double getValue() {
            return value;
        }

        @Override
        public void token(TokenNode node) {
            switch (node.name){
                case "number":
                    value = Double.parseDouble(node.value.toString());
                case "level1-operator":
                case "level2-operator":
                    currentLevel.add(value);
                    currentLevel.add(node.value.toString());
                    break;
            }
        }

        @Override
        public void enterConstruct(ConstructNode node) {
            switch (node.name){
                case "level1":
                case "level2":
                    stack.push(currentLevel);
                    currentLevel = new ArrayList<>();
                    break;
            }
        }

        @Override
        public void exitConstruct(ConstructNode node) {
            switch (node.name){
                case "negative":
                    value = -value;
                    break;
                case "level1":
                case "level2":
                    currentLevel.add(value);
                    value = (double) currentLevel.get(0);
                    for(int i = 1; i< currentLevel.size(); i++){
                        String operator = currentLevel.get(i).toString();
                        // operators precedence is encoded in the grammar:
                        // executes the operations in the order they are presented
                        switch(operator){
                            case "+":
                                value += (double) currentLevel.get(++i);
                                break;
                            case "-":
                                value -= (double) currentLevel.get(++i);
                                break;
                            case "*":
                                value *= (double) currentLevel.get(++i);
                                break;
                            case "/":
                                value /= (double) currentLevel.get(++i);
                                break;
                        }
                    }
                    currentLevel = stack.pop();
                    break;
            }
        }
    }

    private static Double evaluate(CharSequence expression) throws UnexpectedSymbolException, ExpectedSymbolsException {
        return parser.parse(expression)
                .accept(new ExpressionVisitor())
                .getValue();
    }

    public static void main(String[] args) throws ExpectedSymbolsException, UnexpectedSymbolException {
        String expression = "2+3*(4+2)*2";
        System.out.println(expression + " = " + evaluate(expression));
    }
}