<< Click to Display Table of Contents >> Navigation:  Introduction > Parser and object structures > More about parsing (ANTLR)

In the previous section, some benefits of using a 'real' parser were explained. ANTLR was chosen as parser because it is a mature and stable product (and open source). Using a parser like ANTLR has a rather steep learning curve, but the benefits are large in number:

 

•The parser outputs a two-dimensional structure (a so-called AST tree) of the command file, whereas a tokenizer only outputs in one dimension (a flat list).

•The parser keeps track of all the rules of the grammar, such as matching parentheses and so on. The parser will produce an error message if a particular line cannot be understood, and try to point to the exact offending position in the command (file).

•The parser may try to interpret a given Gekko command in different ways, until it finds some combination of language rules consistent with the command.

•The parser output (AST tree structure) is very well-suited for translation of the Gekko command file into C# code.

•The parser grammar keeps the rules of the language in one convenient place (the ANTLR grammar file), so that grammar rules are not spread around the entire Gekko source code.

 

A parser like ANTLR is a two-part machine, where the lower part (lexer) is really mostly a tokenizer, whereas the upper part is a parser that tries to parse the tokens. The two parts of the machine know nothing of one another: the only connection is that the lower part feeds tokens into the upper part. This division of labor is done for efficiency reasons, so that the parser can operate on tokens (strings/blocks of characters) and try to combine those into something meaningful, rather than combining individual characters (lexerless parsers do exist, but are rare). From a user perspective, the problem with this is that the lexer (tokenizer) has no context: it just naively chops up a sequence of characters into words/tokens, and knows nothing about what kind of token the parser might expect to come up next.

 

Understanding how tokens are created is a key to understanding why ANTLR might refuse to make sense of a given input. But the parser might also fail on its own, especially if it gets lost in the language rules, taking the wrong path so to say (there are backtracking features available to the parser though). Some experience with parsers pays off in that case, but it should be said that ANTLR most often behaves as expected and can transform long complicated mathematical expressions into nice AST trees without a hitch (and very quickly). ANTLR is also used to parse model files, by the way.

 

We repeat here the series statement shown in the previous section, and its corresponding AST tree:

 

 

       

 

The actual ANTLR grammar file used to parse the series statement could be something like the following:

 

 

 

The assignment rule can be broken up in the following way:

 

•dates is a rule that expects two concecutive expressions (which can be integers, dates like 2010q3, or mathematical expressions). The ? indicates that the <> bracket is optional, and can be omitted.

•Next is a reference to the name rule which in turn expects a token of Ident type from the lexer, where Ident is a sequence of letters and digits (where the first character is not a digit). More on Ident type in the later section on AST trees.

•The operator rule expects one of the legal operators (simplified here to only accept =, *= or +=, and the | means logical OR).

•Finally the data rule expects one or more expressions, separated by comma (the * means repeated 0 or more times).

 

In the actual parser grammar, there is also a rewrite rule, so the assignment rule actually looks like the following:

 

 

The rewrite follows the -> arrow. This is where the actual AST tree corresponding to the command is produced. In general, in the rewrite rules, ^(x1 x2 x3 ...) tells ANTLR to create a new AST node with x1 as the parent node, and x2, x3, etc. as the children nodes. So a parent node ASTASSIGNMENT is created, with ASTNAME, ASTDATES, ASTOPERATOR, and ASTDATA as children nodes. And for instance the ASTDATES node will have two children nodes (if dates are given in the series statement), namely two expressions (in our case these expressions are simply two integers).

 

The tree structure is maybe not that necessary for such a relatively "flat" series statement, but with nested mathematical expressions on the right-hand side, these AST trees can become quite deep and involved. When emitting C# code corresponding to the Gekko command (file), only the above tree is used. The C# code is produced in small chunks while Gekko walks through the nodes of the tree one by one. For instance, the ASTASSIGNMENT node might know that it should emit the following C# code:

 

 

This can be done using a kind of schema:

 

 

where the {i} are replaced by values of the child nodes (the C# code that these nodes contain), to produce the C# code of the ASTASSIGNMENT node.

 

The statement O.Lookup("x1", 2010, 2015, "=", 150); could be used directly in C#, provided that Gekko has a suitable Lookup() method defined. This is actually not the precise way it is done in Gekko, but the basic idea is very similar.

 

The drawbacks of using a parser like ANTLR is a rather steep learning curve, and some frustrations while learning the difference between a lexer and a parser etc. There may also be frustrations if ANTLR deems a particular grammar invalid, or refuses to parse some command line that ought to be parseable. On the other hand, much of the work on Gekko is adding new commands and options that are quite similar syntax-wise to existing ones, and in that case it is easy to write new grammar rules while keeping an eye on existing ones as inspiration. Producing C# code from these rules is not that difficult either, as long as we are not talking about fundamental changes to grammar or data types.

 

Providing Gekko capabilities like mathematical expressions, functions, procedures, list logic, composite names (x{%}y) etc. -- not to mention translating that into reasonably well-structured C# code -- without a parser like ANTLR would indeed be a tough task. Some occasional frustrations with ANTLR fade in comparison with that alternative.

 

 

Note about ANTLR

 

When ANTLR works, it works good. When it does not work, for instance if it does not transform a statement into the expected AST tree (or simply refuses to parse a valid Gekko statement), it can be a hassle. One annoying thing about ANTLR is that the newest version (ANTLR 4) is not capable of emitting AST trees, and therefore Gekko cannot upgrade from ANTLR 3 to ANTLR 4. This is really annoying, not least because the author of ANTLR has been advokating AST trees as something like the best invention since sliced bread. More about this in the this Gekko blog post.

 

This has harmed the feeling of loyalty regarding ANTLR, and in the longer run, it would probably pay off to use one's own parser. Writing a recursive descent parser (using tokens as inputs) for a syntax like Gekko's should not be particularly difficult, and then there would be no dependence on an outdated ANTLR version (ANTLR 3). Handcoded parsers are often used for the compilation of computer languages, by the way.

 

So for the time being, Gekko uses ANTLR 3, which is frozen in time. But when it works, it is reliable and fast enough. As mentioned above, if ANTLR is scrapped for use in Gekko, so-called scannerless parsing could perhaps be interesting.