# Grammar for a custom language called Elegance

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

• 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;

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.languages.Language
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)
//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
{
languages=[localLoader]+languages  //List addition!  languages= is required because its a named parameter
);

if questionId do
end

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.


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 person, your language looks a lot like . 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.)

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.

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.

• @mdfst13 thanks for the typo fixes. I shouldn't write answers when I'm this tired... and run it through a real typechecker... Sep 6 '17 at 3:19
• Wow, this is fantastic. 1. Splitting lexer and parser, I've never heard of that, but I like the idea. What features are possible? 2. I've never actually tried scala, but I believe that my type system is vastly different 3. I'm not sure what you mean by "reverse solidus". Can you explain? 4. I use Gradle, but I still had to add the @header to make it work 5. I'm ok with package_path and variable being identical. 6. option (or opt) is a magic keyword that adds named, optional parameters to a function/constructor Sep 6 '17 at 4:06
• 7. I don't understand Never. Is the entire purpose to say "this function never finishes"? Sep 6 '17 at 4:06
• @NathanMerrill TBH I probably should have not included Never here. A bit of type theory leaking through. But yeah, you're basically right. Reverse solidus == backslash == \ (Sorry, Unicode-related work has influenced my character naming.) I know the maven plugin has a thing to handle packaging, but I don't know about the gradle plugin. The biggest lexer-only feature is Lexical Modes. Sep 6 '17 at 4:16
• Also, SE markdown engine ate by </sarcasm> on the note about scala :( Sep 6 '17 at 4:19