9 ms·

ANTLR Mega Tutorial

253 points by ftomassetti 10y ago

raverbashing 10y ago
Just a note on "Why not to use regular expression". Because it's impossible depending on the language complexity REs are level 3 https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy
- ftomassetti 10y ago
  That is also a good reason not to, but unfortunately that escape to most people
- exDM69 10y ago
  Classic regular expressions are level 3 in the Chomsky classification, but most regex implementations have features that aren't a part of "regular languages". The upside is that they are more expressive, but the downside is that it's no longer O(n) to parse a string. Worst case for some regexes can be exponential, never run untrusted regexes on your server unless you use a safe implementation like re2 which was developed for Google Code Search.
  - srssays 10y ago
    ...and if you're generating your lexer (with ragel, flex, etc) then you are using regular expressions.
- farresito 10y ago
  How is it usually done in most high performance compilers, if I may ask?
  - nv-vn 10y ago
    Parsed by hand
    - posterboy 10y ago
      That strikes me as odd, but who am I to argue with the wisdom of the crowd. http://stackoverflow.com/questions/6319086/are-gcc-and-clang-parsers-really-handwritten http://stackoverflow.com/questions/6319086/are-gcc-and-clang... (short answer, yes)
  - lallysingh 10y ago
    C++ is a context sensitive language, so (at least some) hand parsing is necessary.
    - munificent 10y ago
      You can use a generated parser for C/C++, I believe. You just need to insert a little shim between the lexer and parser to look up identifiers in the symbol table and mark which name tokens refer to types versus functions or variables.
      - joshuata 10y ago
        You are (essentially) correct. The language itself is context-free, and therefore parse-able as a regular language. Looking up identifiers in symbol tables is part of the type checking phase of compilation. This is a pretty common misconception, that type constraints effect the parsing complexity of a language. Language type only relates to the process of building an abstract syntax tree from an input, not validating it.
        munificent 10y ago
        > therefore parse-able as a regular language. You mean "context-free" not "regular" here, but either way, I believe that C is actually context-sensitive: (a)(b); Is this: 1. Evaluating "b" and casting it to type "a"? 2. Evaluating the parenthesized expression "a" which yields a function, and then calling it, passing in "b"? The only way to distinguish the two is by knowing whether "a" is a type or not. You could argue that as long as the parser produces a suitably vague AST, it doesn't need to know the distinction and can pass it on to later phases. I think that might work because I don't know of cases where the syntax actually diverges based on the type of a symbol. But in practice, I think most parsers want to produce a more precise AST that distinguishes cast expressions from function calls.
        joshuata 10y ago
        You are right, the regular/context-free comment was a typo. You are also correct about c being non-context-free[0]. I have just seen many explanations of language hierarchy online mistaking type-checking for language complexity that it is a pet peeve of mine. [0] http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...
- base698 10y ago
  I always thought a hilarious interview question was, "what's regular about a regular expression?" Similar to, "What's Cascading about Cascading Style Sheets?"
  - betenoire 10y ago
    I know the answers to those questions... but don't get the joke... What's the joke?
    - kmill 10y ago
      What is your answer to the first question? In Kleene's original paper (which I've only skimmed), he is interested in "events" for nerve computation models, and defines "regular events" to be some minimal set of events which is closed under concatenation, alternation, and star. He admits "regular" should be replaced by a better word --- this never happened. http://cs.stackexchange.com/questions/1771/why-is-a-regular-language-called-regular http://cs.stackexchange.com/questions/1771/why-is-a-regular-... If I were to make up history, I would say "oh, regular refers to finite state machines, so a regular language is a language recognizable by a finite state machine," but it appears my made-up history does not exactly match reality. This is not too far off, though, since in the paper he shows that regular events are exactly the kinds of events his nerve networks recognize, and there appears to be something about finite automata in the last section. They could have been called "rational languages" instead, because of a connection with rational functions. In fact, there are manipulations of rational series in Kleene's paper to prove some things about the languages. (I don't get the joke myself --- unless the joke is that you can't take the "regular" out of "regular language.")
      - betenoire 10y ago
        I share your understanding, and yeah, the joke is probably that the word "regular" sounds "easy" or "normal" (shit another loaded term). I was just curious if I was missing more
CalChris 10y ago
I switched over to ANTLR 4. It is strictly superior to ANTLR 3. The listener approach rather than embedding code in the grammar is very natural. Separating leads to clean grammars and clean action code. Odd thing is that I was stuck on 3 because 4 didn't support C yet and then I just switched to the Java target in an anti-C pique. Shoulda done that awhile ago. TParr's The Definitive ANTLR 4 Reference is quite good. And so's this mega tutorial. https://pragprog.com/book/tpantlr2/the-definitive-antlr-4-reference https://pragprog.com/book/tpantlr2/the-definitive-antlr-4-re... ANTLR is my goto tool for DSLs.
- n00b101 10y ago
  ANTLR4 has a C++ target now (finally)
- ftomassetti 10y ago
  agreed! ANTLR 4 is so much better: writing rules with left recursion is much easier
pjmlp 10y ago
Great tutorial, ANTLR is one of the best tools for prototyping languages and compilers. I wasn't aware it supports JavaScript nowadays. In any case, good selection of languages.
- ftomassetti 10y ago
  Thanks! Yes, it is a big pro the fact it supports so many languages, until you need to write semantic predicates at least
jasode 10y ago
I last played around with ANTLR in 2012 (when it was version 3) and I discovered that there's a "bigger picture" to the parser generator universe that most tutorials don't talk about: 1) ANTLR is a good tool for generating "happy path" parsers. With a grammar specification, it easily generates a parser that accepts or rejects a piece of source code. However, it's not easy to use the hooks to generate high quality diagnostic error messages. 2) ANTLR was not good for speculative parsing or probabilistic parsing which would be the basis of today's generation of tools such as "Intellisense" not giving up on parsing when there's an unclosed brace or missing variable declaration. The common theme to the 2 bullet points above is that a high quality compiler written by hand will hold multiple "states" of information and an ANTLR grammar file doesn't really have an obvious way to express that knowledge. A pathological example would be the numerous "broken HTML" pages being successfully parsed by browsers. It would be very hard to replicate how Chrome/Firefox/Safari/IE doesn't choke on broken HTML by using ANTLR to generate an HTML parser. In short, ANTLR is great for prototyping a parser but any industrial-grade parser released into the wild with programmers' expectations of helpful error messages would require a hand-written parser. Lastly, the lexing (creating the tokens) and parsing (creating the AST) is a very tiny percentage of the total development of a quality compiler. Therefore, ANTLR doesn't save as much time as one might think. I welcome any comments about v4 that makes those findings obsolete.
- reacweb 10y ago
  I think most of the creators of quality compilers have written huge numbers of toys (or experimental) compilers before.
- pjmlp 10y ago
  Even so, ANTLR is a great productivity improvement (as other similar compiler generator tools), over those stuck on yacc/lex days. Also many languages don't survive the prototyping phase into some kind of product, so why bother with premature optimizations?
  - 01928301 10y ago
    I've asked this before, and I'll ask it again: How is ANTLR an improvement over menhir/ocamllex? LR has fewer constraints than LL(n), menhir's documentation is better and splitting lexing/parsing IMO adds clarity.
destructaball 10y ago
What are the advantages of ANTLR over something like Haskells Parsec? https://github.com/aslatter/parsec https://github.com/aslatter/parsec
- pjmlp 10y ago
  Graphical tooling, including grammar debuggers and tree walkers and support for more compiler phases as just parsing.
- danidiaz 10y ago
  Speaking of "parsec", "megaparsec" is a modern fork with a few more bells and whistles: http://hackage.haskell.org/package/megaparsec http://hackage.haskell.org/package/megaparsec
intrasight 10y ago
For .Net projects, I've used Irony. From the CodePlex site: "Unlike most existing yacc/lex-style solutions Irony does not employ any scanner or parser code generation from grammar specifications written in a specialized meta-language. In Irony the target language grammar is coded directly in c# using operator overloading to express grammar constructs. "
- corndoge 10y ago
  BNF (even with bison extensions) is hardly a specialized meta-language.
- Matthias247 10y ago
  I used Irony in a very succesful project too. It worked beautifully and got it's job done. The downside is that there is less documentation available then for Antlr.
ttd 10y ago
I think everyone should manually implement a simple recursive descent parser at least once in their careers. It's surprisingly easy, and really (in my experience) helps to break through the mental barrier of parsers being magical black boxes. Plus, once you have an understanding of recursive descent parsing, it's a relatively small leap to recursive descent code generation. And once you're there, you have a pretty good high-level understanding of the entire compilation pipeline (minus optimization). Then all of a sudden, compilers are a whole lot less impenetrable.
- Terr_ 10y ago
  On that note, Parr also has a nice little book called "Language Implementation Patterns" [0] which introduces things on a level of "this kind of language motif maps to this kind of parsing code". [0] https://pragprog.com/book/tpdsl/language-implementation-patterns https://pragprog.com/book/tpdsl/language-implementation-patt...
  - parrt 10y ago
    Thanks for the ptr. :) I just wish I had time to rewrite that book in ANTLR 4 (it's in ANTLR 3).
    - ftomassetti 10y ago
      I also loved that book! It is in my list of best books on building DSLs (https://tomassetti.me/domain-specific-languages#books https://tomassetti.me/domain-specific-languages#books)
poppingtonic 10y ago
I used ANTLR to write a Python parser for the SNOMED expression language last year, and testing it was one of the weirder parts of the experience. I was up and running in a few days, which was largely thanks to the ANTLR book. I love this project. It made doing what I did a lot more fun than I thought it would be. Hand-rolling an ABNF parser from scratch would be a nice hobby project, but not when one has a deadline.
betenoire 10y ago
These types of tutorials always start out explaining the problems with Regular Expressions and why not to use them... then immediately proceeding into lexing via regular expressions. Perhaps the tutorials should start with the strengths of regular expressions, and how we can harness that for getting started with a lexer.
closed 10y ago
This tutorial looks great. I picked up Antlr4 a few months ago, and hadn't done any parsing before then. The first week was basically me, The Definitive Antlr4 Reference, and extreme confusion with how different targets worked. Compounding the problem was the fact that a lot of the antlr4 example grammars only work for a specific target. The use of different language implementations as part of this tutorial seems really useful! (Antlr4 is awesome :)
nradov 10y ago
I used ANTLR to write a fuzz testing tool which parses an ABNF grammar (like in an IETF RFC) and then generates random output which matches the grammar. Worked great! https://github.com/nradov/abnffuzzer https://github.com/nradov/abnffuzzer
- parrt 10y ago
  Heh, that's cool. I tried to do a random phrase generator at one point but it's hard!
  - nradov 10y ago
    If you're referring to human language phrases, I understand that Markov Chains are the usual approach.
musesum 10y ago
I used Antlr v3 to create a NLP parser for calendar events for iOS and Android. It took longer than expected. iOS + C runtime was opaque, so had to write a tool for debugging. Android + Java runtime overran memory, so had to break into separate grammars. Of course, NLP is not a natural fit. Don't know what problems are fixed by v4. > The most obvious is the lack of recursion: you can’t find a (regular) expression inside another one ... PCRE has some recursion. Here is an example for parsing anything between { }, with counting of inner brackets: '(?>\{(?:[^{}]|(?R))\})|\w+' A C++11 constexpr can make hand coded parsers a lot more readible, allowing token names in case statements. For example , search on "str2int" in the following island parser: https://github.com/musesum/par https://github.com/musesum/par

253 points by ftomassetti 10y ago

Just a note on "Why not to use regular expression". Because it's impossible depending on the language complexity REs are level 3 https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy

ftomassetti 10y ago
That is also a good reason not to, but unfortunately that escape to most people
exDM69 10y ago
Classic regular expressions are level 3 in the Chomsky classification, but most regex implementations have features that aren't a part of "regular languages". The upside is that they are more expressive, but the downside is that it's no longer O(n) to parse a string. Worst case for some regexes can be exponential, never run untrusted regexes on your server unless you use a safe implementation like re2 which was developed for Google Code Search.
- srssays 10y ago
  ...and if you're generating your lexer (with ragel, flex, etc) then you are using regular expressions.
farresito 10y ago
How is it usually done in most high performance compilers, if I may ask?
- nv-vn 10y ago
  Parsed by hand
  - posterboy 10y ago
    That strikes me as odd, but who am I to argue with the wisdom of the crowd. http://stackoverflow.com/questions/6319086/are-gcc-and-clang-parsers-really-handwritten http://stackoverflow.com/questions/6319086/are-gcc-and-clang... (short answer, yes)
- lallysingh 10y ago
  C++ is a context sensitive language, so (at least some) hand parsing is necessary.
  - munificent 10y ago
    You can use a generated parser for C/C++, I believe. You just need to insert a little shim between the lexer and parser to look up identifiers in the symbol table and mark which name tokens refer to types versus functions or variables.
    - joshuata 10y ago
      You are (essentially) correct. The language itself is context-free, and therefore parse-able as a regular language. Looking up identifiers in symbol tables is part of the type checking phase of compilation. This is a pretty common misconception, that type constraints effect the parsing complexity of a language. Language type only relates to the process of building an abstract syntax tree from an input, not validating it.
      - munificent 10y ago
        > therefore parse-able as a regular language. You mean "context-free" not "regular" here, but either way, I believe that C is actually context-sensitive: (a)(b); Is this: 1. Evaluating "b" and casting it to type "a"? 2. Evaluating the parenthesized expression "a" which yields a function, and then calling it, passing in "b"? The only way to distinguish the two is by knowing whether "a" is a type or not. You could argue that as long as the parser produces a suitably vague AST, it doesn't need to know the distinction and can pass it on to later phases. I think that might work because I don't know of cases where the syntax actually diverges based on the type of a symbol. But in practice, I think most parsers want to produce a more precise AST that distinguishes cast expressions from function calls.
        joshuata 10y ago
        You are right, the regular/context-free comment was a typo. You are also correct about c being non-context-free[0]. I have just seen many explanations of language hierarchy online mistaking type-checking for language complexity that it is a pet peeve of mine. [0] http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...
base698 10y ago
I always thought a hilarious interview question was, "what's regular about a regular expression?" Similar to, "What's Cascading about Cascading Style Sheets?"
- betenoire 10y ago
  I know the answers to those questions... but don't get the joke... What's the joke?
  - kmill 10y ago
    What is your answer to the first question? In Kleene's original paper (which I've only skimmed), he is interested in "events" for nerve computation models, and defines "regular events" to be some minimal set of events which is closed under concatenation, alternation, and star. He admits "regular" should be replaced by a better word --- this never happened. http://cs.stackexchange.com/questions/1771/why-is-a-regular-language-called-regular http://cs.stackexchange.com/questions/1771/why-is-a-regular-... If I were to make up history, I would say "oh, regular refers to finite state machines, so a regular language is a language recognizable by a finite state machine," but it appears my made-up history does not exactly match reality. This is not too far off, though, since in the paper he shows that regular events are exactly the kinds of events his nerve networks recognize, and there appears to be something about finite automata in the last section. They could have been called "rational languages" instead, because of a connection with rational functions. In fact, there are manipulations of rational series in Kleene's paper to prove some things about the languages. (I don't get the joke myself --- unless the joke is that you can't take the "regular" out of "regular language.")
    - betenoire 10y ago
      I share your understanding, and yeah, the joke is probably that the word "regular" sounds "easy" or "normal" (shit another loaded term). I was just curious if I was missing more

CalChris 10y ago

I switched over to ANTLR 4. It is strictly superior to ANTLR 3. The listener approach rather than embedding code in the grammar is very natural. Separating leads to clean grammars and clean action code. Odd thing is that I was stuck on 3 because 4 didn't support C yet and then I just switched to the Java target in an anti-C pique. Shoulda done that awhile ago. TParr's The Definitive ANTLR 4 Reference is quite good. And so's this mega tutorial. https://pragprog.com/book/tpantlr2/the-definitive-antlr-4-reference https://pragprog.com/book/tpantlr2/the-definitive-antlr-4-re... ANTLR is my goto tool for DSLs.

n00b101 10y ago
ANTLR4 has a C++ target now (finally)
ftomassetti 10y ago
agreed! ANTLR 4 is so much better: writing rules with left recursion is much easier

pjmlp 10y ago

Great tutorial, ANTLR is one of the best tools for prototyping languages and compilers. I wasn't aware it supports JavaScript nowadays. In any case, good selection of languages.

ftomassetti 10y ago
Thanks! Yes, it is a big pro the fact it supports so many languages, until you need to write semantic predicates at least

jasode 10y ago

I last played around with ANTLR in 2012 (when it was version 3) and I discovered that there's a "bigger picture" to the parser generator universe that most tutorials don't talk about: 1) ANTLR is a good tool for generating "happy path" parsers. With a grammar specification, it easily generates a parser that accepts or rejects a piece of source code. However, it's not easy to use the hooks to generate high quality diagnostic error messages. 2) ANTLR was not good for speculative parsing or probabilistic parsing which would be the basis of today's generation of tools such as "Intellisense" not giving up on parsing when there's an unclosed brace or missing variable declaration. The common theme to the 2 bullet points above is that a high quality compiler written by hand will hold multiple "states" of information and an ANTLR grammar file doesn't really have an obvious way to express that knowledge. A pathological example would be the numerous "broken HTML" pages being successfully parsed by browsers. It would be very hard to replicate how Chrome/Firefox/Safari/IE doesn't choke on broken HTML by using ANTLR to generate an HTML parser. In short, ANTLR is great for prototyping a parser but any industrial-grade parser released into the wild with programmers' expectations of helpful error messages would require a hand-written parser. Lastly, the lexing (creating the tokens) and parsing (creating the AST) is a very tiny percentage of the total development of a quality compiler. Therefore, ANTLR doesn't save as much time as one might think. I welcome any comments about v4 that makes those findings obsolete.

reacweb 10y ago
I think most of the creators of quality compilers have written huge numbers of toys (or experimental) compilers before.
pjmlp 10y ago
Even so, ANTLR is a great productivity improvement (as other similar compiler generator tools), over those stuck on yacc/lex days. Also many languages don't survive the prototyping phase into some kind of product, so why bother with premature optimizations?
- 01928301 10y ago
  I've asked this before, and I'll ask it again: How is ANTLR an improvement over menhir/ocamllex? LR has fewer constraints than LL(n), menhir's documentation is better and splitting lexing/parsing IMO adds clarity.

destructaball 10y ago

What are the advantages of ANTLR over something like Haskells Parsec? https://github.com/aslatter/parsec https://github.com/aslatter/parsec

pjmlp 10y ago
Graphical tooling, including grammar debuggers and tree walkers and support for more compiler phases as just parsing.
danidiaz 10y ago
Speaking of "parsec", "megaparsec" is a modern fork with a few more bells and whistles: http://hackage.haskell.org/package/megaparsec http://hackage.haskell.org/package/megaparsec

intrasight 10y ago

For .Net projects, I've used Irony. From the CodePlex site: "Unlike most existing yacc/lex-style solutions Irony does not employ any scanner or parser code generation from grammar specifications written in a specialized meta-language. In Irony the target language grammar is coded directly in c# using operator overloading to express grammar constructs. "

corndoge 10y ago
BNF (even with bison extensions) is hardly a specialized meta-language.
Matthias247 10y ago
I used Irony in a very succesful project too. It worked beautifully and got it's job done. The downside is that there is less documentation available then for Antlr.

ttd 10y ago

I think everyone should manually implement a simple recursive descent parser at least once in their careers. It's surprisingly easy, and really (in my experience) helps to break through the mental barrier of parsers being magical black boxes. Plus, once you have an understanding of recursive descent parsing, it's a relatively small leap to recursive descent code generation. And once you're there, you have a pretty good high-level understanding of the entire compilation pipeline (minus optimization). Then all of a sudden, compilers are a whole lot less impenetrable.

Terr_ 10y ago
On that note, Parr also has a nice little book called "Language Implementation Patterns" [0] which introduces things on a level of "this kind of language motif maps to this kind of parsing code". [0] https://pragprog.com/book/tpdsl/language-implementation-patterns https://pragprog.com/book/tpdsl/language-implementation-patt...
- parrt 10y ago
  Thanks for the ptr. :) I just wish I had time to rewrite that book in ANTLR 4 (it's in ANTLR 3).
  - ftomassetti 10y ago
    I also loved that book! It is in my list of best books on building DSLs (https://tomassetti.me/domain-specific-languages#books https://tomassetti.me/domain-specific-languages#books)

poppingtonic 10y ago

I used ANTLR to write a Python parser for the SNOMED expression language last year, and testing it was one of the weirder parts of the experience. I was up and running in a few days, which was largely thanks to the ANTLR book. I love this project. It made doing what I did a lot more fun than I thought it would be. Hand-rolling an ABNF parser from scratch would be a nice hobby project, but not when one has a deadline.

betenoire 10y ago

These types of tutorials always start out explaining the problems with Regular Expressions and why not to use them... then immediately proceeding into lexing via regular expressions. Perhaps the tutorials should start with the strengths of regular expressions, and how we can harness that for getting started with a lexer.

closed 10y ago

This tutorial looks great. I picked up Antlr4 a few months ago, and hadn't done any parsing before then. The first week was basically me, The Definitive Antlr4 Reference, and extreme confusion with how different targets worked. Compounding the problem was the fact that a lot of the antlr4 example grammars only work for a specific target. The use of different language implementations as part of this tutorial seems really useful! (Antlr4 is awesome :)

nradov 10y ago

I used ANTLR to write a fuzz testing tool which parses an ABNF grammar (like in an IETF RFC) and then generates random output which matches the grammar. Worked great! https://github.com/nradov/abnffuzzer https://github.com/nradov/abnffuzzer

parrt 10y ago
Heh, that's cool. I tried to do a random phrase generator at one point but it's hard!
- nradov 10y ago
  If you're referring to human language phrases, I understand that Markov Chains are the usual approach.

musesum 10y ago

I used Antlr v3 to create a NLP parser for calendar events for iOS and Android. It took longer than expected. iOS + C runtime was opaque, so had to write a tool for debugging. Android + Java runtime overran memory, so had to break into separate grammars. Of course, NLP is not a natural fit. Don't know what problems are fixed by v4. > The most obvious is the lack of recursion: you can’t find a (regular) expression inside another one ... PCRE has some recursion. Here is an example for parsing anything between { }, with counting of inner brackets: '(?>\{(?:[^{}]|(?R))\})|\w+' A C++11 constexpr can make hand coded parsers a lot more readible, allowing token names in case statements. For example , search on "str2int" in the following island parser: https://github.com/musesum/par https://github.com/musesum/par