Grammar for a custom language called Elegance

Question

I'm working on my own custom language called Elegance. This is my first grammar, and I'm looking for help with:

• Readability
• Expressiveness/DRY code (Can I easily reuse rules/tokens?)
• Edge cases (Is there code that I can't parse that I didn't consider?)

My grammar is far from finished, but I'd appreciate some guidance in its current state so new rules are written well. I've included both the grammar and some sample code I've been using to write my grammar.

Grammar:

grammar Elegance;

@header {
package com.nmerrill.elegance.antlr;
}

file: (package)? (file_import)* (ele_class | function | statement)* EOF;

package :
    PACKAGE_DECLARATION IDENTIFIER COLON package_path;

package_path :
    IDENTIFIER (PERIOD IDENTIFIER)*;

file_import :
    IMPORT_DECLARATION (IDENTIFIER COLON)? package_path;

ele_class :
    CLASS_DECLARATION IDENTIFIER
    type_parameters?
    parameter_list?
    type_alias*
    OPEN_CURLY 
    (ele_class | function | assignment)*
    CLOSE_CURLY;

function:
    FUNCTION_DECLARATION IDENTIFIER parameter_list 
    COLON type
    (MUTABLE_DECLARATION OPEN_PAREN (variable (COMMA variable)*)? CLOSE_PAREN)?
    (
        OPEN_CURLY (function | statement)* CLOSE_CURLY |
        EQUAL function_call
    );

variable:
    IDENTIFIER (PERIOD IDENTIFIER)*;

assignment:
    (VALUE_DECLARATION | VARIABLE_DECLARATION | OPTION_DECLARATION)?
    (MUTABLE_DECLARATION)?
    IDENTIFIER
    (COLON type)? 
    EQUAL 
    (expression)
    SEMICOLON;

statement:
    (function_call | assignment | statement_if | for);

statement_if: IF expression DO statement* (ELSE statement*)? END;
expression_if: IF expression DO expression ELSE expression END;
for: FOR IDENTIFIER IN expression DO statement* END;

function_call: expression argument_list SEMICOLON;

argument_list:
    OPEN_PAREN 
       (argument
           (COMMA  argument)* 
           (COMMA  named_argument)* 
       | named_argument
           (COMMA  named_argument)* 
       )?
   CLOSE_PAREN;

argument: expression;

named_argument: IDENTIFIER EQUAL expression;

parameter_list:
    OPEN_PAREN 
        (parameter
            (COMMA  parameter)* 
        )?
    CLOSE_PAREN;

parameter:
    expression 
    (COLON type)?;

type:
    type ASTERISK |  //Iterable type
    type COMMA type |  //Pair type
    type QUESTION_MARK |  //Optional type
    OPEN_PAREN type_function_parameters CLOSE_PAREN ARROW type | //Named function type
    type ARROW type | //Function type
    IDENTIFIER
        type_parameters?
        (OPEN_BRACKET trait_expression CLOSE_BRACKET)?;

type_function_parameters:
    IDENTIFIER COLON type (COMMA IDENTIFIER COLON type)* |
    type (COMMA type)*;

type_parameters:
    (OPEN_ANGLE_BRACKET type (SEMICOLON type)* CLOSE_ANGLE_BRACKET);

trait_expression:
    trait_expression OR trait_expression |
    trait_expression AND trait_expression |
    IDENTIFIER (OPEN_PAREN (literal (COMMA literal)*)? CLOSE_PAREN)?;

type_alias:
    WHERE_DECLARATION IDENTIFIER COLON type;

expression:
        expression PERIOD IDENTIFIER | //Accessor
        expression argument_list | //Function call
        expression OR expression |
        expression AND expression |
        expression (IS | EQ | NEQ)  expression |
        expression (LEQ | GEQ | LT | GT)  expression |
        expression (PLUS | MINUS)  expression |
        expression (ASTERISK | DIV)  expression |
        expression_if |
        OPEN_PAREN  expression  CLOSE_PAREN |
        literal |
        type |
        IDENTIFIER;

literal: integer | ele_float | list | tuple | dictionary | set | STRING ;

list: OPEN_BRACKET  (expression (COMMA  expression)* )? CLOSE_BRACKET ;

tuple: TUPLE_START  (expression (COMMA  expression)* )? CLOSE_BRACKET ;

set: SET_START  (expression (COMMA  expression)* )? CLOSE_BRACKET ;

dictionary: DICT_START  (expression COLON expression (COMMA  expression COLON expression)* )? CLOSE_BRACKET ;

integer: (PLUS | MINUS)? INTEGER | ZERO;

ele_float: (PLUS | MINUS)? FLOAT;


INTEGER: [1-9][0-9]* ;

FLOAT: ('0' | [1-9][0-9]* ) '.' [0-9]+;

ZERO: '0' ;

STRING: '"' ('\\'. | ~('"' | '\\'))* '"' |  '\'' ('\\'. | ~('\'' | '\\'))* '\'';

SET_START: 's[';
TUPLE_START: 't[';
DICT_START: 'd[';

PACKAGE_DECLARATION: 'package' ;
CLASS_DECLARATION : 'class' ;
FUNCTION_DECLARATION: 'fun' ;
VALUE_DECLARATION: 'val' ;
VARIABLE_DECLARATION: 'var' ;
OPTION_DECLARATION: 'option' ;
IMPORT_DECLARATION: 'import' ;
WHERE_DECLARATION: 'where' ;
MUTABLE_DECLARATION: 'mut' ;

OPEN_CURLY: '{' ;
CLOSE_CURLY: '}' ;
OPEN_PAREN: '(' ;
CLOSE_PAREN: ')';
OPEN_ANGLE_BRACKET: '<' ;
CLOSE_ANGLE_BRACKET: '>';
OPEN_BRACKET: '[' ;
CLOSE_BRACKET: ']' ;

IF: 'if' ;
ELSE: 'else';
FOR: 'for' ;
IN: 'in' ;
DO: 'do' ;
END: 'end';


COLON: ':' ;
COMMA: ',';
PERIOD: '.' ;

EQUAL: '=';

OR: 'or';
AND: 'and';
IS: 'is';
EQ: 'eq';
NEQ: 'neq';
LEQ: 'leq';
GEQ: 'geq';
LT: 'lt';
GT: 'gt';


ASTERISK: '*';
PLUS: '+';
MINUS: '-';
DIV: '/';

SEMICOLON: ';';

IDENTIFIER: [a-zA-Z_][a-zA-Z0-9_]*;

UNDERSCORE: '_';

ARROW : '->';

QUESTION_MARK: '?';

COMMENT: ('//' ~('\r' | '\n')+) -> skip;
WS: ('\n' | '\r' | '\t' | ' ')+ -> skip;

Test Code:

package kothcomm:game    //Modules are named:  "kothcomm" is the name for the module "com.nmerrill.kothcomm"

import communication.Downloader  // No module is necessary for local packages, equivalent to kothcomm:communication.Downloader
import communication.LanguageLoader
import communication.languages.Language
import communication.languages.local.LocalJavaLoader
import game.games.AbstractGame
import game.players.AbstractPlayer
import game.players.Submission
import game.scoring.Aggregator
import game.scoring.ItemAggregator
import game.scoring.Scoreboard
import game.tournaments.Sampling
import game.tournaments.Tournament
import ui.text.TextUI

import core:Random  // core is the built-in module
import core:IO

class KotHComm<Player, Game>(gameSupplier: (Void)->Game, gameSize: Int[greaterThan(1)])  //No use of <T,U>, type parameters should be readable
    where Player: AbstractPlayer*    //Similar to Player extends AbstractPlayer
    where Game: AbstractGame<Player>  //Doesn't necessarily have to be the first thing in the class
    where PlayerSubmission: Submission<Player>  //This isn't a type parameter, but "renames" Submission<Player> to PlayerSubmission
{
    val mut localLoader = LocalJavaLoader<Player>.new();  //val means the reference doesn't change, mut means that the object can be mutated, private is implied

    option languages: Language<Game>* = [];  //This one is not required because it has a default value
    option scorer: (items: Scoreboard<PlayerSubmission>*)->Scoreboard<PlayerSubmission> = ItemAggregator.new();
        //Types!  The above is a function that takes a named parameter `items` which is an iterable of Scoreboard<PlayerSubmission> and returns a Scoreboard<PlayerSubmission>
        //ItemAggregator.new() is a constructor call, which means that ItemAggregator implements the above function
    option tournamentSupplier: (submissions: PlayerSubmission*, random: Random)->Tournament<PlayerSubmission> = Sampling.new;
        //Function references can be generated using Sampling.new
    option printer: Printer = TextUI.new();
    option mut random: Random = Random.new();
    option numIterations: Int = 100;
    option questionId: Int? = null;
        //   ? indicates an optional/nullable type


    fun addSubmission(name: String, playerSupplier: Void->Player): Void
        mut(self)
        = localLoader.register(name, playerSupplier);
        //This function takes two named parameters, and passes them onto localLoader.register
        //LocalLoader.register *does* require named parameters, but because the paramter names match the argument names, no naming is required (you could write name=name if you wanted to)
        //mut(self) indicates that the function is impure because it mutates the object
        // You should also shorten the above by doing `fun addSubmission = localLoader.register`


    fun run(): Void
        mut(IO.out,IO.network)  //This function mutates the Standard out, and access the network
    {
        val loader = LanguageLoader<Player>.new(
            languages=[localLoader]+languages  //List addition!  `languages=` is required because its a named parameter
        );

        if questionId do
            Downloader.downloadQuestions(loader, questionId);  //Downloader.downloadQuestions mutates IO.network
        end

        val players = loader.load();
        val tournament = tournamentSupplier(submissions = players, random);  //To call a function, you simply add the parenthesis
        val mut runner = TournamentRunner.new(tournament, aggregator, gameSize, gameSupplier, random);  //We'll mutate the runner later, so we need to declare it
        printer.printStart();  //This (and other printer calls) mutates IO.out

        for i in range(numIterations) do  //Range is a function that *doesn't* require named parameters.
                                        //The signature looks like `fun range(ordered stop: Int)`
            printer.printProgress(progress=i, total=totalIterations);
            runner.createGame().run();  //createGame mutates the runner
        end
        printer.printFinished();
        printer.printScoreboard(runner.scoreboard());  //This also requires a name parameter, scoreboard, but because the method call is `scoreboard`, it isn't needed
    }
}

KotHComm.new(gameSupplier = MyGame.new, gameSize = 1)  //Creates a KotHComm.

Answer 1

Let's start with the minor things:

Personally, I like splitting my lexer grammar and parser grammar into two separate files. I understand that a lot of people don't like that though, so either way is fine. I split mine because the lexing and parsing are two separate logical steps that have nothing to do with each other. It also allows for some more powerful ANTLR features if you ever want them.

If you are going to use a combined grammar though, I'd suggest actually using the convenience of the combined grammar to use e.g. ';' in your parser rules instead of the more unruly SEMICOLON.

The example grammars all follow the convention of TokenName and ruleName, rather than what you have of TOKEN_NAME and rule_name. This is again, highly dependent on your own style and the language target you are targeting: conventions are different in all of them and when possible you like to generate idiomatic naming conventions so using the API doesn't feel too much like using generated code.

Being a kotlin person, your language looks a lot like scala. Have you tried it? </sarcasm>

For long fragments with a lot of options, it seems like the preferred option for formatting is the following:

parserRule
🌭: TOKEN SEQUENCE
🌭| ALTERNATE SEQUENCE
🌭| (SOMETHING)* CRAZY?
🌭;

(With your usual indentation style. If it's not clear, the 🌭 stands for whatever indentation.)

---

Now for your tokens:

Is there a reason ZERO is separate from INTEGER? You only use it by unioning it back with INTEGER anyway.

Break out the inner part of your STRING definition into a fragment to deduplicate it. In any case, restricting the second half of the inner part to not be a reverse solidus is technically not required as a reverse solidus will always be consumed by the earlier part of the match (except at the end of input, technically).

The *_DECLARATION is probably not required; just calling a keyword token by its name (so long as it doesn't conflict with a keyword in your target language) is usually better, like you've done with if and below.

Your identifier rules exclude a large portion of Unicode recommended identifiers. It's a long complicated document, but since you can use Unicode character information in ANTLR you can just do [\p{XID_START}_][\p{XID_CONTINUE}]*. There are complicated issues in doing so (namely, normalization, or lack thereof), so this is merely a suggestion. Some context

UNDERSCORE will never be emit! If the lexer starts parsing a token and sees _, it will first see a match for IDENTIFIER and never emit a UNDERSCORE.

---

And a little about your parser rules:

If you integrate with a build tool such as maven, the @header block with a package statement isn't required.

The @header suggests that package is a keyword in your target language but then you use package as a parser rule's name. I'm surprised this works outside of the ANTLR interpreter (if it does). It will probably cause problems to use a reserved word in your target language as a parser rule, so I'd advise against it.

package_path and variable are identical. This might be useful if they might diverge in the future, but you might consider just refactoring them to both use a more generically named path (or similar; naming is NP-hard and not my strong suit).

Given that assignment is using your *_DECLARATION tokens, I'd think it's more of a declaration node than an assignment one. And since you have a VARIABLE_DECLARATION, I assume you want to be able to assign to a variable without redeclaring it.

---

And a little bit of language design:

If you have option foo: Int, why do you also have option foo: Int? and var foo: Int??

Given var, val, and mut, I'd expect opt not option.

Your floats don't allow exponential notation. That's a bit harder to support but very appreciated when you need to write large numbers like 1e20.

---

On a whole though, it looks solid! I'd have to play with this for a good deal longer to really get a feel for the language, but it looks like it'd be interesting to use.

Just one last thing: rename Void to Unit. void is a legacy name that could mean a bunch of things, but Unit is more accurate when you mean that it takes (or returns) no useful information. Unit is the zero-tuple or a single-element enumerated type; it has a single singleton element with no information. Never is then the uninstantiable type. A function taking Never can not be called, because you cannot produce a Never to give it, and a function returning Never can never terminate because it cannot produce a Never to return.