Functionality of the Language#

The programming language currently being developed has a built-in data type - a dictionary - which enables storing and manipulating data in the form of key–value pairs. In this language, we can perform basic dictionary operations such as adding, removing, searching for elements based on a key, and checking whether a given key exists in the dictionary.

An important aspect of the language is the ability to iterate over dictionary elements in a defined order. This order is determined by a function passed as an additional parameter to a method, allowing us to control the sequence in which elements are returned. This enables more precise data management and processing within the dictionary.

Additionally, the language offers the ability to perform LINQ-style (Language Integrated Query) queries on dictionaries. LINQ is a powerful tool that enables searching, filtering, and transforming data declaratively. Thanks to LINQ integration, we can use these advanced data-processing techniques without writing a large amount of code.

This language is statically typed. This means all data types must be declared by the programmer, which allows the detection of type-related errors.

The language also uses strong typing, meaning that conversions between different types require explicit definition and are not performed automatically. This increases safety and code readability, eliminating ambiguous behavior and unexpected results.

The interpreter for this programming language is implemented in Java 17. Choosing Java as the implementation language allows leveraging the rich and mature Java ecosystem and taking advantage of strong typing and static analysis capabilities.

Language Constructs#

Arithmetic operations:

Example program

+ – addition
- – subtraction
* – multiplication
/ – division

Composition of algebraic expressions:

1
int value = first * (second + third);

Logical operations:

Example program

and - conjunction
or - disjunction
not - negation

Logical expression composition:

1
boolean expression = first and (second or third);

Numeric casting:

Example program

int to double - lossless
double to int - floor (fractional truncation)

1
int a = 1;
2
double b = 2.5;
3
double value = (@double a) + b;

Variable visibility:

Example program

variables are visible only within the block where they were declared

1
fun main() {
2
    if (true) {
3
        int a = 1;
4
    }
5
    int b = a; # error - `a` not visible outside the block
6
}

Conditional statements:

Example program

if statement:

1
boolean expression = 2 + 2 == 4;
2

3
if expression {
4
    # do something
5
}
6

7
if expression doSomething();

if-else:

1
boolean expression = 2 + 2 == 4;
2

3
if expression {
4
    # do something
5
} else {
6
    # do something else
7
}

Nested if-else:

1
boolean first = 2 + 2 == 4;
2
boolean second = false;
3

4
if first {
5
    # do something
6
} else if second {
7
    # do something else on condition
8
}

While loop:

Example program

1
boolean expression = true;
2
while expression {
3
    # do something
4
}

Iteration over iterable structures:

Example program

1
Map<String, String> map = [];
2
for (Tuple<String, String> entry : map.iterator()) {
3
    # do something
4
}

Functions:

Parameterized:

1
fun add(first: int, second: int): int {
2
    return first + second;
3
}

Without return:

1
fun log(message: String) {
2
    print(message);
3
}

Parameterless:

1
fun getOne(): int {
2
    return 1;
3
}

Variable assignment:

1
int a = 1;
2
int b = 2;
3
int tmp = a;
4
a = b;
5
b = tmp;

Argument-passing semantics:

arguments are passed by reference
objects are passed via references, not by copying values
changes inside a function are visible outside

Variable semantics:

static typing
- types must be declared
- type cannot change at runtime
strong typing
- no implicit conversions
- prevents ambiguity
mutability
- variables may be reassigned if the new value has the same type

Function recursion:

functions may be called recursively
- direct or indirect
- recursion depth is limited
- limit prevents infinite recursion and memory overflow
- configurable parameter

1
fun fibbonaci(n: int): int {
2
    if n == 0 return 0;
3
    if n == 1 return 1;
4
    return fibbonaci(n - 1) + fibbonaci(n - 2);
5
}

Comments:

1
# Single-line comment

1
/*
2
    Multi-line comment
3
*/

Data Types#

Primitive types:

int
- integers from [-2147483648; 2147483647]
double
- 64-bit floating-point
boolean
- true, false

Mathematical, logical, and comparison operations are defined for primitive types.

Complex types:

String
Map<key, value>
- dictionary
Tuple<value, ...>
Comparator<value>
Iterable<value>

Pseudo-interfaces and built-ins#

String

1
fun print(messsage: String);

Comparator

1
class Comparator<V> {
2
    fun compare(this:V, other:V): int;
3
}
4

5
fun compareValues(this: int, other: int): int {
6
    return 1;
7
}

Tuple<value, …>

1
class Tuple<V1, V2, V3, ...> {
2
    fun $name1: V1;
3
    fun $name2: V2;
4
    fun $name3: V3;
5
    ...
6
}
7

8
Tuple<String, int, double> tuple = |
9
    value1 AS name1,
10
    value2 AS name2,
11
    value3 AS name3,
12
|;

Map<key, value>

1
class Map<K, V> {
2
    fun operator[](key: K): V;
3
    fun put(key: K, value: V);
4
    fun contains(key: K): boolean;
5
    fun remove(key: K);
6
    fun iterable(): Iterable<K, V>;
7
    fun sortedIterable(comparator: Comparator<K, V>): Iterable<K, V>;
8
}
9

10
fun operator[]: Map<key, value>;
11

12
Map<String, int> map = [
13
    "id_1": 1,
14
    "id_2": 2
15
];

Iterable<value, …>

1
class Iterable<VALUE, ...> {
2
    fun hasNext(): boolean;
3
    fun next(): Tuple<VALUE, ...>;
4
}
5

6
Map<String, int> map = prepareMap(); # user defined function
7
Iterable<String, int> query =
8
    SELECT
9
        entry.key AS key,
10
        entry.value AS value
11
    FROM map AS entry
12
    WHERE entry.key != "abc" AND entry.value > 0
13
    ORDER BY entry.value, entry.key;

Syntax#

Terminal Symbols#

1
(* Regular expressions *)
2
letter                  = [a-zA-Z];
3
non_zero_digit          = [1-9];
4
digit                   = [0-9];
5
zero                    = "0";
6
character               = ?;
7
relation_operator       = "<" | "<=" | "==" | ">" | ">=" | "!="
8
addition_operator       = "+" | "-";
9
multiplication_operator = "*" | "/";
10

11
(* EBNF *)
12
INTEGER                 = zero
13
                        | non_zero_digit, {digit};
14
FLOATING_POINT          = INTEGER, ".", digit, {digit};
15
NUMBER                  = INTEGER
16
                        | FLOATING_POINT;
17

18
BOOLEAN                 = "true"
19
                        | "false";
20

21
IDENTIFIER              = letter, {letter | digit};
22

23
CHARACTERS              = {character};
24
STRING_DOUBLE_QUOTE     = '"', CHARACTERS, '"';
25
STRING_SINGLE_QUOTE     = "'", CHARACTERS, "'";
26

27
STRING                  = STRING_DOUBLE_QUOTE
28
                        | STRING_SINGLE_QUOTE;
29

30
COMMENT_SINGLE_LINE     = "#", CHARACTERS , "\n";
31
COMMENT_MULTI_LINE      = "/*", CHARACTERS , "*/";
32

33
COMMENT                 = COMMENT_SINGLE_LINE
34
                        | COMMENT_MULTI_LINE;
35

36
SIMPLE_TYPE             = "int"
37
                        | "double"
38
                        | "boolean"
39
                        | "String";
40

41
COMPLEX_TYPE            = "Map"
42
                        | "Comparator"
43
                        | "Iterable"
44
                        | "Tuple";

Complex symbols#

1
FUNCTION_DEFINITION    = "fun", IDENTIFIER, "(", [ARGUMENT_LIST], ")", [":", TYPE_DECLARATION], BLOCK;
2
ARGUMENT_LIST           = ARGUMENT_DECLARATION, {",", ARGUMENT_DECLARATION};
3
ARGUMENT_DECLARATION    = IDENTIFIER, ":", TYPE_DECLARATION;
4

5
TYPE_DECLARATION        = SIMPLE_TYPE
6
                        | COMPLEX_TYPE, "<", TYPE_DECLARATION, {",", TYPE_DECLARATION} ,">";
7

8
DECLARATION             = TYPE_DECLARATION, IDENTIFIER, "=", EXPRESSION, ";";
9

10
// STATEMENTS
11

12
BLOCK                   = "{", {STATEMENT} "}";
13

14
STATEMENT               = IF_STATEMENT
15
                        | WHILE_STATEMENT
16
                        | FOR_STATEMENT
17
                        | DECLARATION
18
                        | ASSIGNMENT_OR_IDENTIFIER_EXPRESSION
19
                        | RETURN_STATEMENT
20
                        | EXPRESSION, ";"
21
                        | BLOCK
22
                        | ";";
23

24
IF_STATEMENT            = "if", LOGICAL_EXPRESSION, STATEMENT,
25
                          ["else", STATEMENT];
26

27
WHILE_STATEMENT         = "while", LOGICAL_EXPRESSION, STATEMENT;
28

29
FOR_STATEMENT           = "for", "(", TYPE_DECLARATION, IDENTIFIER, ":", EXPRESSION, ")", STATEMENT;
30

31
ASSIGNMENT_OR_IDENTIFIER_EXPRESSION = [IDENTIFIER, "="], EXPRESSION, ";";
32

33
RETURN_STATEMENT        = "return", EXPRESSION, ";";
34

35
// EXPRESSION
36

37
EXPRESSION              = LOGICAL_EXPRESSION;
38

39
LOGICAL_EXPRESSION      = LOGICAL_OR_EXPRESSION;
40

41
LOGICAL_OR_EXPRESSION   = LOGICAL_AND_EXPRESSION, {"or", LOGICAL_AND_EXPRESSION};
42

43
LOGICAL_AND_EXPRESSION  = RELATION, {"and", RELATION};
44

45
RELATION                = ["not"], (BOOLEAN | ARITHMETIC_EXPRESSION, [relation_operator, ARITHMETIC_EXPRESSION]);
46

47
ARITHMETIC_EXPRESSION   = FACTOR, {addition_operator, FACTOR};
48

49
FACTOR                  = TERM, {multiplication_operator, TERM};
50

51
TERM                    = ["-"], (SIMPLE_TYPE | TUPLE_OR_METHOD_CALL);
52

53
SIMPLE_TYPE             = NUMBER | STRING;
54

55
TUPLE_METHOD_MAP_CALL   = SIMPLE_EXPRESSION, { (".", IDENTIFIER, [FUNCTION_ARGUMENTS] | "[", EXPRESSION,"]" ) };
56
FUNCTION_ARGUMENTS      = "(", [EXPRESSION, {",", EXPRESSION}], ")";
57

58
SIMPLE_EXPRESSION       = IDENTIFIER_OR_FUNCTION_CALL
59
                        | SELECT_EXPRESSION
60
                        | STANDALONE_TUPLE_EXP
61
                        | MAP_EXPRESSION
62
                        | EXPLICIT_CAST
63
                        | PARENTHESES_EXPRESSION;
64

65
IDENTIFIER_OR_FUNCTION_CALL = IDENTIFIER, [FUNCTION_ARGUMENTS];
66

67
SELECT_EXPRESSION       = "SELECT", TUPLE_EXPRESSION, "FROM", TUPLE_ELEMENT,
68
                          {"JOIN", TUPLE_ELEMENT, ["ON", EXPRESSION]},
69
                          ["WHERE", EXPRESSION],
70
                          ["GROUP", "BY", EXPRESSION, {",", EXPRESSION}, ["HAVING", EXPRESSION]],
71
                          ["ORDER", "BY", EXPRESSION, ["ASC" | "DESC"], {"," ORDER_BY_EXPRESSION}];
72

73
MAP_EXPRESSION          = "[", [EXPRESSION, ":", EXPRESSION, {",", EXPRESSION, ":", EXPRESSION}], "]";
74

75
STANDALONE_TUPLE_EXP    = "|", TUPLE_EXPRESSION, "|";
76
TUPLE_EXPRESSION        = TUPLE_ELEMENT, {",", TUPLE_ELEMENT};
77
TUPLE_ELEMENT           = EXPRESSION, "AS", IDENTIFIER;
78

79
EXPLICIT_CAST           = "@", TYPE_DECLARATION, EXPRESSION;
80

81
PARENTHESES_EXPRESSION  = "(", EXPRESSION, ")";

Start symbol#

1
PROGRAM = {COMMENT | FUNCTION_DEFINITION | DECLARATION | ";"};

How to Run#

The interpreter can be launched using the prepared script: interpreter

Example execution and result:

1
$ ./interpreter --help
2
Usage: ./interpreter [OPTION] [FILE]
3
    -h --help               Display this message
4
    -c --clean              Re-build project from scratch before running application
5
    -i --identifier [VALUE] Set the maximum number of characters in a identifier
6
                            Default: 100
7
    -s --string [VALUE]     Set the maximum number of characters in a string
8
                            Default: 1000
9
    -e --exception [VALUE]  Set the maximum number of exceptions before stopping execution of a program
10
                            Default: 500
11
    -f --function [VALUE]   Set the maximum number of nested function calls before stopping execution of program
12
                            Default: 100
13
$ ./interpreter hello.txt
14
Hello, World!

To run the script, Java 17 must be installed on the system.

The interpreter together with its libraries is packaged into a single Fat Jar, which also allows running the program using the java command:

1
$ java -jar "$FAT_JAR" "$FILE"

Alternative#

It is also possible to run the program directly from the console. In this case, you must first add a shebang header with the path to the interpreter:

1
#!/mnt/c/Users/Public/Documents/TKOM/interpreter
2

3
fun main() {
4
    print("Hello, World!");
5
}

Execution is then done by calling the file directly:

1
$ ./hello.txt
2
Hello, World!

Configuration#

The language provides several configurable parameters:

maximum identifier length

1
    -i --identifier [VALUE] Set the maximum number of characters in a identifier
2
                            Default: 100

maximum string length

1
    -s --string [VALUE]     Set the maximum number of characters in a string
2
                            Default: 1000

maximum number of non-critical errors before program execution should stop

1
    -e --exception [VALUE]  Set the maximum number of exceptions before stopping execution of a program
2
                            Default: 500

maximum depth of nested function calls

1
    -f --function [VALUE]   Set the maximum number of nested function calls before stopping execution of program
2
                            Default: 100

Implementation#

Lexer#

Interface#

1
public interface Lexer {
2
    Token nextToken();
3
}

The lexer is a key component in the lexical analysis process. Its main task is to transform a stream of characters into a sequence of tokens that represent valid language elements.

When creating a Lexer instance, a Reader is passed as an argument, providing the character stream for analysis. The lexer exposes a method that returns subsequent tokens.

An important feature of the lexer is lazy (on-demand) mode. This means it reads characters only when a new token is requested. This allows efficient processing because it does not require loading and analyzing the entire source text at once.

When the token retrieval method is called, the lexer reads the necessary number of characters from the input stream and performs lexical analysis, producing the next token.

Tokens#

1
public enum TokenType {
2
    END_OF_FILE,
3

4
    FUNCTION_DEFINITION("fun"),
5
    RETURN("return"),
6
    WHILE("while"),
7
    FOR("for"),
8
    IF("if"),
9
    ELSE("else"),
10

11
    SELECT("select", false),
12
    FROM("from", false),
13
    JOIN("join", false),
14
    ON("on", false),
15
    WHERE("where", false),
16
    GROUP("group", false),
17
    HAVING("having", false),
18
    ORDER("order", false),
19
    BY("by", false),
20
    ASCENDING("asc", false),
21
    DESCENDING("desc", false),
22

23
    AS("as", false),
24

25
    OPEN_CURLY_PARENTHESES("{"),
26
    OPEN_ROUND_PARENTHESES("("),
27
    OPEN_SQUARE_PARENTHESES("["),
28
    CLOSED_CURLY_PARENTHESES("}"),
29
    CLOSED_ROUND_PARENTHESES(")"),
30
    CLOSED_SQUARE_PARENTHESES("]"),
31
    VERTICAL_BAR_PARENTHESES("|"),
32

33
    SEMICOLON(";"),
34
    COLON(":"),
35
    COMMA(","),
36
    DOT("."),
37
    EXPLICIT_CAST("@"),
38

39
    AND("and", false),
40
    NOT("not", false),
41
    OR("or", false),
42

43
    EQUALITY("=="),
44
    INEQUALITY("!="),
45
    GREATER(">"),
46
    LESS("<"),
47
    GREATER_EQUAL(">="),
48
    LESS_EQUAL("<="),
49

50
    EQUALS("="),
51

52
    PLUS("+"),
53
    MINUS("-"),
54
    TIMES("*"),
55
    DIVIDE("/"),
56

57
    SINGLE_LINE_COMMENT("#", "\n"),
58
    MULTI_LINE_COMMENT("/*", "*/"),
59

60
    IDENTIFIER,
61
    INTEGER_CONSTANT,
62
    FLOATING_POINT_CONSTANT,
63
    STRING_DOUBLE_QUOTE_CONSTANT("\"", "\""),
64
    STRING_SINGLE_QUOTE_CONSTANT("'", "'"),
65

66
    BOOLEAN_TRUE("true"),
67
    BOOLEAN_FALSE("false"),
68

69
    INT("int"),
70
    DOUBLE("double"),
71
    BOOLEAN("boolean"),
72
    VOID("void"),
73

74
    STRING("String"),
75

76
    MAP("Map"),
77
    ITERABLE("Iterable"),
78
    TUPLE("Tuple"),
79
    COMPARATOR("Comparator"),
80
    ;
81
    ...
82
}

Parser#

Interface#

1
public interface Parser {
2
    Program parseProgram() throws CriticalParserException;
3
}

The parser is a crucial component of the language implementation. Its primary role is to analyze the syntactic structure of the source text and generate an Abstract Syntax Tree (AST).

The AST is a hierarchical representation of the program’s structure. It consists of nodes representing language constructs such as statements, expressions, and declarations.

ASTs are easier to analyze and process than raw source text, and they serve as the foundation for interpretation.

Interpreter#

Interface#

1
public interface Interpreter {
2
    void execute(Program program);
3
}

1
public interface Visitor {
2
    void visit(Program program);
3

4
    void visit(FunctionDefinitionStatement statement);
5

6
    void visit(DeclarationStatement statement);
7

8
    void visit(IfStatement statement);
9

10
    void visit(WhileStatement statement);
11

12
    void visit(ForStatement statement);
13

14
    void visit(AssignmentStatement statement);
15

16
    void visit(ReturnStatement statement);
17

18
    void visit(BlockStatement statement);
19

20
    void visit(BinaryLogicalExpression expression);
21

22
    void visit(NegateLogicalExpression expression);
23

24
    void visit(BooleanExpression value);
25

26
    void visit(RelationLogicalExpression expression);
27

28
    void visit(EqualityRelationLogicalExpression expression);
29

30
    void visit(BinaryArithmeticExpression expression);
31

32
    void visit(NegationArithmeticExpression expression);
33

34
    void visit(IntegerExpression value);
35

36
    void visit(FloatingPointExpression value);
37

38
    void visit(StringExpression value);
39

40
    void visit(TupleCallExpression expression);
41

42
    void visit(MethodCallExpression expression);
43

44
    void visit(IdentifierExpression expression);
45

46
    void visit(FunctionCallExpression expression);
47

48
    void visit(SelectExpression expression);
49

50
    void visit(TupleExpression expression);
51

52
    void visit(TupleElement expression);
53

54
    void visit(MapExpression expression);
55

56
    void visit(ExplicitCastExpression expression);
57

58
    void visit(PrintFunction expression);
59
}

InterpretingVisitor implements the Visitor interface, which contains methods for visiting each type of AST node. Each visit() method defines how that specific node should be interpreted.

It also implements the Interpreter interface, whose interpret() method begins program execution by passing the AST root to accept().

1
public class InterpretingVisitor implements Visitor, Interpreter {
2
    ...
3
}

Using the Visitor design pattern allows the interpreter to traverse the AST structure cleanly and process each node according to its type.

Obsługa błędów#

1
public interface ErrorHandler {
2
    void handleLexerException(LexerException exception);
3

4
    void handleParserException(ParserException exception);
5

6
    void handleInterpreterException(InterpreterException exception);
7

8
    void showExceptions(Reader reader) throws IOException;
9
}

Error handling covers multiple layers of the interpreter:

Source

Errors are displayed to the user with appropriate messages
Interpreter stops after encountering an error

Lexer

Errors are forwarded to the ErrorHandler
Excessively long identifiers, comments, or strings are truncated
Overly long integers have the excess digits removed
Floating-point numbers with too many fractional digits have extras ignored
Unrecognized characters are skipped

Parser

Errors are passed to the ErrorHandler
Two types of errors: critical and non-critical
Critical errors stop execution
Non-critical errors (e.g., missing semicolon) are reported but don’t halt parsing

Interpreter

All interpreter errors are critical
All errors are reported to the ErrorHandler

Error Messages#

Errors are collected and displayed to the user in a readable format. Each line with errors is preceded by a line number, followed by detailed messages.

This format helps users identify problematic lines quickly and fix issues efficiently.

Example code:

1
#!/mnt/c/Users/Public/Documents/TKOM/interpreter
2

3
fun recursive() {
4
    print("recursion");
5
    recursive();
6
}
7

8
fun main() {
9
    recursive();
10
}

Result:

1
$ ./src/test/resources/error-recursion-limit.txt --function 5
2
recursion
3
recursion
4
[INFO]    4:    print("recursion");
5
[ERROR] MaxFunctionStackSizeReachedException(super=CriticalInterpreterException(position=Position(line=4, characterNumber=8), contextStack=[~~main~~: Position(line=1, characterNumber=1), main: Position(line=1, characterNumber=1), recursive: Position(line=9, characterNumber=2), recursive: Position(line=5, characterNumber=2), recursive: Position(line=5, characterNumber=2), print: Position(line=4, characterNumber=2)])) - org.example.interpreter.error.MaxFunctionStackSizeReachedException:
6
~~main~~: Position(line=1, characterNumber=1)
7
main: Position(line=1, characterNumber=1)
8
recursive: Position(line=9, characterNumber=2)
9
recursive: Position(line=5, characterNumber=2)
10
recursive: Position(line=5, characterNumber=2)
11
print: Position(line=4, characterNumber=2)

On interpretation errors, the program stops and displays all related issues.

Additionally, the interpreter prints a call stack trace, showing the chain of function calls leading to the error and the source code positions where they occurred.

This gives the user a full picture of the error context, allowing faster debugging.

Custom Programming Language