Corresponds to 17 arrays

Introduction

I would like to support an array of basic data structures. This article is a continuation of "Corresponding to method calls".

What you want to do with array support

Confirm what you want to do with array support. For example, there is the following program. Create an array on the first line and assign it to the variable ʻar. The second line outputs the array length 3. The third line aims to output the third element " c "` of the array.

var ar = ["a", "b", "c"]
println(ar.size())
println(ar[2])

How to implement

We will consider how to implement it in the order of lexical analysis (Lexer), parser (Parser), and interpreter (Interpreter).

How to implement lexical analysis (Lexer)

Since there is no function to parse [ and ], add it.

How to implement parsing

Implementations for parsing correspond to two syntaxes: one that creates an array and one that accesses elements of an array.

The syntax for generating an array begins with a [ token. Implement it in the lead () method, just as the other first token constructs.

The syntax for accessing the elements of an array is equivalent to the syntax for a function call that takes one argument. Replacing [] of ʻar [2]with() in the program example results in ʻar (2). You can see that they are equivalent because they look like function calls. Implement in the bind () method in the same way as function call parsing.

How to implement the Interpreter

Since the array entity can add elements and get the length by instance method, I decided to use ʻArrayList `. In the previous article, Supports method calls, so you can make use of it.

The processing for the syntax implements array generation and access to array elements. In array generation, ʻArrayList is generated and elements are added. To access the array elements, call the ʻArrayList <Object> :: get () method.

Try to implement in Java

Move on to implementation. About lexical analysis (Lexer), parser (Parser), interpreter (Interpreter) Let's take a look at the changes and additions in order.

Lexer.java

An implementation of Lexer.java.

Add lexical analysis for [ and ].

Add the ʻisBracketStart ()method. Detects[and]`.

Lexer.java


    private boolean isBracketStart(char c) {
        return c == '[' || c == ']';
    }

Add the bracket () method. Parse [ and ] into tokens. kind, which stands for [ and] , should be bracket.

Lexer.java


    private Token bracket() throws Exception {
        Token t = new Token();
        t.kind = "bracket";
        t.value = Character.toString(next());
        return t;
    }

Modify the nextToken () method. Add the call to the added method to // Add. Now you can decompose [ and ] into tokens.

Lexer.java


    public Token nextToken() throws Exception {
        skipSpace();
        if (isEOT()) {
            return null;
        } else if (isSignStart(c())) {
            return sign();
        } else if (isDotStart(c())) {
            return dot();
        } else if (isDigitStart(c())) {
            return digit();
        } else if (isStringStart(c())) {
            return string();
        } else if (isIdentStart(c())) {
            return ident();
        } else if (isParenStart(c())) {
            return paren();
        } else if (isCurlyStart(c())) {
            return curly();
            // Add
        } else if (isBracketStart(c())) {
            return bracket();
        } else if (isSymbolStart(c())) {
            return symbol();
        } else {
            throw new Exception("Not a character for tokens");
        }
    }

That's all for changing Lexer.java.

Parser.java

An implementation of Parser.java.

Add a definition of how it works for the meaning of the token. Added the degree of ordering of [ to // Add. [ Is better than arithmetic operators like + and * Because it strongly connects the left and right tokens, It is 80, which is larger than the degree of + and *.

Parser.java


    public Parser() {
        degrees = new HashMap<>();
        degrees.put(".", 80);
        degrees.put("(", 80);
        degrees.put("[", 80);   // Add
        degrees.put("*", 60);
        degrees.put("/", 60);
        degrees.put("+", 50);
        degrees.put("-", 50);
        degrees.put("==", 40);
        degrees.put("!=", 40);
        degrees.put("<", 40);
        degrees.put("<=", 40);
        degrees.put(">", 40);
        degrees.put(">=", 40);
        degrees.put("&&", 30);
        degrees.put("||", 30);
        degrees.put("=", 10);
        factorKinds = Arrays.asList(new String[] { "digit", "ident", "string" });
        binaryKinds = Arrays.asList(new String[] { "sign", "dot" });
        rightAssocs = Arrays.asList(new String[] { "=" });
        unaryOperators = Arrays.asList(new String[] { "+", "-", "!" });
        reserved = Arrays.asList(new String[] { "function", "return", "if", "else", "while", "break", "var" });
    }

Implements parsing of array generation syntax. Of the lead () method that implements the syntax determined by the first token Added a call to the newArray () method that performs array generation parsing to // Add.

Parser.java


    private Token lead(Token token) throws Exception {
        if (token.kind.equals("ident") && token.value.equals("function")) {
            return func(token);
        } else if (token.kind.equals("ident") && token.value.equals("return")) {
            token.kind = "ret";
            if (!token().kind.equals("eob")) {
                token.left = expression(0);
            }
            return token;
        } else if (token.kind.equals("ident") && token.value.equals("if")) {
            return if_(token);
        } else if (token.kind.equals("ident") && token.value.equals("while")) {
            return while_(token);
        } else if (token.kind.equals("ident") && token.value.equals("break")) {
            token.kind = "brk";
            return token;
        } else if (token.kind.equals("ident") && token.value.equals("var")) {
            return var(token);
        } else if (factorKinds.contains(token.kind)) {
            return token;
        } else if (unaryOperators.contains(token.value)) {
            token.kind = "unary";
            token.left = expression(70);
            return token;
        } else if (token.kind.equals("paren") && token.value.equals("(")) {
            Token expr = expression(0);
            consume(")");
            return expr;
            // Add
        } else if (token.kind.equals("bracket") && token.value.equals("[")) {
            return newArray(token);
        } else {
            throw new Exception("The token cannot place there.");
        }
    }

Added a newArray () method to perform array generation parsing. Collect the elements separated by , into the params of the [ token until the] token is reached. The token type kind is set to newArray. If the last element of the array is empty, like [1,2,], it will be ignored as an element. If an empty element is specified in the middle of the array, such as [1,, 3], The blank token prepared in advance is assigned.

Parser.java


    private Token newArray(Token token) throws Exception {
        token.kind = "newArray";
        token.params = new ArrayList<Token>();
        while(true) {
            if (token().value.equals("]")) {
                consume("]");
                break;
            }
            if (token().value.equals(",")) {
                token.params.add(blank);
                consume(",");
                continue;
            }
            token.params.add(expression(0));
            if (token().value.equals(",")) {
                consume(",");
                continue;
            } else {
                consume("]");
                break;
            }
        }
        return token;
    }

I've added the blank token, which represents the empty element mentioned earlier, to the static field variable.

Parser.java


    public static Token blank;
    static {
        blank = new Token();
        blank.kind = "blank";
        blank.value = "";
    }

Implements array access syntax. Of the bind () method that parses function call syntax etc. Added array access parsing to // Add. Assign the array itself, for example, the token corresponding to ʻar of ʻar [2] to left of ʻoperator corresponding to [ token For right of ʻoperator, assign an index to access, for example, a token corresponding to 2of ʻar [2].

Parser.java


    private Token bind(Token left, Token operator) throws Exception {
        if (binaryKinds.contains(operator.kind)) {
            operator.left = left;
            int leftDegree = degree(operator);
            if (rightAssocs.contains(operator.value)) {
                leftDegree -= 1;
            }
            operator.right = expression(leftDegree);
            return operator;
        } else if (operator.kind.equals("paren") && operator.value.equals("(")) {
            operator.left = left;
            operator.params = new ArrayList<Token>();
            if (!token().value.equals(")")) {
                operator.params.add(expression(0));
                while (!token().value.equals(")")) {
                    consume(",");
                    operator.params.add(expression(0));
                }
            }
            consume(")");
            return operator;
            // Add
        } else if (operator.kind.equals("bracket") && operator.value.equals("[")) {
            operator.left = left;
            operator.right = expression(0);
            consume("]");
            return operator;
        } else {
            throw new Exception("The token cannot place there.");
        }
    }

That's all for changing Parser.java.

Interpreter.java

An implementation of Interpreter.java.

ʻExpression () method change. It is a process that branches according to the meaning (kind) of the token that represents the expression. Under // Add, Call the blank ()method for empty elements, Call thenewArray () method for array generation, Added ʻaccessArray () method call for array access.

Interpreter.java


    public Object expression(Token expr) throws Exception {
        if (expr.kind.equals("digit")) {
            return digit(expr);
        } else if (expr.kind.equals("string")) {
            return string(expr);
        } else if (expr.kind.equals("ident")) {
            return ident(expr);
            // Add
        } else if (expr.kind.equals("blank")) {
            return blank(expr);
            // Add
        } else if (expr.kind.equals("newArray")) {
            return newArray(expr);
            // Add
        } else if (expr.kind.equals("bracket")) {
            return accessArray(expr);
        } else if (expr.kind.equals("func")) {
            return func(expr);
        } else if (expr.kind.equals("fexpr")) {
            return fexpr(expr);
        } else if (expr.kind.equals("paren")) {
            return invoke(expr);
        } else if (expr.kind.equals("sign") && expr.value.equals("=")) {
            return assign(expr);
        } else if (expr.kind.equals("unary")) {
            return unaryCalc(expr);
        } else if (expr.kind.equals("sign")) {
            return calc(expr);
        } else if (expr.kind.equals("dot")) {
            return dot(expr);
        } else {
            throw new Exception("Expression error");
        }
    }

Added a blank () method for empty elements. It simply returns null.

Interpreter.java


    public Object blank(Token token) {
        return null;
    }

Added newArray () method for array generation. After generating ʻArrayList `and adding an element, it returns it.

Interpreter.java


    public Object newArray(Token expr) throws Exception {
        List<Object> a = new ArrayList<>();
        for (Token item : expr.params) {
            a.add(value(expression(item)));
        }
        return a;
    }

Changed the value () method of the method that guarantees that the argument is a value. The first // Add now allows ʻArrayList as a value. The next// Add now allows null` as a value.

Interpreter.java


    public Object value(Object value) throws Exception {
        if (value instanceof Integer) {
            return value;
        } else if (value instanceof String) {
            return value;
            // Add
        } else if (value instanceof List<?>) {
            return value;
            // Add
        } else if (value == null) {
            return value;
        } else if (value instanceof Func) {
            return value;
        } else if (value instanceof Variable) {
            Variable v = (Variable) value;
            return value(v.value);
        }
        throw new Exception("right value error");
    }

Added ʻaccessArray () method for array access. The argument ʻexpr is passed a [ token. The [ token left resolves to the array itself. The [ token right resolves to the index to access. Use them and use the ʻArrayList :: get ()` method to retrieve the elements and return them.

Interpreter.java


    public Object accessArray(Token expr) throws Exception {
        List<Object> ar = array(expression(expr.left));
        Integer index = integer(expression(expr.right));
        return ar.get(index);
    }

Added the ʻarray () method, a method that guarantees that the argument is an array (List ). I will guarantee that what is accessed by the above ʻaccessArray () method is an array.

Interpreter.java


    @SuppressWarnings("unchecked")
    public List<Object> array(Object value) throws Exception {
        if (value instanceof List<?>) {
            return (List<Object>) value;
        } else if (value instanceof Variable) {
            Variable v = (Variable) value;
            return array(v.value);
        }
        throw new Exception("right value error");
    }

The program below using the above implementation

var ar = ["a", "b", "c"]
println(ar.size())
println(ar[2])

To output the length of the array 3 and the third element of the array"c".

Interpreter.java


    public static void main(String[] args) throws Exception {
        String text = "";
        text += "var ar = [\"a\", \"b\", \"c\"]";
        text += "println(ar.size())";
        text += "println(ar[2])";
        List<Token> tokens = new Lexer().init(text).tokenize();
        List<Token> blk = new Parser().init(tokens).block();
        new Interpreter().init(blk).run();
        // --> 3
        // --> c
    }

That's all for the implementation. Thank you very much.

in conclusion

The full source is available here.

Calc https://github.com/quwahara/Calc/tree/article-17-array/Calc/src/main/java

There is a continuation article.

** Corresponds to JSON-like object definition ** http://qiita.com/quwahara/items/5e6cee17b7b03bd994ee