Serializing to S-Expression

[ericvergnaud]

Hi @antlr/antlr5 ,

serialization is an important topic which impacts many aspects of antlr5, both internally and externally:

• we need the tool to communicate with language generator add-ons using strings (such that add-ons can be developed in any language)
• we need the generate parser wrapper (in the target language) to communicate with the generated parser (in WebAssembly) and that communication can only rely on strings (which are not even standardized yet in wasm!!!)
• we want external tools to be able to consume antlr grammars and parse trees. These tools could be developed in any language, so the content would benefit from being language-agnostic strings

This raises the question of the serialization format(s). There are many to choose from, but one I bumped into recently is S-Expression (see https://en.wikipedia.org/wiki/S-expression) which happens to be the serialization format for WebAssembly.

There could be a benefit in using S-Expression for the parse tree, and would be worth digging into for serializing the grammar (might require specifying an @start rule, and could generate lots of duplicates...).

It would be great if we could have just one serialization format end to end...

[kaby76]

I would recommend either XML or JSON. These are well-adopted exchange formats, with fast readers and writers.

In addition, I would recommend understanding the use cases for what you want to inport and export.

In the use-case of displaying a indented text representation of a parse tree, you will want to display the rule names, not integers. If you use rule names instead of rule numbers in the parse tree serialization itself, it will slow the serialization down because you encode the name of the parse rule more than once.

In the use-case of "grepping" parse tree nodes, you will need information on line and column numbers (or index), and the name of the original source file. In Trash, one can also "cat" input text, in which case, there is no file name--it's just "stdin".

In general, I found for Trash that a parse tree is insufficient for tools that operate on parse trees. There's a lot need beyond the parse tree: the grammar, information produced by the Antlr tool, the input string (and file name, if not stdin).

[KvanTTT]

In the use-case of displaying a indented text representation of a parse tree, you will want to display the rule names, not integers.

For dispalying a tree, the following format is the most preferable in my opinion:

File: SimpleExpressions.kt
  packageHeader
  importList
  topLevelObject
    declaration
      functionDeclaration
        FUN("fun")
        simpleIdentifier
          Identifier("a")
        functionValueParameters
          LPAREN("(")
          functionValueParameter
            parameter
              simpleIdentifier
                Identifier("a")
              COLON(":")
              type
                typeReference
                  userType
                    simpleUserType
                      simpleIdentifier
                        Identifier("foo")
            ASSIGNMENT("=")
            expression
              disjunction
                conjunction
                  equality
                    comparison
                      genericCallLikeComparison
                        infixOperation
                          elvisExpression
                            infixFunctionCall
                              rangeExpression
                                additiveExpression
                                  multiplicativeExpression
                                    asExpression
                                      prefixUnaryExpression
                                        postfixUnaryExpression
                                          primaryExpression
                                            simpleIdentifier
                                              Identifier("Unit")
...

If you use rule names instead of rule numbers in the parse tree serialization itself, it will slow the serialization down because you encode the name of the parse rule more than once.

If performance is high-priority, I recommend binary formats such as protobuf, messagepack or something else.

[KvanTTT]

But I agree with @kaby76: serialization format should be different for tree represantation and data-exchanging.

[ftomassetti]

I would agree that JSON is a reasonable choice. I had in the past concerns about performance but then I experienced what @kaby76 is saying: JSON parsers and writers are ubiquituous and very well optimized. Also, JSON can be easily compressed with gzip, if necessary.

I would feel less inclined to use XML instead. While it may be technically better than JSON, I am afraid that nowadays it is less known and slightly less supported than JSON

[KvanTTT]

I would agree that JSON is a reasonable choice. I had in the past concerns about performance but then I experienced what @kaby76 is saying: JSON parsers and writers are ubiquituous and very well optimized

I have an opposite experience. At previous work we used JSON for parse tree serializing but later we switched to MessagePack because of performance problems with JSON. Binary formats always wins string ones in terms of performance.

Also, JSON can be easily compressed with gzip, if necessary.

Binary format is already compressed by its nature. In JSON we use string identifiers for naming some nodes, in binary format we use just integers as identifiers.

[KvanTTT]

we need the generate parser wrapper (in the target language) to communicate with the generated parser (in WebAssembly) and that communication can only rely on strings (which are not even standardized yet in wasm!!!)

A binary format (protobuf, MessagePack) should be used for data-exchanging, otherwise performance slow-down could arise on big trees. I'm not sure if it relies only on string, binary data is very native. It makes sense to reinvensitage what kind of communication is meant.

Also, ANTLR uses binary format for internal ATN representation. I don't see a reason why text format should be used for other internal communications.

[ftomassetti]

For "internal" communication (tool to generators, wrappers to runtime), S-expression seems a reasonable choice, as well as JSON (I will comment under @kaby76's post)

For communications for external tools, I would say two things:

1. It would be useful to export not only the parse tree but also the parse tree schema or structure (what would be called a metamodel in the model-driven development world). By that a mean something indicating the name of the grammar and then for each parser rule, the list of properties it can produces, their type and their multiplicity
2. I would like to support also the LionWeb format, as it would allow interoperability with other tools and this format has been designed to support interoperability between language engineering solutions. I could do that as an external plugin and in addition to any other format we may need to implement

[kaby76]

Yes, for some applications the parse tree is sufficient, while others the meta model is also needed, e.g., when I want to display the tree with parser and lexer rule names instead of integers. Sometimes I would need line/column information to help display the source, e.g., "trxgrep //foobar | trcaret". trparse has a switch to say when to add line/column information into the parse tree. It really depends on what you want to do with the tree.

Trash works like Unix command-line programs with pipes to connect different tools together. While a single program may work on only the parse tree, it's usually part of a chained list of commands that have different data requirements. So, I always pass on the meta model and input to the next command in the chain.

Generally, I found parse tree serialization performance to be not a problem, even for very large grammars and input. This surprised me because there were many requests for it (antlr/antlr4#1006 antlr/antlr4#233) but was pushed back (antlr/antlr4#233 (comment)), then added years later (antlr/antlr4#3773). Yes, trees can be modified, but you only need to add something to indicate that it has been modified so it may no longer follow the meta-model.

[KvanTTT]

Generally, I found parse tree serialization performance to be not a problem, even for very large grammars and input. This surprised me because there were many requests for it (antlr/antlr4#1006 antlr/antlr4#233) but was pushed back (antlr/antlr4#233 (comment)), then added years later (antlr/antlr4#3773).

I disagree, it can be a problem and I've encountered performance problems with JSON for large trees at my previous work. Number of mentioned issues only confirms that this is so.

Also, ANTLR uses kind of binary format for internal ATN represenation. If it was JSON, the serialized string would be much more bigger and slower.

[kaby76]

I have an opposite experience. At previous work we used JSON for parse tree serializing but later we switched to MessagePack because of performance problems with JSON. Binary formats always wins string ones in terms of performance.

I haven't a problem with MessagePack. It seems to be supported in a lot of different languages. In any case, it's best not to reinvent the wheel.

Usually, I am trying to analyze a parse with trtree and trxgrep. This analysis could take several iterations because I don't know what I am looking for and it's easy to make mistakes in the XPath expression. Originally, all the Trash tools like trtree and trxgrep re-parsed from scratch. For really slow grammars like html, redoing the parse was several orders of magnitude slower than JSON serialization. Just about any serialization would be faster than reparsing input for the html grammar.

[KvanTTT]

Actually, as we use Kotlin I suggest using kotlinx.serialization because it provides the following benefits:

• Support of both text (JSON) and binary serialization (Protobuf)
• Support multiplatform: JVM, JS, Native

[ericvergnaud]

How about using Avro ?
On top of being available as both JSON (for debugging) and binary (for performance), and supported by all mainstream languages, it has the benefits of being self described (which makes it very safe to use with 3rd party add-ons and components following a different SDLC).