Glush: A robust parser compiler built using non-deterministic automatons • Hacker News Board

Re: Glush: A robust parser compiler built using non-deterministic automatons

#21

Post by joe_the_user » Sat, Dec 14, 2019, 8:34 AM UTC

seanmcdirmid wrote: post #19

chrisaycock wrote: post #18

> However, in practice it turns out that LALR(1) isn’t always the answer. For instance, both GCC, Rust and Go have chosen to use handwritten parsers that are not based on a declarative grammar file. I find this disappointing: We have decades of experience with specifying languages in a declarative format, and apparently it’s still easier to manually write parsers. Obviously there’s something lacking with the algorith…

Error recovery and reporting are for sure the biggest challenge of a production parser. If you work out of band, you can play a lot of tricks in your parser to make it much more effective in handling errors. For example, braces can be matched in many languages without parsing any other constructs in the language, meaning these errors can all be reported and recovered from independent of the rest of the language. Then…

I don't think it's just error handling. A nice, human readable form has significant chance of being ambiguous - you can remove the ambiguity with a variety of transforms, putting the code into Greibach Normal Form, and this resolves the ambiguities. ... and translates pretty directly to a hand-written recursive descent parser (which you can generate also). But the thing is that here the code essentially serves as a lower level of abstraction, teasing out what you really mean. Which is to say there's nothing wrong with the code being the final spec, that way you don't have to keep the code in sync with the spec.

Re: Glush: A robust parser compiler built using non-deterministic automatons

#22

Post by dukoid » Sat, Dec 14, 2019, 10:24 AM UTC

chrisaycock wrote: post #18

> However, in practice it turns out that LALR(1) isn’t always the answer. For instance, both GCC, Rust and Go have chosen to use handwritten parsers that are not based on a declarative grammar file. I find this disappointing: We have decades of experience with specifying languages in a declarative format, and apparently it’s still easier to manually write parsers. Obviously there’s something lacking with the algorith…

There is also the friction added by throwing in another language and subsystem, potentially with some fancy build system requirements for integrating code generation....

Re: Glush: A robust parser compiler built using non-deterministic automatons

#23

Post by ltratt » Sat, Dec 14, 2019, 10:59 AM UTC

chrisaycock wrote: post #18

> However, in practice it turns out that LALR(1) isn’t always the answer. For instance, both GCC, Rust and Go have chosen to use handwritten parsers that are not based on a declarative grammar file. I find this disappointing: We have decades of experience with specifying languages in a declarative format, and apparently it’s still easier to manually write parsers. Obviously there’s something lacking with the algorith…

I completely agree: the poor quality of error reporting in parsing tools is a significant reason not to use them. When I started looking into this a couple of years back, what surprised me is how much work there's been in this spread over decades.

Building upon that (and obvious bias alert!) led us to come up with a couple of new algorithms. The current paper draft is https://arxiv.org/abs/1804.07133 (a future version of that paper will probably chop out MF which, in retrospect, adds too much complexity over CPCT+ for the relatively small gains). The Rust library (https://crates.io/crates/lrpar) it's implemented in is documented at https://softdevteam.github.io/grmtools/master/book/errorreco... which is probably a friendlier starting point. Summary: one can do a surprisingly decent job of error recovery for very little work.

Re: Glush: A robust parser compiler built using non-deterministic automatons

#24

Post by erezsh » Sat, Dec 14, 2019, 11:27 AM UTC

That sounds really cool, and I hope it will find success. The field of parsing truly needs some refreshment, especially in usability.

I do have a few questions:

1. You claim the algorithm used guarantees O(n^3) for all CFGs, but is different from Earley and CYK. Are there more details for this algorithm, perhaps with a rigorous mathematical proof for this claim?

2. How is Glush's performance in relation to Earley, in terms of constant time and memory requirements? (even for low complexity, a high constant can be problematic)

3. How do you deal with ambiguity? The blog mentions priority, but is there a way to get something similar to a SPPF?

Re: Glush: A robust parser compiler built using non-deterministic automatons

#25

Post by tom_mellior » Sat, Dec 14, 2019, 11:28 AM UTC

sshine wrote: post #13

Skipping to "Glush, the algorithm" can be helpful if you already know the history of parsing. TL;DR: Glush grammars consist of "rules" that are regexes + recursion of rule calls. Compiles to NFAs. I'm not sure I see the point in declaring precedence levels inside rules -- maybe it's just a preference thing, but I like having operator precedences in a separate section of the grammar. Yacc does this. Megaparsec for Has…

> Compiles to NFAs.

No. It cannot, since NFAs cannot parse languages that are not regular. Rather, the algorithm executes like a pushdown automaton. I don't think it's correct to call this compilation.

> I cannot decipher from the article the exact expressive power.

To me it seems to suggest being able to parse (exactly) all context-free languages.

Re: Glush: A robust parser compiler built using non-deterministic automatons

#26

Post by tom_mellior » Sat, Dec 14, 2019, 11:36 AM UTC

Nice article, this looks like a useful parser generator. Though, as others have mentioned, error reporting is a very important point that should be considered even at this early stage.

Here's something that surprised me though:

> a parser toolkit that lets you create efficient parsers in multiple languages (currently JavaScript, Go, and Ruby)

> [some other approach] it looked very interesting, but it’s not completely smooth. First of all, all of the implementations have been in highly expressive, garbage collected languages (Haskell, Scala, Racket).

This isn't the author's only reason to dismiss that alternative approach, but it's still a strange point to spend almost an entire paragraph on. If all the targets the author currently envisions are GC'd languages, it's premature pessimization to worry about how other, hypothetical, targets might be accommodated.

Re: Glush: A robust parser compiler built using non-deterministic automatons

#27

Post by tempguy9999 » Sat, Dec 14, 2019, 3:52 PM UTC

chrisaycock wrote: post #18

> However, in practice it turns out that LALR(1) isn’t always the answer. For instance, both GCC, Rust and Go have chosen to use handwritten parsers that are not based on a declarative grammar file. I find this disappointing: We have decades of experience with specifying languages in a declarative format, and apparently it’s still easier to manually write parsers. Obviously there’s something lacking with the algorith…

> But now I've just polluted my once-pristine grammar file

What's bollixed up your grammar file are the users who absolutely insist on not writing syntactically perfect programs every time.

Your 2nd example is still cleaner than writing a hand parser that does the same thing, surely? A slightly mucky DSL has got to be cleaner, clearer, shorter and so more maintainable than a handwritten equivalent, no?

What would you want the grammar language to look like that handled errors 'properly'?

Re: Glush: A robust parser compiler built using non-deterministic automatons

#28

Post by seanmcdirmid » Sat, Dec 14, 2019, 5:58 PM UTC

joe_the_user wrote: post #21

seanmcdirmid wrote: post #19

Earlier quoted context omitted.

Error recovery and reporting are for sure the biggest challenge of a production parser. If you work out of band, you can play a lot of tricks in your parser to make it much more effective in handling errors. For example, braces can be matched in many languages without parsing any other constructs in the language, meaning these errors can all be reported and recovered from independent of the rest of the language. Then…

I don't think it's just error handling. A nice, human readable form has significant chance of being ambiguous - you can remove the ambiguity with a variety of transforms, putting the code into Greibach Normal Form, and this resolves the ambiguities. ... and translates pretty directly to a hand-written recursive descent parser (which you can generate also). But the thing is that here the code essentially serves as a l…

For a mainstream programming languages, complicated ambiguities are hard on users anyways, by writing your parser by hand you have an extra incentive to keep the grammar simple (eg Scala). A lot of the power a parser generator gives you shouldn’t be used.

Re: Glush: A robust parser compiler built using non-deterministic automatons

#29

Post by joe_the_user » Sat, Dec 14, 2019, 8:36 PM UTC

seanmcdirmid wrote: post #28

joe_the_user wrote: post #21

Earlier quoted context omitted.

I don't think it's just error handling. A nice, human readable form has significant chance of being ambiguous - you can remove the ambiguity with a variety of transforms, putting the code into Greibach Normal Form, and this resolves the ambiguities. ... and translates pretty directly to a hand-written recursive descent parser (which you can generate also). But the thing is that here the code essentially serves as a l…

For a mainstream programming languages, complicated ambiguities are hard on users anyways, by writing your parser by hand you have an extra incentive to keep the grammar simple (eg Scala). A lot of the power a parser generator gives you shouldn’t be used.

Remember, complicated ambiguities are different from complicated structures.

The Ruby programming language is a poster-child for potential ambiguities that seem simple - allowing conditional before and after for example. Essentially, all the programming languages that are "human like" wind-up like this, with the sort of ambiguities that people are comfortable with in natural language. This has a cost in terms of exact expression but a lot of users think of this as being "easy on them".

Oppositely, languages without grammatical ambiguities often seem irritatingly verbose to use - new users dislike lisp's parenthesis proliferation and personally find Scala irritatingly verbose.

The complexity of compiler-writing approaches as limiting factor to language complexity probably depending what someone is familar with. Some people can spit out annotated YACC grammar pretty easily whereas my head swimming looking at the stuff. I can produce a recursive descent parser from a grammar pretty easily however.

Re: Glush: A robust parser compiler built using non-deterministic automatons

#30

Post by judofyr » Mon, Dec 16, 2019, 7:42 AM UTC

erezsh wrote: post #24

That sounds really cool, and I hope it will find success. The field of parsing truly needs some refreshment, especially in usability. I do have a few questions: 1. You claim the algorithm used guarantees O(n^3) for all CFGs, but is different from Earley and CYK. Are there more details for this algorithm, perhaps with a rigorous mathematical proof for this claim? 2. How is Glush's performance in relation to Earley, in…

Author of the article here. Thanks for your comments!

> 1. You claim the algorithm used guarantees O(n^3) for all CFGs, but is different from Earley and CYK. Are there more details for this algorithm, perhaps with a rigorous mathematical proof for this claim?

Not quite yet. There is a lot more work needed and writing this article was one step in right direction. I was hoping I was able to get even closer to

> 2. How is Glush's performance in relation to Earley, in terms of constant time and memory requirements? (even for low complexity, a high constant can be problematic)

This is yet to be determined. A few comments:

- I'm not 100% concerned about performance because as mentioned in the article, I don't plan to use this in a place where performance is critical.

- I'm not too worried about the performance since I'm not doing too complicated data structures (it's all hash maps), and most intermediate data structures are small in size and are probably best implemented linearly (e.g. plain array) for practical grammars with few ambiguities.

- It's based on NFA-style "advance one state at a time" which actually is not good for performance. This means that parsing a keyword such as "function" actually passed through 8 different states instead of just looking ahead and jumping straight ahead. I think taking advantage of these look ahead will probably help a lot

> 3. How do you deal with ambiguity? The blog mentions priority, but is there a way to get something similar to a SPPF?

A single output from the parser is conceptually a flat list of _marks_ (think like a reverse RPN):

    // this input:
    1 + 2 * 3 + 4
    // with this precedence:
    (1 + (2 * 3)) + 4
    // could generate this flat list of marks:
    add, add, 1, mul, 2, 3, 4

The total output from the parser is a "tree of marks".