10.8 C
New York
Tuesday, October 4, 2022

Building Your Own Programming Language From Scratch: Part V – Arrays – hackernoon.com

6+ years Java developer

In this part of creating your programming language, we will implement arrays. Please see the previous parts:

The full source code is available over on GitHub.

We will begin with lexical analysis. Basically, it’s a process to divide the source code into tokens, such as keyword, identifier/variable, operator, etc.
First, to define the array, we add curly brackets { } as the GroupDivider lexeme. We can’t use the square brackets [ ] or round brackets ( ) as they are already taken by the functions/structures definitions and by expression operators accordingly.

Second, we need to introduce a new << Operator lexeme to define the "append a value to array" operation. We’ll extend the current less than operator < by adding an {1,2} quantifier after it, which will be able to catch either one or two < symbols:

With all this being set, we will catch all the needed lexemes properly with defined TokenType values.

In this section, within the syntax analysis, we will convert tokens obtained from the lexical analysis into final statements following our language’s array rules. Arrays are just like any other part of the expression without any additional statements. Therefore, we just need to extend the existing functionality for the ExpressionStatement.
First, to declare any values in our array, we define the ArrayExpression class and add the List of values, which will accept the Expression values to allow us to place non-final values such as variables, structure invocations, function invocations, operators, and any other Expression implementations. Next, we implement the Expression interface, which requires us to override the evaluate() method. It’s a deferred interface to transform array Expression expressions into final Value values, which will be invoked only during direct code execution:

The next class we implement is ArrayValue, which will accept the ArrayExpression as a constructor argument to gather all the details about the array state. To change the array values, we include the corresponding getValue(), setValue(), appendValue() methods:

We can also override the equals() method, as it will be used by the EqualsOperator and NotEqualsOperator to compare:

With the ArrayExpression implementation, we can already instantiate arrays and fill them with values. The next goal is to access the array’s value by index position. For this purpose, we'll create the BinaryOperatorExpression operator implementation, which contains two operands. The evaluate() method will use the first operand as the array itself and the second operand as an index. The assign() method is used to set the array’s value by index using the same operands:

The new AssignExpression interface can be used to set the variable's value only within the assignment = operator:

Next, to transform the "append a value to array" operator defined as << Operator lexeme, we create a new BinaryOperatorExpression implementation. The left operand is still the array itself, and the right operand is the value we want to append:

Don’t forget to include this << operator in the Operator enum. It will have the same precedence as the Assignment operator:

In this section, we will complete syntax analysis for the array integration by reading an actual array instantiation and the array’s value. To make it work, we need to extend the ExpressionReader implementation to support array expressions within Dijkstra's Two-Stack algorithm.
First, we will read the array instantiation. We extend the readExpression() filter to support the curly brackets as the marker of array beginning:

Next, we implement the corresponding case for the GroupDivider { lexeme:

The pattern for the array expression is the same as for the function invocation except for using the curly brackets instead of square brackets: we read the array's values as the Expression expressions divided by a comma within the curly brackets. In the end, we build the ArrayExpression with the obtained values:

Accessing the array’s value by index position is less straightforward than the array’s append operation because our Dijkstra’s Two-Stack algorithm inside the ExpressionReader cannot handle the array’s index defined within the curly brackets as an operator. To solve this limitation, we will read the operator with operands together as a composite operand the same way we did read the structure instantiation, except for the fact that we don’t have the "new" operator in front of the structure and the array’s index is defined inside curly brackets instead of square brackets:

We have finished embedding arrays in both lexical and syntax analyzers. Now we should be able to read array expressions, access and update array values. Let’s implement a more realistic task – the recursive binary search algorithm:

Encode, Stream, and Manage Videos With One Simple Platform
Quality Weekly Reads About Technology Infiltrating Everything


Related Articles


Please enter your comment!
Please enter your name here

Latest Articles