Maybe you have read some tutorial that was too complicated or so partial that seemed to assume that you already know how to use a parser. This is not that kind of tutorial. We just expect you to know how to code and how to use a text editor or an IDE. That\u2019s it.<\/p>\n
At the end of this tutorial:<\/p>\n
- \n
- you will be able to write a parser to recognize different formats and languages<\/li>\n
- you will be able to create all the rules you need to build a lexer and a parser<\/li>\n
- you will know how to deal with the common problems you will encounter<\/li>\n
- you will understand errors and you will know how to avoid them by testing your grammar.<\/li>\n<\/ul>\n
In other words, we will start from the very beginning and when we reach the end you will have learned all you could possible need to learn about ANTLR.<\/p>\n
![](\"http:\/\/www.javacodegeeks.com\/wp-content\/uploads\/2017\/03\/ANTLR-Mega-Tutorial_Finale_Second.png\")
<\/a><\/p>\nANTLR Mega Tutorial Giant List of Content<\/p>\n
What is ANTLR?<\/h2>\n
ANTLR is a parser generator, a tool that helps you to\u00a0create parsers. A parser takes a piece of text and transform it in an organized structure<\/strong>, such as an Abstract Syntax Tree (AST). You can think of the AST as a story describing the content of the code or also as its logical representation created by putting together the various pieces.<\/p>\n
![\"\"](\"http:\/\/www.javacodegeeks.com\/wp-content\/uploads\/2017\/03\/798px-Abstract_syntax_tree_for_Euclidean_algorithm.svg_.png\")
<\/a><\/p>\nGraphical representation of an AST for the Euclidean algorithm<\/p>\n
What you need to do to get an AST:<\/p>\n
- \n
- define a lexer and parser grammar<\/li>\n
- invoke ANTLR: it will generate a lexer and a parser in your target language (e.g., Java, Python, C#, Javascript)<\/li>\n
- use the generated lexer and parser: you invoke them passing the code to recognize and they return to you an AST<\/li>\n<\/ol>\n
So you need to start by defining a lexer and parser grammar\u00a0for the thing that you are analyzing. Usually the \u201cthing\u201d is a language, but it could also be a data format, a diagram, or any kind of structure that is represented with text.<\/p>\n
Aren\u2019t regular expressions\u00a0enough?<\/h2>\n
If you are the typical programmer you may ask yourself why can\u2019t I use a regular expression<\/em>? A regular expression is quite useful, such as when you want to find a number in a string of text, but it also has many limitations.<\/p>\n
The most obvious is the lack of recursion: you can\u2019t find a (regular) expression inside another one, unless you code it by hand for each level. Something that quickly became unmaintainable. But the larger problem is that it\u2019s not really scalable: if you are going to put together even just a few regular expressions, you are going to create a fragile mess that would be hard to maintain.<\/p>\n
\n
It\u2019s not that easy to use regular expressions<\/p>\n<\/blockquote>\n
Have you ever tried parsing HTML with a regular expression? It\u2019s a terrible idea, for one you risk summoning Cthulhu<\/a>, but more importantly it doesn\u2019t really work<\/strong>. You don\u2019t believe me?\u00a0Let\u2019s see, you want to find the elements of a table, so you try a regular exprdatession like this one:
<table>(.*?)<\/table><\/code>. Brilliant! You did it! Except somebody adds attributes to\u00a0their table, such asstyle<\/code> orid<\/code>. It doesn\u2019t matter, you do this<table.*?>(.*?)<\/table><\/code>, but you actually cared about the data inside the table, so you then need to parsetr<\/code> andtd<\/code>, but they are full of tags.<\/p>\nSo you need to eliminate that, too. And somebody dares even to use comments like <!\u2014 my comment >l\u2014>. Comments can be used everywhere, and that is not easy to treat with your regular expression. Is it?<\/p>\n
So you forbid the internet to use comments in HTML: problem solved.<\/p>\n
Or alternatively you use ANTLR, whatever seems simpler to you.<\/p>\n
ANTLR\u00a0vs writing your own parser by hand<\/h2>\n
Okay, you are convinced, you need a parser,\u00a0but why to use a parser generator like ANTLR instead of building your own?<\/p>\n
\n
The main advantage of ANTLR is productivity<\/p>\n<\/blockquote>\n
If you actually have to work with a parser all the time, because your language, or format, is evolving,\u00a0you need to be able to keep the pace, something you can\u2019t do if you have to deal with the details of implementing a parser. Since you are not parsing for parsing\u2019s sake, you must have the chance to concentrate on accomplishing your goals. And ANTLR make it much easier to do that, rapidly and cleanly.<\/p>\n
As second thing, once you defined your grammars you can ask ANTLR to generate multiple parsers in different languages. For example you can get a parser in C# and one in Javascript to parse the same language in a desktop application and in a web application.<\/p>\n
Some people argue that writing a parser by hand you can make it faster and you can produce better error messages. There is some truth in this, but in my experience parsers generated by ANTLR are always fast enough. You can tweak them and improve both performance and error handling by working on your grammar, if you really need to. And you can do that once you are happy with your grammar.<\/p>\n
Table of Contents or\u00a0ok, I am convinced, show me what you got<\/em><\/h2>\n
Two small notes:<\/p>\n
- \n
- in the companion repository of this tutorial<\/a> you are going to find all the code with testing, even where we don\u2019t see it in the article<\/li>\n
- the examples will be in different languages, but the knowledge would be generally applicable to any language<\/li>\n<\/ul>\n
Setup<\/h3>\n
- \n
- Setup ANTLR<\/a><\/li>\n
- Javascript Setup<\/a><\/li>\n
- Python Setup<\/a><\/li>\n
- Java Setup<\/a><\/li>\n
- C# Setup<\/a><\/li>\n<\/ol>\n
Beginner<\/h3>\n
- \n
- Lexers and Parsers<\/a><\/li>\n
- Creating a Grammar<\/a><\/li>\n
- Designing a Data Format<\/a><\/li>\n
- Lexer Rules<\/a><\/li>\n
- Parser Rules<\/a><\/li>\n
- Mistakes and Adjustments<\/a><\/li>\n<\/ol>\n
Mid-Level<\/h3>\n
- \n
- Setting Up the Chat Project in Javascript<\/a><\/li>\n
- Antlr.js<\/a><\/li>\n
- HtmlChatListener.js<\/a><\/li>\n
- Working with\u00a0a Listener<\/a><\/li>\n
- Solving Ambiguities with Semantic Predicates<\/a><\/li>\n
- Continuing the Chat in Python<\/a><\/li>\n
- The Python Way of Working with a Listener<\/a><\/li>\n
- Testing with Python<\/a><\/li>\n
- Parsing Markup<\/a><\/li>\n
- Lexical Modes<\/a><\/li>\n
- Parser Grammars<\/a><\/li>\n<\/ol>\n
Advanced<\/h3>\n
- \n
- The Markup Project in Java<\/a><\/li>\n
- The Main App.java<\/a><\/li>\n
- Transforming Code with ANTLR<\/a><\/li>\n
- Joy and Pain of Transforming Code<\/a><\/li>\n
- Advanced Testing<\/a><\/li>\n
- Dealing with Expressions<\/a><\/li>\n
- Parsing Spreadsheets<\/a><\/li>\n
- The Spreadsheet Project in C#<\/a><\/li>\n
- Excel is Doomed<\/a><\/li>\n
- Testing Everything<\/a><\/li>\n<\/ol>\n
Final Remarks<\/h3>\n
- \n
- Tips and Tricks<\/a><\/li>\n
- Conclusions<\/a><\/li>\n<\/ol>\n
Setup<\/h2>\n
In this section we prepare our development environment to work with ANTLR: the parser generator tool, the supporting tools and the runtimes for each language.<\/p>\n
1.Setup ANTLR<\/h2>\n
ANTLR is actually made up of two main parts: the tool, used to generate the lexer and parser, and the runtime, needed to run them.<\/p>\n
The tool will be needed just by you, the language engineer, while the runtime will be included in the final software using your language.<\/p>\n
The tool is always the same no matter which language you are targeting: it\u2019s a Java program that you need on your development machine. While the runtime is different for every language and must be available both to the developer and to the user.<\/p>\n
The only requirement for the tool is that you have installed at least Java 1.7<\/strong>. To install the Java program you need to download the last version from the official site, which at the moment is:<\/p>\n
http:\/\/www.antlr.org\/download\/antlr-4.6-complete.jar<\/pre>\n
Instructions<\/h3>\n
- \n
- copy the downloaded tool where you usually put third-party java libraries (ex.
\/usr\/local\/lib <\/code>orC:\\Program Files\\Java\\lib<\/code>)<\/li>\n- add the tool to your
CLASSPATH<\/code>. Add it to your startup script (ex..bash_profile<\/code>)<\/li>\n- (optional) add also aliases to your startup script to simplify the usage of ANTLR<\/li>\n<\/ol>\n
Executing the instructions on\u00a0Linux\/Mac OS<\/h4>\n
\/\/ 1.\r\nsudo cp antlr-4.6-complete.jar \/usr\/local\/lib\/\r\n\/\/ 2. and 3.\r\n\/\/ add this to your .bash_profile\r\nexport CLASSPATH=\".:\/usr\/local\/lib\/antlr-4.6-complete.jar:$CLASSPATH\"\r\n\/\/ simplify the use of the tool to generate lexer and parser\r\nalias antlr4='java -Xmx500M -cp \"\/usr\/local\/lib\/antlr-4.6-complete.jar:$CLASSPATH\" org.antlr.v4.Tool'\r\n\/\/ simplify the use of the tool to test the generated code\r\nalias grun='java org.antlr.v4.gui.TestRig'<\/pre>\n
Executing the instructions on Windows<\/h4>\n
\/\/ 1.\r\nGo to System Properties dialog > Environment variables\r\n-> Create or append to the CLASSPATH variable\r\n\/\/ 2. and 3. Option A: use doskey\r\ndoskey antlr4=java org.antlr.v4.Tool $*\r\ndoskey grun =java org.antlr.v4.gui.TestRig $*\r\n\/\/ 2. and 3. Option B: use batch files\r\n\/\/ create antlr4.bat\r\njava org.antlr.v4.Tool %*\r\n\/\/ create grun.bat\r\njava org.antlr.v4.gui.TestRig %*\r\n\/\/ put them in the system path or any of the directories included in %path%<\/pre>\n
Typical Workflow<\/h3>\n
When you use ANTLR you start by writing a grammar<\/em>, a file with extension
.g4<\/code> which contains the rules of the language that you are analyzing. You then use theantlr4<\/code> program to generate the files that your program will actually use, such as the lexer and the parser.<\/p>\nantlr4 <options> <grammar-file-g4><\/pre>\n
There are a couple of important options you can specify when running
antlr4<\/code>.<\/p>\nFirst, you can specify the target language, to generate a parser in Python or JavaScript or any other target different from Java (which is the default one). The other ones are used to generate visitor and listener (don\u2019t worry if you don\u2019t know what these are, we are going to explain it later).<\/p>\n
By default only the listener is generated, so to create the visitor you use the\u00a0
-visitor<\/code> command line option, and-no-listener<\/code> if you don\u2019t want to generate the listener. There are also the opposite\u00a0options,-no-visitor<\/code> and-listener<\/code>, but they are the default values.<\/p>\nantlr4 -visitor <Grammar-file><\/pre>\n
You can optiofi test\u00a0your grammar using a little utility named
TestRig (<\/code>although, as we have seen, it\u2019s usually aliased togrun<\/code>).<\/p>\ngrun <grammar-name> <rule-to-test> <input-filename(s)><\/pre>\n
The filename(s) are optional and you can instead analyze the input that you type on the console.<\/p>\n
If you want to use the testing tool you need to generate a Java parser, even if your program is written in another language. This can be done just by selecting a different option with
antlr4<\/code>.<\/p>\nGrun is useful when testing manually the first draft of your grammar. As it becomes more stable you may want to relay on automated\u00a0tests (we will see how to write them).<\/p>\n
Grun<\/code> also has a few useful options:-tokens<\/code>, to shows the tokens detected,\u00a0-gui<\/code> to generate an image of the AST.<\/p>\n2. Javascript Setup<\/h2>\n
You can put your grammars in the same folder as\u00a0your Javascript files. The file containing the grammar must have the same name of the grammar, which must be declared at the top of the file.<\/p>\n
In the following example the name is
Chat<\/code> and the file isChat.g4<\/code>.<\/p>\nWe can create the corresponding Javascript parser simply by specifying the correct option with the ANTLR4 Java program.<\/p>\n
antlr4 -Dlanguage=JavaScript Chat.g4<\/pre>\n
Notice that the option is case-sensitive, so pay attention to the uppercase \u2018S\u2019. If you make a mistake you will receive a message like the following.<\/p>\n
error(31): ANTLR cannot generate Javascript code as of version 4.6<\/pre>\n
ANTLR can be used both with
node.js<\/code> and in the browser. For the browser you need to usewebpack<\/code> orrequire.js<\/code>. If you don\u2019t know how to use either of the two you can look at the official documentation for some help<\/a>\u00a0or read this tutorial on antlr in the web<\/a>. We are going to usenode.js<\/code>, for which you can install the ANTLR runtime simply by using the following standard command.<\/p>\nnpm install antlr4<\/pre>\n
3. Python Setup<\/h2>\n
When you have a grammar you put that in the same folder as\u00a0your Python files. The file must have the same name of the grammar, which must be declared at the top of the file. In the following example the name is
Chat<\/code> and the file isChat.g4<\/code>.<\/p>\nWe can create the corresponding Python parser simply by specifying the correct option with the ANTLR4 Java program. For Python, you also need to pay attention to the version of Python, 2 or 3.<\/p>\n
antlr4 -Dlanguage=Python3 Chat.g4<\/pre>\n
The runtime is available from PyPi so you just can install it using pio.<\/p>\n
pip install antlr4-python3-runtime<\/pre>\n
Again, you just have to remember to specify the proper python version.<\/p>\n
4. Java Setup<\/h2>\n
To setup our Java project using ANTLR you can do things manually. Or you can be a civilized person and use Gradle or Maven.<\/p>\n
Also, you can look in ANTLR plugins for your IDE.<\/p>\n
4.1 Java Setup using Gradle<\/h3>\n
This is how I typically setup my Gradle project.<\/p>\n
I use a Gradle plugin to invoke ANTLR and I also use the IDEA plugin to generate the configuration for IntelliJ IDEA.<\/p>\n
dependencies {\r\n antlr \"org.antlr:antlr4:4.5.1\"\r\n compile \"org.antlr:antlr4-runtime:4.5.1\"\r\n testCompile 'junit:junit:4.12'\r\n}\r\n \r\ngenerateGrammarSource {\r\n maxHeapSize = \"64m\"\r\n arguments += ['-package', 'me.tomassetti.mylanguage']\r\n outputDirectory = new File(\"generated-src\/antlr\/main\/me\/tomassetti\/mylanguage\".toString())\r\n}\r\ncompileJava.dependsOn generateGrammarSource\r\nsourceSets {\r\n generated {\r\n java.srcDir 'generated-src\/antlr\/main\/'\r\n }\r\n}\r\ncompileJava.source sourceSets.generated.java, sourceSets.main.java\r\n \r\nclean{\r\n delete \"generated-src\"\r\n}\r\n \r\nidea {\r\n module {\r\n sourceDirs += file(\"generated-src\/antlr\/main\")\r\n }\r\n}<\/pre>\nI put my grammars under src\/main\/antlr\/<\/em> and the gradle configuration make sure they are generated in the directory corresponding to their package. For example, if I want the parser to be in the package me.tomassetti.mylanguage<\/em> it has to be generated into generated-src\/antlr\/main\/me\/tomassetti\/mylanguage<\/em>.<\/p>\n
At this point I can simply run:<\/p>\n
# Linux\/Mac\r\n.\/gradlew generateGrammarSource\r\n \r\n# Windows\r\ngradlew generateGrammarSource<\/pre>\n
And I get my lexer & parser generated from my grammar(s).<\/p>\n
Then I can also run:<\/p>\n
# Linux\/Mac\r\n.\/gradlew idea\r\n \r\n# Windows\r\ngradlew idea<\/pre>\n
And I have an IDEA Project ready to be opened.<\/p>\n
4.2 Java Setup using\u00a0Maven<\/h3>\n
First of all we are going to specify in our POM that we need
antlr4-runtime<\/code> as a dependency. We will also use a Maven plugin to run ANTLR through Maven.<\/p>\nWe can also specify if we ANTLR to generate visitors or listeners. To do that we define a couple of corresponding properties.<\/p>\n
<project xmlns=\"http:\/\/maven.apache.org\/POM\/4.0.0\" xmlns:xsi=\"http:\/\/www.w3.org\/2001\/XMLSchema-instance\"\r\n xsi:schemaLocation=\"http:\/\/maven.apache.org\/POM\/4.0.0 http:\/\/maven.apache.org\/xsd\/maven-4.0.0.xsd\">\r\n <modelVersion>4.0.0<\/modelVersion>\r\n \r\n [..]\r\n \r\n <properties>\r\n <project.build.sourceEncoding>UTF-8<\/project.build.sourceEncoding>\r\n <antlr4.visitor>true<\/antlr4.visitor>\r\n <antlr4.listener>true<\/antlr4.listener>\r\n <\/properties> \r\n \r\n <dependencies>\r\n <dependency>\r\n <groupId>org.antlr<\/groupId>\r\n <artifactId>antlr4-runtime<\/artifactId>\r\n <version>4.6<\/version>\r\n <\/dependency>\r\n [..]\r\n <\/dependencies>\r\n \r\n <build>\r\n <plugins>\r\n [..]\r\n <!-- Plugin to compile the g4 files ahead of the java files\r\n See https:\/\/github.com\/antlr\/antlr4\/blob\/master\/antlr4-maven-plugin\/src\/site\/apt\/examples\/simple.apt.vm\r\n Except that the grammar does not need to contain the package declaration as stated in the documentation (I do not know why)\r\n To use this plugin, type:\r\n mvn antlr4:antlr4\r\n In any case, Maven will invoke this plugin before the Java source is compiled\r\n -->\r\n <plugin>\r\n <groupId>org.antlr<\/groupId>\r\n <artifactId>antlr4-maven-plugin<\/artifactId>\r\n <version>4.6<\/version> \r\n <executions>\r\n <execution>\r\n <goals>\r\n <goal>antlr4<\/goal>\r\n <\/goals> \r\n <\/execution>\r\n <\/executions>\r\n <\/plugin>\r\n [..]\r\n <\/plugins>\r\n <\/build>\r\n<\/project><\/pre>\n
Now you have to put the *.g4 files of your grammar under\u00a0
src\/main\/antlr4\/me\/tomassetti\/examples\/MarkupParser.<\/code><\/p>\nOnce you have written your grammars you just run
mvn package<\/code> and all the magic happens: ANTLR is invoked, it generates the lexer and the parser and those are compiled together with the rest of your code.<\/p>\n\/\/ use mwn to generate the package\r\nmvn package<\/pre>\n
If you have never used Maven you can look at the official ANTLR documentation for the Java target<\/a> or also the Maven website<\/a> to get you started.<\/p>\n
There is a clear advantage in using Java for developing ANTLR grammars: there are plugins for several IDEs and it\u2019s the language that the main developer of the tool actually works on. So they are tools, like the
org.antlr.v4.gui.TestRig<\/code>, that can be easily integrated in you workflow and are useful if you want to easily visualize the AST of an input.<\/p>\n5. C# Setup<\/h2>\n
There is support for .NET Framework and Mono 3.5, but there is no support for .NET core. We are going to use Visual Studio to create our ANTLR project, because there is a nice extension for Visual Studio created by the same author of the C# target, called ANTLR Language Support<\/em>. You can install it\u00a0by going in Tools -> Extensions and Updates. This extension will automatically generate parser, lexer and visitor\/listener when you build your project.<\/p>\n
Furthermore, the extension will allow you to create a new grammar file, using the well known menu to add a new item. Last, but not least, you can setup the options to generate listener\/visitor right in the properties of each grammar file.<\/p>\n
Alternatively, if you prefer to use an editor, you need to use the usual\u00a0Java tool to generate everything. You can do that just by indicating the right language. In this example the grammar is called \u201cSpreadsheet\u201d.<\/p>\n
antlr4 -Dlanguage=CSharp Spreadsheet.g4<\/pre>\n
Notice that the \u2018S\u2019 in CSharp is uppercase.<\/p>\n
You still need the ANTLR4 runtime for your project, and you can install it with the good ol\u2019 nuget<\/strong>.<\/p>\n
Beginner<\/h2>\n
In this section we lay the foundation you need to use ANTLR: what lexer and parsers are, the syntax to define them in a grammar and the strategies you can use to create one. We also see the first examples to show how to use what you have learned.\u00a0 You can come back to this section if you don\u2019t remember how ANTLR works.<\/p>\n
6. Lexers and Parsers<\/h2>\n
Before looking into\u00a0parsers, we need to first\u00a0to look into lexers, also known as tokenizers. They are basically the first stepping stone toward a parser, and of course ANTLR allows you to build them too. A lexer takes the individual characters and transforms them in tokens<\/strong>, the atoms that the parser uses to create the logical structure.<\/p>\n
Imagine this process applied to a natural language such as English. You are reading the single characters, putting them together until they make a word, and then you combine the different words to form a sentence.<\/p>\n
Let\u2019s look at the following example and imagine that we are trying to parse a mathematical operation.<\/p>\n
437 + 734<\/pre>\n
The lexer scans the text and find \u20184\u2019, \u20183\u2019, \u20187\u2019 and then the space \u2018 \u2018. So it knows that the first characters actually represent a number. Then it finds a \u2018+\u2019 symbol, so it knows that it represents an operator, and lastly it finds another number.<\/p>\n
- add the tool to your
- Conclusions<\/a><\/li>\n<\/ol>\n
- The Main App.java<\/a><\/li>\n
- Antlr.js<\/a><\/li>\n
- Creating a Grammar<\/a><\/li>\n
- Javascript Setup<\/a><\/li>\n
- the examples will be in different languages, but the knowledge would be generally applicable to any language<\/li>\n<\/ul>\n
- in the companion repository of this tutorial<\/a> you are going to find all the code with testing, even where we don\u2019t see it in the article<\/li>\n