When to use ANTLR and when to use a parsing library

I’ve always wanted to learn how to write a compiler – I’ve decided to use ANTLR, and am currently reading through the book (its very good by the way)

I’m pretty new to this, so go easy, but the jist seems to be that you write your grammar, transform this into a data structure (usually an AST) and then walk this one or more times actually executing the ‘meat’ of whatever you want your program to do.

If my input “language” was something like JSON or XML, i.e something that probably has a library that can turn it into a graph of pojos – does this negate the need to do the lexing and parsing with a compiler compiler like ANTLR? clearly if my input is very bespoke then I need to write my own lexer/parser – but could I and should I short-cut this if my input language is already broadly used.

Would be fair to say you could parse, say json, with Jackson,into POJO’s and then drive your code of the resulting pojos? – or in this case, does a ‘proper’ compiler compiler offer some advantage?

Edited (based on the answers) to add

I probably should have pointed out that my question was slightly hypothetical – I wouldn’t ever try and build a programming language in XML!

So I guess the deal is that AST != Pojo – and the tree walkers that antlr give you are more useful in the case where you need to ‘walk’ the data structure and execute code.

You could use either to perform either task. The difference is what each is meant for. You can draw pictures or diagrams in Excel if you want to, but you can also draw a picture in something built for that purpose.

JSON and XML libraries are designed around general purpose loading of documents, pulling parts out of them, or transforming their structures into different structures, etc.

ANTLR on the other hand is a tool designed for generating parsers for compilers. It is tailored specifically to suit the needs of that task.

If you use an xml or json parser to parse either of those, you’ll ultimately end up writing a bunch of code that transforms your input into an AST of some sort, for you to process. So, whether you want to write and debug all of that, or use something that gives it to you up front, that’s up to you.

If your input is serialized as XML or JSON, then you should prefer an existing XML or JSON parser. This makes it ultimately more likely that your parser will be correct, and that aids compatibility and interoperability with other systems. Note that XML is not really a language, but a system for defining new languages sharing common syntax. Writing a correct and performant XML or YAML parser is highly non-trivial, and even JSON has a couple of minor pitfalls.

Once the parser returns a datastructure (e.g. the DOM in case of XML), it is fairly simple to translate that to an AST representation that suits your needs – much simpler than writing a parser of your own, since building the AST would be part of the parser anyway.

In my experience, data serialization formats are not very suitable as a primary input format for an interesting language (however, they might be very suitable for AST serialization). While XML and JSON are human-readable, they are difficult to write by hand. For example, JSON doesn’t even have comments and XML has very verbose syntax. While – to a certain degree – syntax is not what ultimately makes or breaks a language, good syntax can often help to clearly convey intent, and a good language will map well to its problem domain in both semantics and syntax.

@Groostav, answering rather than commenting so I can say a bit more.

Interesting post. Since I asked my question, I made a bit more progress, so have a bit more perspective.

I think Id try to initially use something standard like YAML or JSON. Then if you feel you are stretching the boundary of what the config management system can do, only then would I make a DSL.

What does ‘stretching the boundary‘ mean? – well I think it’s things like trying to form programming idioms into things like JSON – e.g if you try and stuff a for loop into a json document, you probably went past the point where it should be a DSL rather than a standard config file solution.

You touch on the second point with your ‘Null checks’ observation. if you do a DSL and a grammar, you can enforce some schema constraints like

node 'shape' should always have a subnode called 'edges'

which alleviates you from some of this burden as the grammar will do this for you – although you may have to do some work to get nice ‘user friendly’ error messages out of it.

Having said that – JSON has schema validators, and I’d bet someone has done one for YAML as well.

TL;DR is that I think its more art than science… for your use case, with the information you provided… I’d stick to YAML.

I’m actually in the process of debating exactly this. My issue is that I want to give our users really pretty YAML documents to edit by-hand and then load back into our software –something akin to what CircleCI does with their circle.yml file.

We’re on the JVM and SnakeYAML is a very nice YAML serializer/deserializer, so I can simply add it to my project and get started, yet that means I have to bridge from our domain’s various model objects to serializer-friendly POJO (‘surrogates’) objects and back again. And that has some fairly disastrous consequences, including 300 or so lines to handle null checks alone (its a lot of null checks, and I’m sure I’ve missed some and will continue to miss them as I add features).

If I go with ANTLR and a make our configuration document not a true YAML document but instead a strict subset of YAML I can bake those null checks into the parser. But now I get a new set of problems: will my grammar properly handle YAML’s references? will I have bugs in my whitespace handling (YAML is a whitespace sensitive document language like the python programming language).

I’m really torn. Right now the winds are favoring the latter since the amount of buggy validation we’re doing is just getting too extensive.

Some questions/thoughts I’ve asked/had myself that have been reasonably helpful:

What specific problems are you going to encounter with using a Serializer?
How complex is your target language? What kind’ve gotchas does it have for your parser (eg preprocesor directives, comments (with semantics?), whitespace handling)
Experience with grammars, parsers and visitors is experience with sophisticated and reusable tools, experience writing null-checks and domainType.x = surrogateType.x is not. Getting to know a serializer intimately can also be helpful, but is generally not transferable out of your current language/tech-stack.
You can get started with both serializers and parser-generators reasonably easily, meaning its not impossible to try both. See how sophisticated your POJO classes can be before your serializer buckles and see what kind of parse tree gets generated by a simple grammar on a subset of the langauge you’re looking at.

Filed under: softwareengineering - @ 17:17

Thẻ: compiler, java, language-design, lexer, parsing

Thiết kế website giá rẻ

Danh mục

When to use ANTLR and when to use a parsing library