4 ms·
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
by 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 agoThis 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 agoIt'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