Home CPSC 401

Sloth Arrays

 

Due: April 10

 

Introduction

For this stage of the Sloth interpreter, we will be adding arrays into the language. This will involve changes to the lexer, parser, and tree-walking interpreter.

We can make arrays in Sloth using this literal notation:


numbers := [];
names := ["Alice", "Bob", "Claire"];

We can then index a list using the familiar syntax to either read or set a value:


print(names[1]);
names[2] := "Charlie";

We can join two lists using the + operator, and get the length of one using the new length function:


numbers := numbers + [1, 2, 3];
size := length(numbers);

We can also pass an array into the print or println functions.

To keep things simple, we will only have "one-dimensional" arrays — that is we can only have arrays of the other types, not arrays containing other arrays.

We will use the following new test programs for this stage of the assignment:

ProgramDescription
arrays.slMakes an array and then loops through it.
sort.slReads in an array of data and then bubble sorts it.

You should also make shorter test programs to test each new language feature as you implement it. For instance, when you support printing an array literal, write a test program to do just that and try it.


 

Lexer Changes

Your lexer will need to capture the following new tokens:

  1. [
  2. ]
  3. ,
  4. "length", as a new standard library function.

These will allow us to recognize the lexical forms to support arrays in Sloth.


 

Parser Changes

We will need to make several changes to the parser in order to recognize the ways arrays will be used:

  1. We have to be able to parse literal arrays. These consist of any number of expressions, separated by commas, inside of brackets. For instance, the following are all array literals:
  2. In the previous version of the interpreter, we could only assign into a single variable. So the only valid form for the right hand side of the := operator was an ID. Now we can also assign into the slots of an array as well. For example, in code like array[i] := i * 10;. The technical term for what may appear on the left-hand side of the assignment operator is an L-value. We need to modify the assignment operator so that the left-hand side may be either a simple ID, or be followed by a '[', any expression, and then a ']'.
  3. There is also now the ability to use array values as part of an expression. We'll need to add an optional production for expression that goes to a subscripted array as well.
  4. Finally, we have the length function which takes one parameter inside of parentheses. This should be parsed similarly to the print function.

 

Interpreter Changes

Now we need to make the following changes in the interpreter to support the syntax we've added:

  1. First, add array as a new possible type. This means adding it to the SlothType enum, and also adding supporting code to the SlothValue class. Make a constructor that takes an ArrayList as a parameter, and store it in the object wrapped by the class.
  2. Setup conversions between arrays and other types. The array type should not be convertible into an int, real, or boolean, but it should be convertible into a String. You can use the ArrayList toString for that. Add a toArray method to this class. It should return array objects as ArrayLists. Other types should be converted into arrays of length one with, with the value as the only element. (This will allow us to append to arrays more easily).
  3. In the SlothVisitor, we need to add modify the visitAssign method to account for assigning into an array slot. If there is a subscript, we need to evaluate the expression used, take the result as an index and write to the array at that slot. When there are options like this in a rule, calling the sub-tree method (such as .expression()) will return null if it is not present.
  4. When handling the addition operator, we need to add the ability to concatenate arrays. When one operand is a string we area already joining the two into one string (converting one if needed). Now we will do the same for arrays. If either is an array, get them both as arrays. Then build a new array with the elements of the first, followed by the elements of the second. Then return that as the result of the addition. This should be done after handling strings (so adding a string + an array results in a string).
  5. We need to add a visit method for array literals. We must create a new ArrayList first. Then evaluate each of the expression nodes under this tree node, adding them to the array one by one. Finally, return the array as a SlothValue.
  6. Another visit method will need to be created for an array being indexed. In this method, we need to evaluate the expression and get the result as an integer. Then we fetch the ID of the array from the symbol table, get it as an ArrayList, and then perform the indexing.
  7. Finally, add a visit method for then length function to find the length of an array. While we are here, we could also make it work for strings, but none of the test programs use that.

There are many things that can go wrong in the methods above: the index might be a non-integer, it might be negative, or too big, etc. You don't need to check for these things for this assignment. If something goes wrong, the Java VM will kill our interpreter. Making good error messages for our language would take a bit of doing and we won't worry about it here.


 

Submitting

Submit the files for your interpreter to Canvas for this assignment.

Copyright © 2024 Ian Finlayson | Licensed under a Creative Commons BY-NC-SA 4.0 License.