3 ms·

Is Owl similar to ANTLR? Could you explain the differences between the two languages, and what makes a parser unique if they're similar? I'm curious because I

Is Owl similar to ANTLR? Could you explain the differences between the two languages, and what makes a parser unique if they're similar? I'm curious because I've quickly run across two of these types of projects now, but admittedly know very little about them.

panic 8y ago
Yeah, they both solve the same problem -- turning text into a structured "parse tree". At the core of each parsing tool is a particular parsing algorithm. The details of this algorithm determine what kind of text the parser can parse, how efficiently it can parse it, and what kind of error messages you get if something goes wrong. There's a huge variety of these algorithms, but nearly all of them are variations on two basic types: "LL" and "LR" parsers. For example, ANTLR uses an "LL(*)" parsing algorithm. This is a great blog post about the difference between the two basic types: http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demyst.... Owl is unique because its algorithm isn't a variation of either of these. It works more like a regular expression parsing algorithm. This makes it more limited than a tool like ANTLR, but it can solve some problems that have been difficult with the existing algorithms. For example, most programming languages allow expressions like "1 - 2" to be used as statements. If you don't use a semicolon or anything to separate the statements, there's an ambiguity -- is "1 - 2" a single expression, or is it the two expressions "1" "-2" in sequence? ANTLR (at least with the default settings I tried) doesn't tell you about this ambiguity at all. It just picks one of the two options ("1 - 2" in this case). This may or may not have been what you were expecting! The problems with ambiguity checking are quite deep (this followup to the earlier blog post I linked goes into more detail: http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why...). Owl's parsing algorithm avoids these problems; it can show you the ambiguity in all cases.
- sbjs 8y ago
  This is really amazing work! I think the only thing it needs now is to have https://ianh.github.io/owl/try/ https://ianh.github.io/owl/try/ wrapped up into an Electron app that can load/save Owl files and generate header files for you right on your filesystem. That would be awesome! Hmm, I think I see a project in my near future (eyes:winking nose:pointy mouth:open-smile)
- adito 8y ago
  It's often I stumble upon discussion mentioning the term LL and LR and other stuff related to parsing[0]. Without a proper CS background, it's quite hard to follow along. That first link[1] and the wikipedia page[2] mentioned there are really great. Many thanks for posting those. It really shed some light about those terms. [0]: https://jeffreykegler.github.io/personal/timeline_v3 https://jeffreykegler.github.io/personal/timeline_v3 [1]: http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demyst... [2]: http://en.wikipedia.org/wiki/Tree_traversal http://en.wikipedia.org/wiki/Tree_traversal
bmn__ 8y ago
Owl is much more limited. That's not a problem because the documentation tells outright what it can and can't do and what it's for; experts can get things done better if we have specialised tools for different tasks. ANTLR claims to be a general parser¹ but it falls short of its promise. People should stop using it; the software is popular only due to its relentless marketing, but not actually very good. It does not return all possible results for ambiguous grammars. It fails dozens of torture tests, including any grammar that's left-recursive, those cause the software to abort at compile time. You can't simply implement a huge number of language descriptions with it. Instead of simply admitting the algorithm's flaw, the maintainer would rather misdirect in bug reports. I find this disgusting. If you want a general parser that does not disappoint, get Marpa/libmarpa. ¹ https://github.com/antlr/antlr4/blob/4.6/doc/getting-started.md https://github.com/antlr/antlr4/blob/4.6/doc/getting-started... "ANTLR v4 takes whatever you give it--it just doesn't give a crap!"
- parrt 8y ago
  Well, as the author of ANTLR, I will disagree with your assessment of the tool as you can imagine. It never claimed to be a general tool. Specifically, it cannot handle indirect left-recursion; hence, not a general context free grammar parser. It is however the sweet spot between generality and speed. That quote was having a bit of fun using a tiny bit of hyperbole. If you take a look at our academic paper you will see that the general parsers are like walking a minefield. One never knows when they will hit a landmine and the parser takes overnight to parse a file. It took me 30 years to find the sweet spot in power and speed (with the help of Sam Harwell). I welcome the introduction of new tools, but I'm not sure your assessment is accurate nor is your understanding of the parsing landscape. Also as the paper says, "GLR return multiple parse trees (forests) for ambiguous grammars because they were designed to handle natural language grammars, which are often intentionally ambiguous. For computer languages, ambiguity is almost always an error." When was the last time you wanted to parse a language where the same syntax meant two different things? C++ and a few other cases, sure, but most languages are specifically designed to be unambiguous. You are welcome to use a tool that handles all context free grammars, but the speed and ambiguity issues are not something I care to deal with. You also mischaracterize ANTLR's handling of left recursion. It handles immediate left recursion through a rewrite automatically such as for expressions. It does not handle indirect left recursion. You may have not seen ANTLR 4, and are basing your assessment on ANTLR 3? There is no aborting at compile time for left recursion, except in the unusual case of indirect left record. http://www.antlr.org/papers/allstar-techreport.pdf http://www.antlr.org/papers/allstar-techreport.pdf

panic 8y ago

Yeah, they both solve the same problem -- turning text into a structured "parse tree". At the core of each parsing tool is a particular parsing algorithm. The details of this algorithm determine what kind of text the parser can parse, how efficiently it can parse it, and what kind of error messages you get if something goes wrong. There's a huge variety of these algorithms, but nearly all of them are variations on two basic types: "LL" and "LR" parsers. For example, ANTLR uses an "LL(*)" parsing algorithm. This is a great blog post about the difference between the two basic types: http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demyst.... Owl is unique because its algorithm isn't a variation of either of these. It works more like a regular expression parsing algorithm. This makes it more limited than a tool like ANTLR, but it can solve some problems that have been difficult with the existing algorithms. For example, most programming languages allow expressions like "1 - 2" to be used as statements. If you don't use a semicolon or anything to separate the statements, there's an ambiguity -- is "1 - 2" a single expression, or is it the two expressions "1" "-2" in sequence? ANTLR (at least with the default settings I tried) doesn't tell you about this ambiguity at all. It just picks one of the two options ("1 - 2" in this case). This may or may not have been what you were expecting! The problems with ambiguity checking are quite deep (this followup to the earlier blog post I linked goes into more detail: http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why...). Owl's parsing algorithm avoids these problems; it can show you the ambiguity in all cases.

sbjs 8y ago
This is really amazing work! I think the only thing it needs now is to have https://ianh.github.io/owl/try/ https://ianh.github.io/owl/try/ wrapped up into an Electron app that can load/save Owl files and generate header files for you right on your filesystem. That would be awesome! Hmm, I think I see a project in my near future (eyes:winking nose:pointy mouth:open-smile)
adito 8y ago
It's often I stumble upon discussion mentioning the term LL and LR and other stuff related to parsing[0]. Without a proper CS background, it's quite hard to follow along. That first link[1] and the wikipedia page[2] mentioned there are really great. Many thanks for posting those. It really shed some light about those terms. [0]: https://jeffreykegler.github.io/personal/timeline_v3 https://jeffreykegler.github.io/personal/timeline_v3 [1]: http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demyst... [2]: http://en.wikipedia.org/wiki/Tree_traversal http://en.wikipedia.org/wiki/Tree_traversal

bmn__ 8y ago

Owl is much more limited. That's not a problem because the documentation tells outright what it can and can't do and what it's for; experts can get things done better if we have specialised tools for different tasks. ANTLR claims to be a general parser¹ but it falls short of its promise. People should stop using it; the software is popular only due to its relentless marketing, but not actually very good. It does not return all possible results for ambiguous grammars. It fails dozens of torture tests, including any grammar that's left-recursive, those cause the software to abort at compile time. You can't simply implement a huge number of language descriptions with it. Instead of simply admitting the algorithm's flaw, the maintainer would rather misdirect in bug reports. I find this disgusting. If you want a general parser that does not disappoint, get Marpa/libmarpa. ¹ https://github.com/antlr/antlr4/blob/4.6/doc/getting-started.md https://github.com/antlr/antlr4/blob/4.6/doc/getting-started... "ANTLR v4 takes whatever you give it--it just doesn't give a crap!"

parrt 8y ago
Well, as the author of ANTLR, I will disagree with your assessment of the tool as you can imagine. It never claimed to be a general tool. Specifically, it cannot handle indirect left-recursion; hence, not a general context free grammar parser. It is however the sweet spot between generality and speed. That quote was having a bit of fun using a tiny bit of hyperbole. If you take a look at our academic paper you will see that the general parsers are like walking a minefield. One never knows when they will hit a landmine and the parser takes overnight to parse a file. It took me 30 years to find the sweet spot in power and speed (with the help of Sam Harwell). I welcome the introduction of new tools, but I'm not sure your assessment is accurate nor is your understanding of the parsing landscape. Also as the paper says, "GLR return multiple parse trees (forests) for ambiguous grammars because they were designed to handle natural language grammars, which are often intentionally ambiguous. For computer languages, ambiguity is almost always an error." When was the last time you wanted to parse a language where the same syntax meant two different things? C++ and a few other cases, sure, but most languages are specifically designed to be unambiguous. You are welcome to use a tool that handles all context free grammars, but the speed and ambiguity issues are not something I care to deal with. You also mischaracterize ANTLR's handling of left recursion. It handles immediate left recursion through a rewrite automatically such as for expressions. It does not handle indirect left recursion. You may have not seen ANTLR 4, and are basing your assessment on ANTLR 3? There is no aborting at compile time for left recursion, except in the unusual case of indirect left record. http://www.antlr.org/papers/allstar-techreport.pdf http://www.antlr.org/papers/allstar-techreport.pdf