Mucking with ANTLR

revusky

As a consequence of the discussion initiated by ngx about converting a large ANTLR grammar to CongoCC, I started looking at the ANTLR grammar (for SQL) he pointed to and I started thinking about writing (maybe) a converter -- not specifically for the SQL grammar, but for ANTLR4 grammars generally, of course.

Well, I haven't written an ANTLR->Congo converter yet, but I have done the first step, which is to write a CongoCC grammar for ANTLR grammar files. See here. The parser that this generates can parse all the files in the ANTLR grammar repository.

It is actually striking how modest a project this turned out to be. The resulting grammar is a bit over 500 lines. That compares to the CongoCC grammar which is more like 1600 lines, and that is not including the fact that it INCLUDEs the Java grammar which is as big again.

If you count the embedded Java grammar, the CongoCC grammar is something like 3000 lines, but note, of course, that the ANTLR grammar/parser has no knowledge of Java or any of the other target languages. The way that it deals with an embedded code action is simply to handle it lexically, all the characters inside the {...} delimiters. So, basically, it just matches delimiters, which is a rather crude approach. The tree that CongoCC builds from a .ccc grammar file actually contains the sub-trees for all the Java code actions and injections. And, aside from that, the CongoCC grammar files are just syntactically richer, what with lookahead/up-to-here and assertions and so on.

I wrote the CongoCC grammar for ANTLR using this one as a starting point. Well, again, the problem of parsing the .g4 files is solved. Soon, I'll get into the problem of outputting the resulting tree in a .ccc format. I don't know how well I can get it to work, due to the different sematics. Also, unlike ANTLR, CongoCC does not support left recursion. Though, that said, it is a well-known problem. I may figure out how to transform the productions that use left recursion and output them in CongoCC format without the left recursion. (No promises though!)

All that said, even a crude converter tool could probably save a lot of time for people in the position of the aforementioned ngx. And, anyway, I thought to announce this here because maybe somebody is interested. After all, there are a lot of existing ANTLR grammars, so the ability to parse them and build and manipulate the AST using a CongoCC tree traversal sort of API could already be useful.

Of course, generally speaking, nobody will know about something like this unless I tell them about it, so...

adMartem

A horse of a similar color...

Well, I accidentally found myself in ANTLR-world myself! You might have seem my sandbox commit adding a "peg" folder. It started out with my looking for a language that had a simple syntax, but was meaningful enough to allow me to experiment with fault-tolerant behavior and be able to try it with a variety of test cases that weren't all done by me. I decided that Ford's PEG grammar would be a good candidate since it was extremely small, yet provably powerful, and had a syntax that intuitively seemed like fault tolerance could be leveraged.
And so I wrote a PEG parser in CongoCC. I quickly realized that the PEG AST could be easily visited to produce a CongoCC equivalent parser by using up-to-here on every choice (not great performance potential, but so what). Of course when I did this, my test case was to generate a PEG parser in CongoCC from Ford's original PEG grammar, so the booting had begun. Upon achieving that goal, I had learned enough about PEG to realize I needed a more powerful version it to make life easier...
So, I added up-to-here (which I named entailment, since I was in math-world by that time) to allow limiting lookahead where desirable and more normal notation, since I was making mistakes remembering to type the now-archaic notation that Ford used. Then I went looking for test cases. Guess what I found. Essentially everyone that worked from the original Ford paper invented modifications and extensions to his grammar (including Ford), so there didn't seem to be any that were really compatible with the original. But I did find that ANTLR4 was darn close.

Now, as you know all-to-well, I'm sure, ANTLR might look like PEG, but it is not at all PEG semantically. In particular the predictive(?) parser it generates is more like a Packrat parser driven by an NFA. I remembered all the problems I had with ANTLR years ago, and finally understood why. I had "assumed" the grammar would work like a PEG grammar (although I had no knowledge of PEG at that time) and process the rule's choices left to right, rather than as a real CFG would. Boy was I misguided. But, for my current purpose as a test case source, ANTLR was a cornucopia of possibilities. Hence I chose CPP14.g4 as an experiment.

As it turned out, I didn't have to do much to it, and it was suddenly a grammatically correct (extended) PEG grammar of 2K+ lines. Unfortunately, the CongoCC it generates doesn't parse even the smallest C++ source correctly (I assume because the order of one or more choices in PEG does not result in the longest match, or because I messed up one of the 20 or so left recursions I had to refactor). I added the fragment keyword to what I now call PEG-alt, along with some minor scan-and-pitch things like ; so my next choice (the 200 line calculator grammar) was very quick to modify (remove the -> skips and comment the initial grammar declaration).

Which is where I am now with that little detour.

revusky

adMartem

I had "assumed" the grammar would work like a PEG grammar (although I had no knowledge of PEG at that time) and process the rule's choices left to right, rather than as a real CFG would. Boy was I misguided.

Yeah, well, the thing is that surely this is just how anybody would intuit the question. You have a series of options, possible branches, and you go through them in order and the first one that matches, you go with that one...

But, you know, generally speaking, all of this parsing theory pretty much has me perplexed, drives me nuts. I suppose you know the old quip, that modern abstract art is some massive conspiracy to convince ordinary people that they're stupid. So, I was wondering the same thing about some of this parsing theory. The context-free grammar (CFG) concept, that all of the branches in a choice have equal priority... As an implementer, how does that even work? It just seems pretty obvious to me that the earlier choices would have priority, no? I mean, the procedural programming that we all cut our teeth on tends to be like:

              if (conditionA) {do A}
              else if (conditionB) {do B}
              ....
              else {We have a problem, Houston...}

So you go through and you try the choices in order. And once you match a given condition and go into the corresponding block, you don't try to match any of the later ones! If conditionA matches, then you do A, and you don't even check conditionB or any of the later ones. To be saying that you check all the conditions and if more than one is true, you have a... drumroll... ambiguity... The original JavaCC had this really horrendous code in there to check for these "ambiguities", except to my mind, they are not ambiguities. They're just dead code. So if you write:

          Expression ("," Expression)* [","]

then using 1-token lookahead logic (which is what you have if you don't specify anything else) then the optional comma at the end will never be hit. You probably noticed that I put back the warnings for these things half a year ago or so, but the warning message does not say that there is any "ambiguity". It just says that the second comma is unreachable, which means you should have look at what you're doing there! But all this talk of "ambiguity"...

So, kudos to Bryan Ford for deciding that the earlier specified branch has priority. I was looking at this again just today and I see (I saw it before, I think) that Ford was experimenting with "memoization" to speed up the parsing. So he'd cache results of certain paths through the input, I guess. Actually, if you go through a CongoCC parser step by a step in a debugger, you do see that it's frequently scanning over the same sequence of tokens again and again. So one could wonder whether memoization could speed things up significantly. I thought about it somewhat, but I have my doubts by how much. Unless you're switching between lexical states during the lookahead (which is not the most typical case) all the tokens are cached, so you're just scanning a number of them and checking the tokenType and I think it's really pretty fast. After all, you type ant test and it builds the various parsers -- Java, Python, C# -- and in each case, parses through some thousands of files. I honestly doubt that many people have a practical need to parse code any faster than that! I dunno for sure. It's not like people show up and say they want to use this but it's too slow. But not many people show up and say anything at all, so...

But I just don't relate to all that blather about "ambiguity". Of course, natural language is full of ambiguity highly dependent on context. But you'd think that a parsing system like CongoCC just wouldn't have any ambiguity really. If you can build the parser code, it compiles and runs, then its behavior is pretty determinate. Even left recursion. There was a check for that in legacy JavaCC, but I just pulled it out at some point, because, like with the other "ambiguity" checks, the code was just horrible and I figured it would be easier to just write it from scratch at a later point. So I did it redo it and now it warns you about left recursion and exits, but before that, it would run, and you'd get a stack overflow... but that does not strike me as an ambiguous result. It looks pretty determinate to me!

Well, I could rant more about all this. Oh, here is one thing that I resolved (to my satisfaction anyway) some time ago, which is, you know, when you have two regexp specs that will match the input. Well, you know, the longest match wins, of course. But if they match the same length of input, then it is the earlier specified regexp that wins out. (Strangely, nobody says that is an ambiguity!) So, you can have a problem if you specify a literal word after the definition of an identifier so you have:

                <ID : (["a"-"z", "A"-"Z"])+>
                |
                <FOO : "foo" >

Of course, FOO will never be matched because if there is a foo, it will always be matched by the ID regexp, and since that is the earlier specified one... So, actually, the original JavaCC had some (again, totally obfuscated) code to check for these things and warn you. So, I removed that and, as in the other cases, left the user on his own. But then (as in the other cases) I just finally decided that if somebody specified a literal string and also a regexp that matches that literal string, they always will want the literal string to take priority. So I quietly changed things so it works that way. Basically, I just sort them so that the literal strings always occur earlier, or it's as if they did -- even if, in the file, they don't. I just couldn't conceive of when one would specify a literal string as a pattern and not want that to have priority over something more general.

But regardless of that, in a well specified system, how can you really have ambiguity? It surely just means that you haven't specified things precisely enough, no? Oh, and by the way, I just reread this somewhat sarcastic blog article that I wrote nearly 5 years ago, and really, I don't think my opinion has changed particularly. Well, I did put back in the warnings about the dead code, -- well, really just the ones that it is easy to warn about, where we're operating with single-token lookahed and no other conditions (like lookahead predicates expressed in Java code) that could complicate matters.

EOR (End of Rant)

adMartem

revusky
My sense is that "ambiguity" regarding parsers is pretty widely misused. As I recall the use of the term by the linguists that invented all this formalization referred to its generative meaning. I.e., a grammar is ambiguous iff it can generate the same resulting sentence via two or more distinct sequences of rules (more or less, by memory is fuzzy and I'm too lazy to look it up). Now, in computer-land, the word is used in the context of accepting the language and, to me, it seems like the term "redundant" is more meaningful in most cases when dealing with parsing that is not context-free and is top-down with ordered choices (i.e., a PEG-class parser). That is, if there is a way to recognize a distinct element of the language that is not reachable, it is redundant and possibly an error if there is a dependency outside of the grammar on its actions or position in the AST. So I think a warning whenever this case can be determined is a righteous choice.

adMartem

I remember well when you added the warnings. It uncovered about a dozen cases where my grammar needed to be cleaned up a bit, and revealed one case that, to this day, I can't figure out. I have a sticky note to suss it out someday. So your inclination to add that was worthwhile, at least for my peace of mind.

Yes, Ford also published a famous paper on memoized parsing, I think even before the seminal PEG paper. I think he should get kudos for bothering to formalize the obvious, to paraphrase a bit. I just dug it up because it was one of the few parser-related papers that I was able to fathom with only a few bathroom visits. I don't know if you've had a glance at the peg example in the sandbox, but if so, or you later do, you might notice that, after implementing the "pure" PEG" translator to CongoCC, I spliced a few selected CongoCC capabilities into the PEG-alt language that I thought added enough value to make it a usable, grammar language. The first was the up-to-here annotation. Since for PEG it was difficult (and probably misguided) to describe it in CongoCC terms, I was forced to think about it in the context of the PEG expression of the grammar. That was when I had the revelation that it is actually an indication of where in a sequence the choice of that sequence may be considered made. In other words, at what point does the choice entail the preceding matched elements. So I named it entailment and made the annotation >>>. I then went looking for a cool Unicode character that would be good as an alternative (since every academic language needs difficult-to-type symbols) and found the nested greater than ⫸. It actually adds considerable practical power to PEG, in that it allows the grammar writer to replace, for any choice sequence, the PEG requirement to accept the entire sequence with only acceptance up-to the annotation, at which point the choice is assured. Of course the implementation is trivial, only requiring that the generated CongoCC up-to-here on every sequence be suppressed and only the one at the point of the entailment retained.

The other significant improvement was to allow a < token-name > to be allowed as an identifier referring to a lexer token. During the booting process of getting a CongoCC grammar that would parse a true PEG grammar that could itself parse and generate a PEG grammar in CongoCC, the biggest problem was the so-called "feature" of PEG in that it required no Lexer. That was unbelievably difficult for me to conquer, and resulted in the contrivance of using only a single fixed parser token in the generated grammar (<ANY>). The others needed are all generated as single-state token classes that implement the "regular expression" syntax of the PEG grammar.

But I ramble, so I'll stop now.