IKON: human oriented JSON look-alike

So, yet another DSL/markup but please take a look:

{ Star
   size = 12
    x = 9
    y = 4
    name "Alpha Centaury"
    planets [
        { Planet size = 100 }
        { Planet size = 120 }
        { Planet size = 10 }
    ]
}

Looks like JSON. So why make up another language? Well, unlike JSON this one isn't designed with Javascript compatibility first, instead it's designed with human editor in mind. In general case IKON (Ivan Kravarčšan's object notation) looks like JSON with less double quotes but it can be expanded with domain specific syntax. Need shorthand syntax for matrices? No problem, plug it in. And even more customization can be achieved by extending IKADN (Ivan Kravarščan's abstract data notatins) but more about it later.

(Brief) history

Before unleashing language/notation specifics allow me to tell you a little about brief history of IKADN and IKON. DSLs (domain specific languages) have a tendency of cropping up in almost every project. A year ago I decided to rewrite the Stareater, a strategy game and a rather big project of mine and since it was rewrite I knew that I'll need not one DSL but three: one for settings and save file, another one for assets (statistical data about game objects such as how much they cost and what image present them) and yet another one for localization. Most of developers would simply pick XML, XML and XML. I find XML too heavily oriented on describing data organization instead of data itself. It's good for some purposes but it's overkill for my needs. JSON, YAML and plain INI were options I considered but at some point I figured what I was really looking for is something that can adapted to a specific problem. Settings file would work OK general markup language such as JSON but localization files would work better with text oriented solution. For instance there is no need numbers and arrays in localization data while simplified syntax for single line text is very useful. So, I decided to make my own solution that satisfies specific needs.

The solution I came up with are IKADN, an abstract notation that can be used for making other markup languages and IKON, a general purpose language. The rest are technicalities but I'll mention that I'm actively using IKON and two IKADN derivates in the Stareater project for a year and improve them regularly.

About IKON

As said before IKON is general purpose solution so, much like JSON and YAML it features three classes of data:

• Scalars (atoms of data such as numbers or texts)
• Tables (key-value pairs)
• Array (much like tables but with values only and values are ordered)

For more information about data types consult with project's wiki page: https://code.google.com/p/ikon-library/wiki/IKON. Some differences to JSON are that notation doesn't limit range and precision of numbers (it's up parser implementation), array items are not comma separated, table keys are without double qoutes (but they can't contain white spaces) and there is no separator between key-value pairs. Since it known where each value ends, item separators in arrays and tables would be purely cosmetic so I decided to drop them entirely. Strings (textual atoms) are similar to JSON's "backslash escaped" strings and I'm not very fond of it. It makes multiline text blocks look like a single line text and hard to edit. I do have an idea for a syntax that to make text blocks look more natural but I'm working on details on how to introduce it without breaking too hard the compatibility with previous version of the notation.

About IKADN

The sexiest part of the solution is an abstract notation that simplifies implementation (and to some degree design) of your own notation. Projects wiki page https://code.google.com/p/ikon-library/wiki/IKADN contains more details but in short IKADN syntax consist of following rules:

• Each data type starts with a specific character (such as "=" for numbers in IKON or "[" for array), 
• Notation designer defines how data it self looks like 
• White spaces between data are ignored.

Doesn't look like much but IKADN parser and writer considerably simplify parser and writer of  concrete notation. Official C# implementation (I intend to write more detailed post about it later), available on NuGet, contains:

• Logic for reading stream
• Handling of unexpected end of stream 
• Deciding which data type to read
• Helper methods for reading, skipping and substituting characters from the input stream 
• Helper methods for writing nicely indented IKADN document. 

For comparison, official implemention of IKADN consists of 243 lines of code while IKON implementation that uses it has 328 lines. That's 40% job done by IKADN.

How to get it

Official project web site it at Google Project Hosting: https://code.google.com/p/ikon-library/. There are source code, wiki pages and most recent build for .Net. Build is also available through NuGet.

Here is an example how to use the library. Let's say IKON document from the top of the post is in input.txt. This the code that would print the name of the star:


using System;
using System.IO;
using Ikadn.Ikon;
using Ikadn.Ikon.Types;

namespace IKON_example
{
    class Program
    {
        static void Main(string[] args)
        {
            var reader = new StreamReader("input.txt");
            using(var parser = new IkonParser(reader))
            {
                IkonComposite star = parser.ParseNext().To<IkonComposite>();
               
                Console.WriteLine(star["name"].To<string>());
            }
        }
    }
}

Parser can read form any TextReader subclass so if you want to read from string instead of file, use StringReader instead StreamReader. Also parser implements disposable patters so you can use it with using statement to ensure that input stream is closed after use.

Notice To<T>() method, it's the helper method for converting objects and the alternative to usual C#'s cast-and-get (cast an object to target type and then call a getter method). In the first case IkadnBaseObject is simply cast to IkonComposite (table type). The second case is more complex and shows true power or the method. Instead of type casting, underlying IkonText (textual type) returns it's contents as .Net string. Which types can be requested depends on the underlaying IkadnBaseObject subclass. For example, in the case of IkonNumber (numeric type) valid conversions include most native .Net numeric type (decimal, int, float, ...). In case of IkonArray (array type) one can ask for T[] (native .Net array) or IEnumerable<T> if array elements can be converter to T.

If you have any questions out the project, feel free to drop a comment. If you have a feature request or bug to report, you can file an "issue" on the project site too.

Mouse click and drag

This is a little bugger I coped with recently. In Windows forms dragging (holding a mouse button and moving the mouse) produces mouse click event after the mouse button is released. That's OK when a program is interested in only drag or click events but when it has to handle both events, each with different logic then there has to be a way to differentiate between those two events. Let's start with simple case where only mouse click is needed (C#-ish and .Net-ish code):

void init(){
    control.MouseClick.Add(clickHandler);
}

void clickHandler(object sender, EventArgs e)
{
    // Click logic
}

Now let see simple drag handler:

Point lastPos = null;
 
void init(){
    control.MouseMove.Add(moveHandler);
}

void moveHandler(object sender, MouseEventArgs e)
{
    if (lastPos == null)
        lastPos = e.Location;

    if (e.Button.HasFlag(MouseButtons.Left))
    {
        Point change = (e.Location - lastPos);
 
        // Drag logic
    }

    lastPos = e.Location;
} 

There is no need to handle the situations when mouse leaves or enters control's area because once mouse is pressed over some control, only that control will receive mouse related events. That greatly simplifies the code for handling the mouse movement. Only overhead is checking if last position has been initialized. I hope it work the same on Linux and Mac OS with Mono.

If those two pieces of code were combined, mouse drag that ends inside starting control will trigger click handler. One solution is to simply track how far was mouse dragged:

Point? lastPos = null;
double dragDist = 0;
 
void init(){
    control.MouseClick.Add(clickHandler);
    control.MouseMove.Add(moveHandler);
}

void clickHandler(object sender, EventArgs e)
{
    if (dragDist > 0)
        return;

    // Click logic
} 

void moveHandler(object sender, MouseEventArgs e)
{
    if (!lastPos.HasValue)
        lastPos = e.Location;

    if (e.Button.HasFlag(MouseButtons.Left))
    {
        Point change = (e.Location - (Size)lastPos.Value);
        dragDist += Math.Abs(change.X) + Math.Abs(change.Y);

        // Drag logic
    }
    else
        dragDist = 0;

    lastPos = e.Location;
}

Well, Euclidean distance would do too. I used Manhattan distance because the line of code is narrower and has less chance of being broken to multiple lines in your browser. Neat thing about this solutions is that border between click and drag can be adjusted to tolerate some mouse movement.

Coco/R and parsing strings

Writing a parser for Stareater with Coco/R as parser generator was easy. Despite requiring slightly different way of thinking (all terminals "return void" so output is done through method parameters with keyword out) overhead imposed by Coco/R was minimal. And then I wanted to test the parser. I figured unit tests would be appropriate and while writing first unit test I got stuck at scanner constructor. The scanner is the part that converts input to tokens (lexeme) and default Coco/R scanner can be constructed either by providing a file name (or relative path) string or the Stream object. The problem was my parser was intended for in-memory strings.

Quick googling showed that string can written to memory stream with few lines[1]. If you want to be quick and don't mind bloat you can stop reading, here your solution:

var stream = new MemoryStream(Encoding.UTF8.GetBytes(text));

Parser parser = new Parser(new Scanner(stream);

Why do I call this bloated? Because:

Under the hood default scanner implementation wraps stream with buffer. The buffer does what the name says, buffering, plus conversion of bytes to characters. I'm not going to discuss their design decisions like why didn't they use BufferedStream. When implementing IKON reader for .Net I opted for TextReader as a base class for input because conversion form input to characters is guarantied by interface and there StreamReader and StringReader classes that implement TextReader and can read from any stream or from in-memory string. Maybe they had some reason to insist on the Stream but that is not the point of this post. What is the point is that I was talking about default Coco/R scanner.

Both Coco/R parser and scanner are based upon a frame file. Those files are sort of blueprints, a C# code interleaved with placeholders for generated code. When generating parser and scanner, command line tool must be supplied with those files along with grammar specification file though they don't have to be explicitly named if they are in the same folder as grammar file. By customizing scanner's frame file parsing bloat can be reduced. Below are steps for making a frame for a scanner that only accepts string as input.

Buffers can be ditched altogether since in-memory string is already buffered and converted to collection of characters. Feel free to completle delete Buffer and UTF8Buffer classes from scanner's frame but keep in mind that generated scanner's code depends on Buffer.EOF constant. I prefer to hide it as static private nested class inside Scanner class even but it's valid to just leave original Buffer as is.

static class Buffer
{
  public const int EOF = char.MaxValue + 1;
}


Next, make an reference to input string and initialize it in constructor.


public string input; // scanner input
public Scanner (string input) {
    this.input = input;
    Init();
}


Than clean up Init method. Aside form initialization, that method detect whether the stream is encoded in ASCII or UTF-8. Since new scanner works directly with characters, encoding detection can be omitted.


void Init() {
    pos = -1; line = 1; col = 0; charPos = -1;
    oldEols = 0;
    NextCh();
    pt = tokens = new Token();  // first token is a dummy
}


And finally modify NextCh method to raise "end of file" when end of string is reached.


    void NextCh() {
        if (oldEols > 0) { ch = EOL; oldEols--; }
        else {
            pos = charPos;
            charPos++;

            if (charPos >= input.Length)
                ch = Buffer.EOF;
            else
            {
                ch = input[charPos]; col++;
                // replace isolated '\r' by '\n' in order to make
                // eol handling uniform across Windows, Unix and Mac
                if (ch == '\r' && input.Length > charPos + 1 && input[charPos + 1] != '\n') ch = EOL;
                if (ch == EOL) { line++; col = 0; }
            }
        }
-->casing1
    }


That's it! In case you want to support both strings and streams you could do similar modifications with TextReader instead of string. I haven't tried that yet since the idea occurred to me while writing this post.

Binary Domain and C-evo

It was almost to months since I wanted to write about this and there was always something in the way. I've seen first impressions of Binary Domain video game on Cynical Brit's YouTube channel and although the guy on the channel was not impressed by the game, a friend told me it was good and I was intrigued by the plot. I downloaded the demo version and what should have been fun was an agony. The controls were disaster! You'd understand my shock if I told you that I do not and never had owned a console and the game was ported from console meaning, among the other things, it was designed for a game pad instead of mouse and keyboard. On top of that I played quite a number of first person shooter on desktop computer back in '00 when they were blossoming genre there. My expectations were WASD movement, space for jump, shift for sprint, C or control for crouch, E for interaction, R for reload and mouse for aiming and shooting. Binary Domain being console port did this it's own way, WASD was there but space was kind of everything else button, sprint was some random letter (F or something like that), shift just turned character's facing direction to the left. That looked silly :). To rebind the keys you had to exit the game and use separate application. All of that would be bearable if there wasn't a lot bigger issue, aiming with mouse. When I moved mouse slowly aim kind of jumped few degrees at the time making it hard to "aim for a head", when I tried to make sharp turn, fast mouse movement was dampened to slow turn. Shooters are known to have an issue with mouse acceleration but this was opposite, mouse deceleration. Why??? Was it just on my machine or are there more players that think the game was never tested with mouse? I tried to find a quick workaround but except "use gamepad instead mouse" there was nothing. That's preposterous measure that I'm never going to take to just play a game.

After I stepped back from computer to calm down and eat lunch I figured that only reason why I wanted to play that game was a story and what is natural medium for story telling? In this case it's video and there are a few "let's plays" on the Internet for this game. "Let's plays" are something that big companies don't like and they may even be legal issue if they are monetized. But why people demand such content if video games are there to provide fun in the first place? Some games fail to deliver a fun, some games are broken, some cost more than they are worth and some people are plain lazy so they want somebody to play a game for them :). Binary Domain is broken and probably kind of game that is one time experience, once you play it through that's it, no more new stuff to do. Basically a 25€ movie, thereby it more fun to watch it than play it. What games aren't one time experience? I'd say most strategies (especially grand strategies such as Civilization series) and every game with healthy multiplayer. Out side the world of video games, chess and poker are great examples. It basically boils down to having big enough uncertainty factor and allowing player(s) to influence the outcome.

Watching a video didn't exactly fulfilled my need for interactive fun so I browsed through my good old library and decided to play a game of C-evo. C-evo is polar opposite of Binary Domain, it's PC native, can't be played without the mouse, it's turn based strategy and as most grand strategies has high replay value. I had that game for a few years and played it through about couple dozen times. It occurred to me that I never experimented much with the map size in C-evo. In grand strategies large maps tend to prolong the gameplay while not really adding to the experience, small maps on the other hand tend to be more aggressive. Peaceful expansion is concluded much sooner so wars start sooner. I opted for the smallest map, about half the size (1/4 of area) of normal map with a little bit more land. The game turned out to be easy, there were only two tiles I had to fortify in order to prevent other player from peeking and colonizing my territory and during the second session I had enough technological advantage to steam roll opponents. But the game didn't end there, oh no, it was the time form something more. It took me at least five more session to complete my plan. I could have achieved victory condition with very little effort but instead I chose to something else, something I've tried to do but never managed to pull off before, to cultivate whole planet. Since the map was small and I had almost hundred engineers (special units that can cultivate land) due to disbanding poorly placed AI's cities, it was doable. A little tedious but not to much.

That's what I expect from a game, to be a medium that can surprise and please more than once, to be significantly different experience over multiple playthroughs and to allow experimentation.

ANTLR, second chance and rivals

This post continues the story from the introduction and first impression.

It has been long month and it took me quite a while to gather the material for this post. Long story short ANTLR is no go for C#, it's rival in alpha stage is lacking and the third option finally proved worthy. Now the long story:

Last time I tried ANTLR with separate files for lexer, parser and tree processor grammars which produced "mouth feeding" process in the user code using those grammars. This time i tried ANTLR with combined grammar file, basically all three grammars in one file.

grammar MyLogoCombined;

options {
language=CSharp3;
output=AST;
}

@header {
using System;
}

fragment SIGN
: '+' | '-';
fragment SPACE
: ' ' | '\t';

NUMBER : '0' | SIGN? '1'..'9' '0'..'9'*;
FORWARD : 'FD';
ROTATE : 'RT';

NEWLINE : ('\r'? '\n')+ { Skip(); };
WHITESPACE
: SPACE+ { Skip(); };

public script : statement* EOF!;

statement
: FORWARD v=NUMBER {
double length = toDouble($v);
angle = Math.PI * this.angle / 180;
x += Math.Cos(angle) * length;
y += Math.Sin(angle) * length;
Console.WriteLine("Moved to {0}, {1}", x.ToString("0.#"), y.ToString("0.#"));
}
| ROTATE v=NUMBER {
angle += toDouble($v);
Console.WriteLine("Facing {0}°", angle.ToString("0.#"));
};

It doesn't look bad or crammed and generated code is better too. Generated classes are lexer and merged parser and tree processor. As an effect a user code required to utilize those classes got considerably simpler.

static void CombinedLogo()
{
using (var input = new StreamReader("input.txt")) {
MyLogoCombinedLexer lexer = new MyLogoCombinedLexer(new ANTLRReaderStream(input));
MyLogoCombinedParser parser = new MyLogoCombinedParser(new CommonTokenStream(lexer));
parser.script();
}
}

Now we have something usable. But I wasn't satisfied, generated code requires 100 kB run-time library (may look weird compared to executable weighting 30 kB) and is riddled with comments mentioning full path to original grammar file. And there is no way to generate code without those comments. Well, not exactly critical issues, more like unnecessary vice. There is another issue I haven't mentioned earlier, documentation is not quite there. It exists, that's good, there are a lot of examples, that's good too but you won't get your question answered on the single page. You'll have to look in the official docs, unofficial examples and still do a few experiments to get definite answers.

Irony.Net

On the Stack Overflow webpage that led me to ANTLR next recommended thing was Irony.Net. It's the project hosted on CodePlex with professional looking home page. I've downloaded source code and started looking around. The nicest thing about Irony.Net is the way of defining a grammar, there is no code generations from specially formatted text file, it's defined as ordinary C# class. I usually post code as plain text but for the sake of presentation you'll get an image this time.

That's as awesome as ANTLR's state diagram for grammar rules. Operator overloading is usually syntax evil but in some cases it's OK thing to do and Irony.Net has found one. As you can see plus and bitwise OR operators are overloaded to operate on non-terminals so the grammar rules can resemble BNF notation as closely as possible. At the same time the image presents three issues with the Irony.Net: piece of code commented out, first parameter of MakeStarRule method and lack of rule attributes (tree processor actions).

Commented out code is left on purpose to demonstrate the existence of various flags and properties. While trying to make it work I read somewhere that I should explicitly specify creation of abstract syntax tree which is usually normal process in parsers so I added that line. It turned out that Irony.Net creates syntax tree by default and that flag actually confuses it. Alright, it confused me too because it didn't work with educational material, it required extra information that I couldn't figure out within the time I had at the moment. I figured it is supposed to indicate that custom tree node objects are being used and that creation of those objects is mysterious art.

That leads us to the lack of rule attributes problem. In order to process the tree you have to either traverse the tree on your own or use the mysterious art. I really tried to figure out the mysterious art but the lack of education materials and limited time bested me (a year later after writing this post I did learn how to use visitor pattern but still, there better ways). The biggest problem with Irony.Net is the lack of documentation. It has so many features and only way to figure them out is to dig in their source code.

The weirdness of MakeStarRule method may not be obvious but why does it require destination non-terminal and why is it class member? In my opinion it should be static and have only one mandatory parameter, the repeatable BNF term. The reason why it requires destination non-terminal is because it secretly modifies the rule instead of just building the BNF term. The reason it is non-static is because it uses certain flag from the grammar object. That is actually OK because the grammar object is used to build the "language" object, not for direct parsing.

Now that I mentioned it, using the grammar is quite simple, build parser using the grammar, feed the input and get the tree:


Parser parser = new Parser(new IronyLogo());
ParseTree tree;
using (var input = new StreamReader("input.txt"))
tree = parser.Parse(input.ReadToEnd());

For processing the tree I opted for no mysterious art approach, doing it in the user code and it's not a big hassle:

double x = 0, y = 0, angle = 0;

foreach (ParseTreeNode statement in tree.Root.ChildNodes) {
ParseTreeNode node = statement.ChildNodes[0];
int value = (int)node.ChildNodes[1].Token.Value;

switch (node.Term.Name) {
case "forward":
x += value * Math.Cos(angle);
y += value * Math.Sin(angle);
break;

case "rotate":
angle += Math.PI * value / 180.0;
break;
}

Console.WriteLine("Turtle at {0}, {1}", x.ToString("0.#"), y.ToString("0.#"));
}

Neat thing is that NumberLiteral type of literals handles string to number conversion on it's own. In fact Irony.Net has a lot of features for building programming languages, custom literals for number and identifiers, methods for defining operator precedence to name a few.

So why is Irony.Net on go for C#? If you are building a compiler or interpreter, it's good but if you are build parser for domain specific language it's simply not the right tool. You can chop wood with hammer but using an axe would be more practical. First of all it requires 160 kB of run-time library, that's more than ANTLR, doesn't have elegant grammar attributes and is undocumented. Oh my God, it is so undocumented that I have to involve the God to the issue. Author himself claims that source code is enough and is unwilling to write decent documentation (well, the project is still in alpha phase so I can forgive him) and sometimes doesn't give an answer beyond "look in the code of a certain example shipped with Irony". There is a moderate number of examples included with Irony.Net source code but they are either grammars without attributes or proofs of concept (such as fully featured interpreter with a lot of layers between grammar and attributes) that are hard to follow while learning stuff.

Coco/R

Goggling for third solution led me back to Stack Overflow but to a different page this time. Answers on that page presented various new solutions and I've checked the first one (actually the second one because the first is for F#), Coco/R. The link led me to a clean black on white page where I've quickly found my way to the tutorial that hooked me up. At first I was skeptical, zip file with 5 years old Powerpoint presentation but after skipping language processing theory, presentation arrived at very simple example describing whole process, from writing a grammar to running the parser. Few slides further presented grammar attributes and gimmicks such as how to ignore new line characters, make grammar case insensitive and so on. The post is already long, but heck, I'll publish my first class Logo grammar anyway:

COMPILER Logo
double turtleX = 0, turtleY = 0, angle = 0;

IGNORECASE

CHARACTERS
digit = "0123456789".

TOKENS
number = digit {digit}.

IGNORE '\t' + '\r' + '\n'

PRODUCTIONS
Logo = {Statement}.
Statement = Forward | Rotate.

Forward (. double length; .)
= "fd" Parameter<out length>
(. turtleX += Math.Cos(angle) * length;
turtleY += Math.Sin(angle) * length;
Console.WriteLine("Turtle at {0}, {1}", 
turtleX.ToString("0.#"), 
turtleY.ToString("0.#"));
.)
.

Rotate (. double ang; .)
= "rt" Parameter<out ang>
(. angle += Math.PI * ang / 180; .)
.

Parameter<out double n>
= number (. n = Convert.ToDouble(t.val); .)


.
END Logo.

You've already seen something similar with ANTLR grammar, lexical tokens, extenden BNF production, c# header and attributed code. This one has a period character after almost everything. One thing I should point out is that parts of definition have to strictly follow an order of appearance. For instance IGNORE part can't appear before TOKENS or CHARACTERS blocks. Correct order of appearance can be found in the documentation that exists and is informative. Before I start praising it's documentation, let's conclude the usage of Coco/R. This is what user code looks like:

static void Main(string[] args)
{
Scanner scanner = new Scanner("input.txt");
Parser parser = new Parser(scanner);
parser.Parse();
}

As simple as that. Scanner can also accept Stream object instead of file name, for those insisting on abstraction (which is good requirement).

Conclusion

Unlike ANTLR or Irony.Net, Coco/R didn't catch me with nasty surprises, it's simple, it works, requires no run-time files and it is well documented. Though it doesn't have fancy grammar editor or grammar visualisation it's a tool that I would use in my projects.

ANTLR, first impression

This post continues the story from the previous one.

So, following Stack Overflow link I landed at ANTLR homepage. Psychological scam alarms went off, bunch of text riddled with hyperlinks and varying typefaces, prominent button accompanied with "Oh come on, download me now", testimonials column and a guy making silly face. It took me a few seconds to actually start comprehending the content. Image below silly guy encouraged me to stay, it looked like FSA visualization I once saw during the college and FSA are crucial part of formal language processors. I started to search for something that identifies what the site is about and I read the first few lines:

What is ANTLR?
ANTLR, ANother Tool for Language Recognition,
... lot of technical terms that ordinary eye skips ...
 target language.

"OK, that looks like what I'm looking for", said to myself. I'll stop with through storytelling now and the silly guy is Terence Parr, the guy behind the ANTLR project. Anyway, next thing was to have a taste how the tool works. I was disappointed at first with a fact that it is a command line tool but that wouldn't stop me from learning it. Soon I've found out that it has additional tool with GUI, ANTLRWorks, so I downloaded it and started looking for some kind of tutorial. Thing is with this kind of software that you have to learn a metalanguage for defining grammar rules and examples are best way to start. I've found a good one on a different web site. It's an example of not so basic calculator/interpreter for Java. I copy-pasted all three grammars ANTLRWorks, pressed "generate code" button and it worked. I had a clue how it works but wasn't really ready to work on my own so I've tried different approach, make a parser for a very simple language.

If you remember old days in LOGO, you'll smile. My first informatics class in elementary school (5th grade, I remember it as if it was yesterday :) ) was about LOGO and moving the turtle with FD and RT commands. FD 100 moved the turtle forward 100 pixels and as it moved it left a straight line. RT 90 rotated turtle 90° clockwise. Repeat that four times and you'd draw a rectangle. That's the simple a language I've decided to parse. Also, I've decided to split the grammar to three parts because last example did so and I believed it's a proper way to do and this was my grammar file for lexer:

lexer grammar MyLogoLexer;

options {
language=CSharp3;
}

fragment SIGN
: '+' | '-';
fragment SPACE
: ' ' | '\t';

NUMBER : '0' | SIGN? '1'..'9' '0'..'9'*;
FORWARD : 'FD';
ROTATE : 'RT';

NEWLINE : ('\r'? '\n')+ { Skip(); };
WHITESPACE
: SPACE+ { Skip(); };

Pretty simple vocabulary, white spaces are skipped, digits are treated as numbers and keywords are FD and RT. Second grammar describes what is formally called the parser, a syntax analyzer and a part that build a syntax tree. For the language I was building, the parser was even simpler than lexer:

parser grammar MyLogoParser;

options {
language=CSharp3;
output = AST;
tokenVocab = MyLogoLexer;
}

script : statement* EOF!;

statement
: FORWARD NUMBER
| ROTATE NUMBER;

Basicaly the root of the tree is a script. Script contains zero or more statements and statements are either "forward" or "rotate" commands. ANTLRWorks is full of little features that help writing and validating grammar and graphical representation of a rule is one of them. Look at how nice it is, feast your eyes on it's awesomeness:

And now the last grammar, so called tree grammar, not because it builds the tree but because it traverses the tree and performs node actions:

tree grammar MyLogoTree;

options {
language=CSharp3;
ASTLabelType = CommonTree;
tokenVocab = MyLogoParser;
}

@header {
using System;
}

@members {
double x = 0, y = 0, angle = 0;

private double toDouble(CommonTree node) {
double value = 0.0;
   String text = node.Text;
   value = Double.Parse(text);
   return value;
  }
}
script : statement*;

statement 
: FORWARD v=NUMBER {
double length = toDouble($v);
angle = Math.PI * this.angle / 180;
x += Math.Cos(angle) * length;
y += Math.Sin(angle) * length;
Console.WriteLine("Moved to {0}, {1}", x.ToString("0.#"), y.ToString("0.#"));
}
| ROTATE v=NUMBER {
angle += toDouble($v);
Console.WriteLine("Facing {0}°", angle.ToString("0.#"));
};

When I wrote grammars, I've hit "generate code" button, got errors, corrected them, retried and after a few tries it succeeded. And than I got my self in from of the weird wall, how to run the generated code? It was midnight already and I was trying to break the habit staying up late. I should have been trivial matter but it turned out that it took two hours of my life. I expected that generated source code looked like this:

From the perspective of the user code, a single class that does the job. But instead it turned out that user's code has to mouth feed EVERY phase on it's own. See:

Notice the absence of gray arrows. Thing are even worse, there are additional objects the user code has to take care of besides generated classes. Mimicking the the Java example ("not so basic calculator" mentioned at the beginning), I figured the code should look like this:

static void Main(string[] args)
{
using (var input = new StreamReader("input.txt")) {
MyLogoLexer lexer = new MyLogoLexer(new ANTLRReaderStream(input));

MyLogoParser tokenParser = new MyLogoParser(new CommonTokenStream(lexer));
tokenParser.TreeAdaptor = new CommonTreeAdaptor();
var parserResult = tokenParser.script();

CommonTree tree = (CommonTree)parserResult.Tree;
MyLogoTree treeProcessor = new MyLogoTree(new CommonTreeNodeStream(tree));

treeProcessor.script();
}
}

But there were two big problems: parser's script method was private and tree processor's script method didn't exist at all. For method visibility issue the Google led me back to the Stack Overflow. Each parser and tree grammar generates a method and there is an undocumented feature that defines visibility of such methods. When generating Java code, the feature is ignored and all methods are public but when generating C# code methods are private unless the undocumented feature is used. Since the example that I used as learning material was meant to generate Java code, it didn't mention this issue. The lack of script method in tree parser was my fault entirely, I didn't noticed that the grammar rules has to be repeated in the tree processor even if they have no action. I mean, not all rules have to be repeated, only those that should generate a method.

To summarize, half of the workflow is good, enjoyable and looks mature but the other half is drastically unpolished. That contrast is the problem too, at first you'd live in high hopes that you are working in mature IDE such as Eclipse and Visual Studio and than BAM, this doesn't work, that doesn't work the way you thought and so on.

As I woke up next morning I looked at other options, there aren't looking better than ANTLR. There is one with nice premise but it's in alpha phase. So I decided to try that one and to give ANTLR another chance.

ANTLR, introduction

I did a little research on libraries for processing formal languages, both for my self and for the project I'm working on, the Stareater. Previous versions of Stareater had a feature that allowed having whole expressions instead of plain constant numbers in data files. For instance, for farmer efficiency you could write something that evaluates to 3+0.125*level of farming technology in a single attribute instead of having multiple attributes, one for constant part, one for technology identifier and one for technology level influence factor. And on top of that, you can change operators in an expression any way you want. But there is a catch, you have to write it either normal or reverse Polish notation (postfix and prefix notations respectively) so the last example would look like this (highlighted part):

It's bearable when expressions are simple but take a look at the image below. That is an expression for the maximum number of  starports on a planet. Floor is a function for rounding down, "^" is the power operator, PLANET_VELICINA is the size of a planet and SVEMIRSKI_PROGRAM_LVL is a level of relevant technology.

It translates to Floor( (1 + 0.1 * (tech_level - 1)) * (planet_size ^ 1.5) / 100 ). So, why Polish notation instead of "plain English", the infix notation? I wrote about it before but this is a summary: it's easy to parse. Parser implementation is straightforward there is no operator precedence issue. For instance, evaluator of postfix notation expression could be explained in a few sentences (knowledge of basic data structures assumed): read input from left to right, add operands to the top of the stack, apply operators to the operands on the top of the stack, remove used operands and push the result to the top of the stack. If the expression was valid, in the end stack would contain only one element and that would be the result of the expression. Parser is very similar to described evaluator but instead of calculation, the so called syntax tree is built. What is syntax tree you might wonder. Well now we are stepping in the area of computer science and the rest of the post will assume that you have some degree of familiarity with the field of formal language processing.

This, the picture above, is the syntax tree for 3+0.125*level of farming expression. Arrow at the top points to the root of the tree (knowledge of the trees from graph theory assumed). To get the value of the expression, user code (the one using the tree) has to simply ask the root to evaluate itself. Rest is the magic of composite design pattern, root would see that it needs two or more operands and sum them and it will ask it's children to evaluate them self. Since the first child is a constant, it will simply return 3. Second child on the other hand will ask it's children to evaluate themselves and multiply their values. As you can see a nice utilization of recursion and dynamic polymorphism.

Building syntax tree for infix expression complicated thing, at first there are binary operators (assumed reader knows what that mean) which have one set of not-so-easy-to-implement rules, then add to the mix unary operators and you'd get stuff complicated by factor 1.5 and things can be complicated even further with brackets and functions. On top of that you have to decide whether a / b / c should be interpreted as (a / b) / c, a / (b / c) or rejected as invalid. It would be hell to code and test all of it from scratch. Fortunately our fathers and grandfathers solved that for us when they invented compilers. Programmers use compilers for transforming a source code to an executable files but compilers are more general then that, they translate one language to another. In case of C++, source code written by the rules of C++ is translated to a machine code of the target hardware. There is fair amount of computer science theory involved here and it is named the formal language.

Main phases of compilation process

Every programming language is formal language and as such they have vocabulary (set of lexemes), grammar rules (syntax) and semantic rules. Vocabulary usually contains list of keywords (if, for and default for example) and regular expressions for variable names, constant numeric and textual values and other simple stuff though regular expressions are formal languages of their own. Grammar rules define more complicated stuff such as assignment has form of variable followed by '=' character followed by expression and ended with ';'. Semantic rules cover stuff which are hard to cover by the grammar such as checking if the type of a value can be stored in a variable. There are tools for generating source code for compiler's analysis phases, an inception one might say.

Problem of parsing text containing infix expression is basically that, lexical, syntax and semantic analysis. So I goggled a little bit for C# solutions and found that most queries lead to ANTLR, Java tools that can generate C# source code from grammar rules. More about my impressions with the tool in the following post(s).