4 ms·

I have not published any papers on parsing, but I've read a large chunk of the Handbook on Parsing, am buddies with Terrence Parr and have given a lecture on th

I have not published any papers on parsing, but I've read a large chunk of the Handbook on Parsing, am buddies with Terrence Parr and have given a lecture on the ALL() parsing algorithm, and worked for a company that has perhaps the most extensive collection of GLR parsers around. (Whereas langcc boasts automatically-generated parsers for the easy-to-parse Python and Go, my old employer has automatically-generated parsers for Ruby, C++, COBOL, and about 100 others.) I would not consider myself an expert on parsing in comparison to the few who research it, but I would consider myself expert by the standards of most professional compiler engineers, and certainly by the standards of the average software engineer. When I see a library like this, I ask "What new things does this thing bring to the table?" For that, before I even get into trying to understand what it does, I want to see how well the author understands what's already been done and how it compares to prior work. My very blunt assessment: I don't see any reason to take this library seriously. I looked at the 40 page paper. I can tell just from the citations that it takes a very 70's few of parsing. And when it does discuss other work, it mostly gets it wrong. A few examples: Page 8: He writes about the "ETL family, also called GLR parsing." "ETL family" seems to be a term of his own coinage, and he's writing about GLR parsing and Earley parsing as if they're the same. Now that I think about it, I see some resemblance, but they're usually considered quite different. See e.g.: https://cstheory.stackexchange.com/questions/30903/why-tomita-created-glr-and-didnt-use-earley https://cstheory.stackexchange.com/questions/30903/why-tomit... * Page 9 > There has also been significant development of the top-down family of parser generators, including tools such as ANTLR [PQ95] which support a superset of LL(k) grammars, as well as their parallel counterparts, referred to as Generalized LL (GLL). For the reasons described above, we believe that while top-down parsers are theoretically interesting, the grammars they support are not sufficiently general to capture full programming languages.6 Notably, they are significantly more restrictive than LR(k), and we argue that even the latter is not sufficiently general in its standard formulation. This has not been true since ANTLR 2, released 25 years ago. The LL() algorithm of ANTLR 3, described in a 2011 publication, is capable of parsing even some context-sensitive grammars. Page 9: > The tree automata of Adams and Might [AM17] are similar to our implementation of monotonic attributes; they differ in that they impose left-to-right sequencing on the attribute constraints (whereas attributes can refer to arbitrary constituents of a grammar rule), and require productions to be duplicated (whereas attributes are boolean or integer values layered independently on top of the standard context-free grammar rules)." This is one of my favorite papers of the last 5 years, and this is totally inaccurate. The user writes down a normal grammar and syntactic regular expressions for forbidden subterms. From that, it automatically generates a new grammar that e.g.: breaks symmetries. In short, I think the author has the knowledge to claim that his solution beats the best that the 70's and 80's has to offer. I am not motivated to look at this any further because I've been given no reason to believe it's had a fair comparison to what the 2010's has to offer. I continue to recommend ANTLR 4 for your parser-generator needs. Its ALL(*) algorithm truly is magic. tree-sitter is also good and has a lot of momentum. Joe Zimmerman: If you're reading this, please don't take it too personally. I'm reacting to the claims of the work more than the work itself. If you'd like, I'll gladly discuss this with you. Either I'll learn something new, you'll get better at clarifying your ideas, or both.

samsquire 4y ago
Someone has done something awesome and good, why not start from that perspective of supporting and recognising someone else's talent. From my understanding of your undertone of your message you are telling them they don't know what they're talking about when I don't think that's true. There's no need to put people down.
- Darmani 4y ago
  Satirical answer: Because I'm a crusty old scientist who needs to defend his turf. Self-serving answer: I'm doing the author a favor as perhaps the first person with my level of knowledge of the field putting effort into giving feedback on the work. Serious answer: Because it's presenting itself as an artifact of scientific novelty rather than as an engineering accomplishment. It is making major claims not only about itself but also about the entire state-of-the-art. (You could say that the langcc papers put down the entire field of parsing.) Its contributions and scholarship therefore need to be evaluated like any other scientific work.
camgunz 4y ago
I ran into a couple issues using ANTLR 4. The first is that it mostly required my build pipeline to have a JVM, which wasn't super convenient. The second is that the generated Python parsers are super slow, like too slow for even just iterating while developing. I almost wish ANTLR 5 wouldn't be about any new parsing stuff, but just a refocusing of the project on implementing its compiler-generator in the popular languages. It basically is that already, but it's pretty clearly not first class.
jzimmerman64 4y ago
> Whereas langcc boasts automatically-generated parsers for the easy-to-parse Python and Go, my old employer has automatically-generated parsers for Ruby, C++, COBOL, and about 100 others. Python may be (comparatively) easy to parse, but Golang is not - it is _barely_ LR(1) with the extensions described in https://arxiv.org/pdf/2209.08383.pdf https://arxiv.org/pdf/2209.08383.pdf (notably, semantic attributes and the CPS transformation). > my old employer has automatically-generated parsers for Ruby, C++, COBOL, and about 100 others GLR parsing, as I note in the paper, is very different from pure LR(k) parsing. Are the automatically-generated parsers you mention guaranteed to run in linear time? Are they more efficient than hand-written recursive-descent for the same languages? Not to mention that full C++ parsing, as I also note in the paper, is undecidable, due to simple ambiguities such as "x * y;" (whose parse depends on whether x names a value or a type, which may depend on template computations). So it should be impossible to fully automatically generate a parser for C++ from a declarative BNF spec, without some significant ad-hoc machinery on top. > he's writing about GLR parsing and Earley parsing as if they're the same. Now that I think about it, I see some resemblance, but they're usually considered quite different. I'm not calling them "the same"; I'm grouping them together into the same family, as they share some particular characteristics relevant to the paper (polynomial but not necessarily linear time, left-to-right, dynamic-programming-style). > This has not been true since ANTLR 2, released 25 years ago. The LL() algorithm of ANTLR 3, described in a 2011 publication, is capable of parsing even some context-sensitive grammars. Again, the implicit claim here is "generated from a declarative BNF spec, efficiently, with guaranteed linear time, parsing full industrial languages...". Of course one can parse many languages with backtracking. Do you have examples of full industrial languages parsed with ANTLR 3 that satisfy the relevant criteria? > This is one of my favorite papers of the last 5 years, and this is totally inaccurate. Could you say what, specifically, is inaccurate about it? > In short, I think the author has the knowledge to claim that his solution beats the best that the 70's and 80's has to offer. I am not motivated to look at this any further because I've been given no reason to believe it's had a fair comparison to what the 2010's has to offer. Again, I would ask you to exhibit concrete results here. Show me an existing tool that is already capable of generating a parser for Golang 1.17.8, from a declarative BNF spec, with guaranteed linear-time parsing, and that matches or exceeds the hand-written parser in speed.

samsquire 4y ago

Someone has done something awesome and good, why not start from that perspective of supporting and recognising someone else's talent. From my understanding of your undertone of your message you are telling them they don't know what they're talking about when I don't think that's true. There's no need to put people down.

Darmani 4y ago
Satirical answer: Because I'm a crusty old scientist who needs to defend his turf. Self-serving answer: I'm doing the author a favor as perhaps the first person with my level of knowledge of the field putting effort into giving feedback on the work. Serious answer: Because it's presenting itself as an artifact of scientific novelty rather than as an engineering accomplishment. It is making major claims not only about itself but also about the entire state-of-the-art. (You could say that the langcc papers put down the entire field of parsing.) Its contributions and scholarship therefore need to be evaluated like any other scientific work.

camgunz 4y ago

I ran into a couple issues using ANTLR 4. The first is that it mostly required my build pipeline to have a JVM, which wasn't super convenient. The second is that the generated Python parsers are super slow, like too slow for even just iterating while developing. I almost wish ANTLR 5 wouldn't be about any new parsing stuff, but just a refocusing of the project on implementing its compiler-generator in the popular languages. It basically is that already, but it's pretty clearly not first class.

jzimmerman64 4y ago

> Whereas langcc boasts automatically-generated parsers for the easy-to-parse Python and Go, my old employer has automatically-generated parsers for Ruby, C++, COBOL, and about 100 others. Python may be (comparatively) easy to parse, but Golang is not - it is _barely_ LR(1) with the extensions described in https://arxiv.org/pdf/2209.08383.pdf https://arxiv.org/pdf/2209.08383.pdf (notably, semantic attributes and the CPS transformation). > my old employer has automatically-generated parsers for Ruby, C++, COBOL, and about 100 others GLR parsing, as I note in the paper, is very different from pure LR(k) parsing. Are the automatically-generated parsers you mention guaranteed to run in linear time? Are they more efficient than hand-written recursive-descent for the same languages? Not to mention that full C++ parsing, as I also note in the paper, is undecidable, due to simple ambiguities such as "x * y;" (whose parse depends on whether x names a value or a type, which may depend on template computations). So it should be impossible to fully automatically generate a parser for C++ from a declarative BNF spec, without some significant ad-hoc machinery on top. > he's writing about GLR parsing and Earley parsing as if they're the same. Now that I think about it, I see some resemblance, but they're usually considered quite different. I'm not calling them "the same"; I'm grouping them together into the same family, as they share some particular characteristics relevant to the paper (polynomial but not necessarily linear time, left-to-right, dynamic-programming-style). > This has not been true since ANTLR 2, released 25 years ago. The LL() algorithm of ANTLR 3, described in a 2011 publication, is capable of parsing even some context-sensitive grammars. Again, the implicit claim here is "generated from a declarative BNF spec, efficiently, with guaranteed linear time, parsing full industrial languages...". Of course one can parse many languages with backtracking. Do you have examples of full industrial languages parsed with ANTLR 3 that satisfy the relevant criteria? > This is one of my favorite papers of the last 5 years, and this is totally inaccurate. Could you say what, specifically, is inaccurate about it? > In short, I think the author has the knowledge to claim that his solution beats the best that the 70's and 80's has to offer. I am not motivated to look at this any further because I've been given no reason to believe it's had a fair comparison to what the 2010's has to offer. Again, I would ask you to exhibit concrete results here. Show me an existing tool that is already capable of generating a parser for Golang 1.17.8, from a declarative BNF spec, with guaranteed linear-time parsing, and that matches or exceeds the hand-written parser in speed.