Show HN: Owl, a new kind of parser generator
github.com
github.com
Shameless plug: I saw that you have based the parse tree construction on Dube and Feeley's two-pass algorithm which in its second phase builds a parse tree from a "journal" generated by a DFA in the first recognition phase. This works well, but as you point out, it uses memory linear in the input string for the journal.
While the parse tree must of course still be built and kept in memory, the size of the auxiliary journal can actually be limited to what is semantically required by the ambiguity of the input grammar - in many cases, the bound is O(1). We have written a couple of papers about such a streaming parsing algorithm which you might find interesting for inspiration:
[1] Optimally Streaming Greedy Regular Expression Parsing. https://utr.dk/pubs/files/grathwohl2014-0-paper.pdf
[2] Kleenex: Compiling Nondeterministic Transducers to Deterministic Streaming Transducers. https://utr.dk/pubs/files/grathwohl2016-0-paper.pdf
We never got around to extending the technique to more powerful formalisms such as visibly pushdown languages, although I believe that should be possible.
Regular expressions can also be broken down - by their recursive definition - but curiously they never seem to be, in pratice. e.g.
E = ab+bc
F = x+y
EF = (ab+bc)(x+y)Don't know if you've read this, but it describes how you might build them incrementally:
https://swtch.com/~rsc/regexp/regexp1.html
Also I wonder if instead of using DFA's would it be easier to generate the parser using assembly like instructions, for example:
I'm curious because I've quickly run across two of these types of projects now, but admittedly know very little about them.
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-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...). Owl's parsing algorithm avoids these problems; it can show you the ambiguity in all cases.
I think the only thing it needs now is to have 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)
[0]: https://jeffreykegler.github.io/personal/timeline_v3
[1]: http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demyst...
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... "ANTLR v4 takes whatever you give it--it just doesn't give a crap!"
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.
I've implemented several parser generators myself (nothing as polished as Antlr) and worked on a "rapid prototyping" parser generator tool a while ago (https://github.com/adewes/parsejoy). The idea was a tool that could creates parsers on-the-fly without requiring compilation of any code, and let the user control and modify parsing logic using Lua if necessary. I started writing it in Go but switched to C++ later in order to get more predictable performance.
In the tool I implemented several parsing strategies, notably "parsing expression grammars (PEGs)" as well as a GLR parser (based on the Elkhound paper). And while I find GLR parsing powerful it's not without problems as e.g. errors are hard to debug. That said, it's pretty amazing that you can throw almost any grammar at a GLR parser it and it will (usually) be able to parse it. As you said though writing a "bad" grammar can yield exponential time complexity on some input strings.
PEGs are also nice in general but require you to put more work into the grammar as you are basically required to resolve ambiguities yourself using the "and" or "not" operators. Also, a naive implementation of a PEG parser will have horrid performance as it basically evaluates all possible alternatives via backtracking until it hits a valid one, and for a real-world languages (I've implemented e.g. a Python parser for testing) this will ruin your performance due to the large nesting depth of the rules (Python has around 8-12 levels of rules I think). Using a prefix tree can alleviate this though, as can packrat parsing, which comes with its own cost though as remembering parse results requires memory allocation.
Anyway, in terms of popularity and number of actually implemented grammars, Antlr4 is probably by far the most relevant OS parser generator out there. Thanks for writing it :)
One suggestion I have is to consider improving the tooling for tokenization, as it's often a problem that can be quite challenging in itself. For example, tokenizing Python code is not easy as it's not context-free (due to the indentation that indicates the nesting) and the presence of several types of newline characters (those that occur inside bracketed expressions vs. those that occur outside of them)
Then you certainly won't have a problem changing the wording to make it true, right? The Owl author explains the limitations of his software up-front, why don't you?
> It never claimed to be a general tool.
The documentation does give the impression.
> If you take a look at our academic paper
Consider that HN is populated by craftsmen and businessmen, not scientists. We judge the tools on how well they work in practical terms.
> One never knows when they will hit a landmine and the parser takes overnight to parse a file.
No wonder, I see it's O(n⁴) for ALL()/ANTLR. You need to keep up with the current state of the art, which is O(n³).
> It took me 30 years
Time and effort does not count for anything, the quality of the end result does.
> I'm not sure […] your understanding of the parsing landscape [is accurate]
I can see the practical results of the various software I tried. Does the software get the task done? Yes, fine, that's a candidate for further consideration. No, fine, I can eliminate it. Documentation does not say…? Now one has to come up with experiments to find out the flaws and limitations, multiplied by every single user. That's a waste of people's time.
> When was the last time you wanted to parse a language where the same syntax meant two different things? […] ambiguity is almost always an error.
That was 2014, and I did not design that language. It does contain ambiguities, it can't be helped. No one gains anything by simply wishing it weren't so; there was a task to be done. There exists software that can cope, you should take that as an incentive to improve yours.
> but the speed and ambiguity issues are not something I care to deal with.
… or don't improve. But why would you refuse to? Is not your reputation at stake?
> You also mischaracterize ANTLR's handling of left recursion. […] It does not handle indirect left recursion.
That's what I meant. I was incorrect when I wrote "any grammar that's left-recursive".
Btw, why did you choose the name Owl?
The restriction is that any recursion in the grammar has to be inside explicit begin and end tokens. For example, you can't write a rule like
stmt = 'if' expr 'then' stmt* | expr
stmt = [ 'if' expr 'then' stmt* 'end' ] | expr
> Btw, why did you choose the name Owl?
I wanted a bird name, and Owl was short and easy to type!
. . .
[1] Though in this case, the language is still visibly pushdown, since you can expand it manually to:
stmt = (('if' expr 'then')+ expr*)+ | expr
To automate this expansion process (and re-association into a sensible parse tree), Owl also has syntax for operators with precedence. Here's an example: https://ianh.github.io/owl/try/#expr
yes: S -> <a> S </a> | e
no: S -> <a></a> S | e
I'm interested that you have this too, but it seems to have the same problems I found: https://news.ycombinator.com/item?id=17650770
It would be very exciting if you have found a way around this!
expr = number (('*' | '+') number)*
My solution was to add special syntax which makes rules like this automatically:
expr = number : num
.operators infix left '*' : times
.operators infix left '+' : plus
Nice, a language can be recognized, even if a different parse tree.
I vaguely recall the shunting yard algorithm... am I right in characterising your solution as a second level of parsing? It's not "pure", but from a practical point of view, it's no worse than back-references in PCRE. The practical issue is just of ui usability.
print 2*3 + 4Besides guaranteed O(n) parsing time, it's not clear to me what the advantages of Owl are, and Marpa runs in O(n) time on any grammar that Owl accepts, and many more (and I think it can or could easily be modified to warn if it can't guarantee O(n) parsing time for a particular grammar).
I'm doing some analysis in R, and the data is generated by a program that more or less just spit things out.
Its values are comma separated, but if there are 2 values on one line, it is column 1 and 10. If the first character on a line is a comma, it is not a separator but a value. Commas inside quotations or escaped with backslashes are also values.
The list of special cases and oddities is pretty long. Right now I have a large switch statement that applies different search and replace on all sorts of conditions before feeding the CSV to read_csv.
Is this a case for owl? Can I use it within R or Python?
Alternatively for python you could use a parse combinator like parsec. Depending on how complicated your file can get, using parsec could very likely be the better choice as it has first class support in python and seems powerful enough to handle your use case.
There do seem to be a number of parse combinators in R but none of them seem as well established as parsec for python (which is based on the much more well known parsec for haskell).
A quick look around seems to show that python will be your best bet for parsing as it has some decent tooling. Here is an article on some of the different parse generators/parse combinators in the space.
Like:
expr = expr + expr
expr = expr.method(args)
expr =
identifier : var
.operators postfix
'.' identifier '(' args ')' : method-call
.operators infix left
'+' : plusLet's say you're parsing:
1 + 5 + 7
You can choose to look at it as 7 plus the expression (1+5) or you can choose to look at it as the literal 1 with a +5 suffix that then has a +7 suffix. So in this simplified example, instead of defining:
expr = literal | expr + expr
you'd define expr as:
expr = literal (+ expr)*
That shift in how I thought about the language I was creating basically ended all the left-recursive problems I was having with my parser generator library.