4 ms·

Just generalized parsing algorithms in general would be good to include, I think. It looks like the course only plans to cover basic LL/LR, which are admittedly

Just generalized parsing algorithms in general would be good to include, I think. It looks like the course only plans to cover basic LL/LR, which are admittedly the most commonly used parsers but more would be interesting. A fun one to include might be Might's "Parsing with Derivatives", which is algorithmically novel (though not very performant). I think there was a recent innovation on this: "Parsing with Zippers" at ICFP this year. Hard agree that GLL is hard to follow. I've read the paper a number of times and struggle with it every time haha.

giraj 6y ago
Thanks for mentioning "Parsing with Zippers"! I read "Parsing with Derivatives" last week and wondered if that could be taken further. The paper can be found here: https://dl.acm.org/doi/10.1145/3408990 https://dl.acm.org/doi/10.1145/3408990
- DonaldPShimoda 6y ago
  It's always fun to spread new research around the community! I remember reading PwD and thinking it was just so cool as an algorithm, though the performance concerns were a bit of a turn-off. Still, I always like to talk to people about it because I just think it's such an elegant approach to the problem. As for PwZ, I know one of the authors so maybe I'm a little biased, but I also thought his ICFP talk was quite good. It's here: https://youtu.be/fakSKvP9yaM?t=6180 https://youtu.be/fakSKvP9yaM?t=6180
thesz 6y ago
Parsing with derivatives is not all that slow: https://www.microsoft.com/en-us/research/uploads/prod/2019/02/SRM_tacas19.pdf https://www.microsoft.com/en-us/research/uploads/prod/2019/0... The paper shows that it can compete with re2 (by google).
- DonaldPShimoda 6y ago
  This is not what I'm talking about. "Parsing with Derivatives" is the title of a 2011 paper by Matt Might, David Darais, and Daniel Spiewak that generalizes the Brzozowski derivative from regular expressions to context-free grammars. In the present discussion, I assumed the context to be about CFGs instead of REs because that is most often what people are referring to when we talk about parsers in programming languages, though I admit that I could have been more explicit about this. What you linked is an improvement of the Brzozowski derivative, but it does not constitute a parser for CFGs.
  - thesz 6y ago
    According to "Parsing Techniques: A Practical Guide" [1], it is quite common for computer languages to have most of the grammar in the regular grammars class and some parts to be, actually, context-free. [1] https://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf https://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf For example, consider addition and subtraction in most grammars. They can be expressed as "summation ::= factor ((PLUS | MINUS) factor) * " and factor can be similarly defined as "factor ::= multiplicand ((MUL | DIV) multiplicand) * ". Authors of PTAPG note that these regularities can be exploited for speed. And I think "parsing with derivatives" techniques can be used for speedy parsing too.
    - DonaldPShimoda 6y ago
      Uhh sure, but you're kind of deflecting. The phrase "parsing with derivatives" (or "Might's 'Parsing with Derivatives'" as I wrote in my initial comment to which you first replied) refers specifically to the technique developed by Might et al that generalizes the Brzozowski derivative to CFGs. And, more to the point, their technique has very poor performance, which is addressed directly in the paper. If you talk to parsing people about "parsing with derivatives", they will undoubtedly assume that you specifically mean the Might et al work and not some other, more general notion, regardless of whether one could technically call such notion a "parsing with derivatives" technique. I have never heard of anybody calling anything else "parsing with derivatives" and, indeed, the paper you linked never uses this phrase (the closest they come is "matching with derivatives", which is a bit different in semantics). I appreciate the points you've raised, and I do think the RE-parsing paper you linked previously looks very interesting (I hadn't seen it before), but the crux of the issue is that you misinterpreted what I said and haven't yet acknowledged that misinterpretation. Instead, it feels like you're trying to fight me on other points to win back some ground or something, though I hope I'm just misreading this because I find that kind of a frustrating conversational method.
eru 6y ago
Parsing with derivatives has been around for a long time, at least for regular languages.
- DonaldPShimoda 6y ago
  Yes, the technique was introduced in 1964 by Brzozowski. But the Brzozowski derivative (as it is now known) was generalized to handle all CFGs (instead of only REs) in the 2011 Might et al paper titled "Parsing with Derivatives". This work was then refined this year with "Parsing with Zippers", which generalizes Huet's Zipper data structure to represent CFGs (instead of acyclical, deterministic tree structures) and uses that to re-build the 2011 algorithm with a better representation, achieving greater performance with a small algorithm.
  - eru 6y ago
    Thanks! I'll check out the papers.

giraj 6y ago

Thanks for mentioning "Parsing with Zippers"! I read "Parsing with Derivatives" last week and wondered if that could be taken further. The paper can be found here: https://dl.acm.org/doi/10.1145/3408990 https://dl.acm.org/doi/10.1145/3408990

DonaldPShimoda 6y ago
It's always fun to spread new research around the community! I remember reading PwD and thinking it was just so cool as an algorithm, though the performance concerns were a bit of a turn-off. Still, I always like to talk to people about it because I just think it's such an elegant approach to the problem. As for PwZ, I know one of the authors so maybe I'm a little biased, but I also thought his ICFP talk was quite good. It's here: https://youtu.be/fakSKvP9yaM?t=6180 https://youtu.be/fakSKvP9yaM?t=6180

thesz 6y ago

Parsing with derivatives is not all that slow: https://www.microsoft.com/en-us/research/uploads/prod/2019/02/SRM_tacas19.pdf https://www.microsoft.com/en-us/research/uploads/prod/2019/0... The paper shows that it can compete with re2 (by google).

DonaldPShimoda 6y ago
This is not what I'm talking about. "Parsing with Derivatives" is the title of a 2011 paper by Matt Might, David Darais, and Daniel Spiewak that generalizes the Brzozowski derivative from regular expressions to context-free grammars. In the present discussion, I assumed the context to be about CFGs instead of REs because that is most often what people are referring to when we talk about parsers in programming languages, though I admit that I could have been more explicit about this. What you linked is an improvement of the Brzozowski derivative, but it does not constitute a parser for CFGs.
- thesz 6y ago
  According to "Parsing Techniques: A Practical Guide" [1], it is quite common for computer languages to have most of the grammar in the regular grammars class and some parts to be, actually, context-free. [1] https://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf https://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf For example, consider addition and subtraction in most grammars. They can be expressed as "summation ::= factor ((PLUS | MINUS) factor) * " and factor can be similarly defined as "factor ::= multiplicand ((MUL | DIV) multiplicand) * ". Authors of PTAPG note that these regularities can be exploited for speed. And I think "parsing with derivatives" techniques can be used for speedy parsing too.
  - DonaldPShimoda 6y ago
    Uhh sure, but you're kind of deflecting. The phrase "parsing with derivatives" (or "Might's 'Parsing with Derivatives'" as I wrote in my initial comment to which you first replied) refers specifically to the technique developed by Might et al that generalizes the Brzozowski derivative to CFGs. And, more to the point, their technique has very poor performance, which is addressed directly in the paper. If you talk to parsing people about "parsing with derivatives", they will undoubtedly assume that you specifically mean the Might et al work and not some other, more general notion, regardless of whether one could technically call such notion a "parsing with derivatives" technique. I have never heard of anybody calling anything else "parsing with derivatives" and, indeed, the paper you linked never uses this phrase (the closest they come is "matching with derivatives", which is a bit different in semantics). I appreciate the points you've raised, and I do think the RE-parsing paper you linked previously looks very interesting (I hadn't seen it before), but the crux of the issue is that you misinterpreted what I said and haven't yet acknowledged that misinterpretation. Instead, it feels like you're trying to fight me on other points to win back some ground or something, though I hope I'm just misreading this because I find that kind of a frustrating conversational method.

eru 6y ago

Parsing with derivatives has been around for a long time, at least for regular languages.

DonaldPShimoda 6y ago
Yes, the technique was introduced in 1964 by Brzozowski. But the Brzozowski derivative (as it is now known) was generalized to handle all CFGs (instead of only REs) in the 2011 Might et al paper titled "Parsing with Derivatives". This work was then refined this year with "Parsing with Zippers", which generalizes Huet's Zipper data structure to represent CFGs (instead of acyclical, deterministic tree structures) and uses that to re-build the 2011 algorithm with a better representation, achieving greater performance with a small algorithm.
- eru 6y ago
  Thanks! I'll check out the papers.