« May 2007 | Main | July 2007 »
June 12, 2007
The ANTLR Trinity
There are 3 components to a really useful software development technology: innovative features, clear and comprehensive documentation, and solid tools. The recent release of ANTLR v3.0 is a perfect example of this. This parser generator tool has all 3 components and each component is done superbly.
ANTLR is a parser generator tool that is capable of targeting multiple output languages. Out of the box, it will generate Java, Python, C, C#, or Ruby code. Other target languages are possible if the code generators are written. Amongst its cool features are:
LL(*) parsing: This is an extension to the normal, top down with lookahead, LL(k) parsing technique. It allows for more powerful parsers than those possible with LL(k). Not something I have needed yet, but I can see it being useful in the future.
Semantic and syntactic predicates: These are tests that can be embedded in grammar rules to turn certain choices in rules on and off based on a boolean test. These allow parsers to be built that simulate recognizers for context dependent grammars and this makes the automated parser generation applicable to a lot more problems. Again, this is something I haven't used yet, but will be in the future.
Memoized backtracking: This is a performance improving feature for grammars that use a lot of lookahead. If a parser fails at a choice near the end of the rule it has to go back to the start of the rule and start matching again. The memoization of intermediate matches for a rule speeds this up.
Unicode support: parsers built with ANTLR recognize Unicode input. ANTLR grammar files themselves do not recognize Unicode characters yet, but Unicode characters can be specified as escape sequences.
Hierarchical lexers: Most parser generator tools define tokens by means of a regular expression like language. For these tools lexer rules are independent of each other and cannot refer to each other. ANTLR is different: it allows lexer rules to reference other lexer sub-rules. It also allows recursive lexer rules. Now, this is a very useful feature and, for me, tidies up lexer rules a lot.
Abstract Syntax Tree (AST) generation features: ANTLR has a powerful AST generation feature. When generating parsers I prefer to generate a parse tree or AST and pass that onto a second stage, rather than embedding actions/code in the grammar. This allows the a parser to be used as a module in numerous tools. ANTLR's AST building support is superb and really facilitates that type of design.
Tree grammars: This is a feature of ANTLR that allows for a parser to match tree structures such as ASTs and trigger an action based on this. I used to use JavaCC and what I normally did was use it to generate a parse tree and then use the visitor pattern to process that parse tree. If the action at a particular node depended on the structure of the tree, it was up to me to track that in the Java code in the visitor class. ANTLR's tree grammars really simplify situations like that and I am really looking forward to trying that out.
The Definitive ANTLR Guide, available from the Pragmatic Programmer website, is the main documentation for ANTLR v3.0. The book is well named. It clearly and concisely describes the features of ANTLR v3.0 and how to use them. The book is divided into 3 sections: an introduction to ANTLR and language translation, a reference section for the ANTLR syntax, and a section on how to write predicated LL(*) grammars. I have read through the first section and skimmed parts of the reference and this has enabled me to put together a basic parser/recognizer for Scheme. It really is that straight forward.
In addition to The Definitive ANTLR Guide there is a really good Wiki with tutorials and FAQs at http://www.antlr.org/wiki/display/ANTLR3/ANTLR+3+Wiki+Home. Lastly, the distribution comes with great sample grammars. There is a Java grammar and a Python grammar in there and these put ANTLR through its paces and are worth referring to.
ANTLRWorks is the IDE for building ANTLR grammars. It is a standalone editor, written in Java Swing, that provides the standard features that you would expect from an IDE, such as syntax highlighting and error detection. In addition it has a few handy features that you would not expect. Firstly, there is a syntax diagram pane in the GUI. Selecting a grammar rule in editor pane causes a syntax diagram for the rule to be displayed in the syntax diagram pane. The graphic below is an example.
This is very useful for documenting grammars as the diagrams can be saved as graphics (JPEG, PNG, EPS, etc.). There is also a debugger and an interpreter. The interpreter will interpret the grammar and draw a graphical representation of the parse tree for an input string based on the grammar. If the parse fails it still draws the diagram for what was recognized and puts a node in the tree, at the point were the parse failed, to represent the type of error detected. The parse tree graphics can also be saved and are a real help with visualizing how the rules fit together and what choices the parser is taking.
Technorati Tags: programming antlr
Posted by JohnC at 10:15 PM