4 ms·

> There’s a lot of literature about error recovery for LR parsers, how come academics haven’t figured this out already? I have a bold claim to make: error-recov

> There’s a lot of literature about error recovery for LR parsers, how come academics haven’t figured this out already? I have a bold claim to make: error-recovery research in academia is focusing on a problem irrelevant for IDEs. Specifically, the research is focused on finding “minimal cost repair sequence” The parsing literature can be a bit difficult to navigate because the field is effectively dead for research purposes. However, other models of errors have been considered. Tim Wagner's PhD thesis is the best discussion of the application of LR parsing techniques in IDEs, and this paper extracted from it discusses error recovery in particular: http://harmonia.cs.berkeley.edu/papers/twagner-er.pdf http://harmonia.cs.berkeley.edu/papers/twagner-er.pdf In the non-interactive context, Richter's work on error recovery by substring parsing is also very interesting, in that it doesn't cause spurious errors when attempting to recover from errors, and it only depends on the language and not the grammar or parsing technique used: https://dl.acm.org/doi/10.1145/3916.4019 https://dl.acm.org/doi/10.1145/3916.4019 For LR grammars (and many other grammars), the necessary substring parsing can be done in linear time using variations of the GLR algorithm.

tlb 6y ago
For error recovery, do any parsers have a notion of which tokens are more likely to be wrong? For example, in an actively edited C++ file, braces are more likely correct than angle brackets which are overloaded. So it's reasonable to auto-insert closing > if you see a } with an open <, but not reasonable to insert a } if you see a > with an open <.
- ltratt 6y ago
  > For error recovery, do any parsers have a notion of which tokens are more likely to be wrong? lrpar has a %avoid_insert declaration which allows users to say "these token types are better avoided if there are other equivalently good repair sequences". It's simple, but it works well https://softdevteam.github.io/grmtools/master/book/errorrecovery.html#biasing-repair-sequences https://softdevteam.github.io/grmtools/master/book/errorreco...
  - maxbrunsfeld 6y ago
    I like this solution, and have thought about adding something similar as an "advanced feature" in Tree-sitter grammars. I'm interested to see how you've used it in grammars.
- raphlinus 6y ago
  To the extent that there will be further research on this problem, I think it will be driven by machine learning. We're already seeing this with autocompletion with TabNine, and no reason a similar approach couldn't work for the other issues facing draft code. If you had a large dataset of keystroke-by-keystroke edit streams, you'd be able to match up erroneous code with the eventual fix. Google or Facebook could absolutely capture these datasets for their internal work if they wanted, and I suspect the results could be scary-good. They wouldn't be able to release the models, though, even for their open source work (Chromium and Android), because it would have such a high chance of revealing internal secrets.
  - the_duke 6y ago
    I haven't used it, but Microsoft is already offering machine learning based completions with IntelliCode [1]. See also the introductory blog post. [2] It also offers sharing refined predictions within teams. I think we will see some interesting developments in this domain over the next few years. [1] https://visualstudio.microsoft.com/services/intellicode/ https://visualstudio.microsoft.com/services/intellicode/ [2] https://devblogs.microsoft.com/visualstudio/ai-assisted-intellisense-for-your-teams-codebase/ https://devblogs.microsoft.com/visualstudio/ai-assisted-inte...
raphlinus 6y ago
In the open source world, both Tree-sitter and Lezer are based on GLR, and cite Tim Wagner's thesis. So, while it might be possible to do better even staying in the GLR world, I think the comparison based on Tree-sitter is fair. I think these projects show that GLR is viable (there's a good set of grammars written for Tree-sitter), but I am also very willing to believe that the parser in rust-analyzer is more finely tuned for the specific needs of a Rust IDE.
- cwzwarich 6y ago
  I was only commenting on his claims about the academic literature on parsing, not whether he should use the techniques verbatim. The problem with structured approaches to incremental parsing is that you rarely want incremental parsing alone. You’re going to want to do something else with the resulting parse tree (name resolution, type checking, compilation, etc.) and no structured approach to incremental parsing will help you there. Once you’re stuck writing an incremental type checker by hand, you probably have the right framework for also writing an incremental parser. Rust has additional complications, e.g. the macro system and the fact that the language is defined by a single implementation.
  - raphlinus 6y ago
    I can confirm that Rust's macro system presents massive difficulties. For example, rustfmt is currently broken for subdirectory in Druid because of the use of a `cfg_if!` macro. We filed a bug (https://github.com/rust-lang/rustfmt/issues/4266 https://github.com/rust-lang/rustfmt/issues/4266) but it got closed without (as far as I can tell) actually being fixed. Our present approach is to remove the use of the macro, but this is a bit of a bad sign: two features (macros and automatic formatting) that work fine individually, but their interactions break.
- maxbrunsfeld 6y ago
  While Tree-sitter is heavily influenced by Wagner's thesis, our error recovery strategy actually uses a novel approach, so it is fair to question whether Wagner's would have different properties. For error recovery, Tree-sitter is currently optimized for some goals that are a bit different from the goals of a single-language IDE like Rust-Analyzer: * Like RA, we want to minimize the impact of syntax errors on basic features like syntax highlighting and symbol name extraction (which are important to GitHub, and in lightweight text editors like Neovim and Atom). * Unlike RA, I wanted to avoid requiring grammar authors to think about error recovery at all. * We needed to tightly control the performance cost of pathological error recovery cases, like parsing a large Ruby file as Go (either accidentally or adversarially). My understanding is that Wagner's thesis is mostly concerned with "history-sensitive" error recovery in an IDE: using earlier syntax trees as an additional input to the error recovery process in order to better understand the user's intent when editing. I think this idea makes a lot of sense, but it doesn't address cases like Matklad has prevented here, where the IDE is presented with already-invalid file.

tlb 6y ago

For error recovery, do any parsers have a notion of which tokens are more likely to be wrong? For example, in an actively edited C++ file, braces are more likely correct than angle brackets which are overloaded. So it's reasonable to auto-insert closing > if you see a } with an open <, but not reasonable to insert a } if you see a > with an open <.

ltratt 6y ago
> For error recovery, do any parsers have a notion of which tokens are more likely to be wrong? lrpar has a %avoid_insert declaration which allows users to say "these token types are better avoided if there are other equivalently good repair sequences". It's simple, but it works well https://softdevteam.github.io/grmtools/master/book/errorrecovery.html#biasing-repair-sequences https://softdevteam.github.io/grmtools/master/book/errorreco...
- maxbrunsfeld 6y ago
  I like this solution, and have thought about adding something similar as an "advanced feature" in Tree-sitter grammars. I'm interested to see how you've used it in grammars.
raphlinus 6y ago
To the extent that there will be further research on this problem, I think it will be driven by machine learning. We're already seeing this with autocompletion with TabNine, and no reason a similar approach couldn't work for the other issues facing draft code. If you had a large dataset of keystroke-by-keystroke edit streams, you'd be able to match up erroneous code with the eventual fix. Google or Facebook could absolutely capture these datasets for their internal work if they wanted, and I suspect the results could be scary-good. They wouldn't be able to release the models, though, even for their open source work (Chromium and Android), because it would have such a high chance of revealing internal secrets.
- the_duke 6y ago
  I haven't used it, but Microsoft is already offering machine learning based completions with IntelliCode [1]. See also the introductory blog post. [2] It also offers sharing refined predictions within teams. I think we will see some interesting developments in this domain over the next few years. [1] https://visualstudio.microsoft.com/services/intellicode/ https://visualstudio.microsoft.com/services/intellicode/ [2] https://devblogs.microsoft.com/visualstudio/ai-assisted-intellisense-for-your-teams-codebase/ https://devblogs.microsoft.com/visualstudio/ai-assisted-inte...

raphlinus 6y ago

In the open source world, both Tree-sitter and Lezer are based on GLR, and cite Tim Wagner's thesis. So, while it might be possible to do better even staying in the GLR world, I think the comparison based on Tree-sitter is fair. I think these projects show that GLR is viable (there's a good set of grammars written for Tree-sitter), but I am also very willing to believe that the parser in rust-analyzer is more finely tuned for the specific needs of a Rust IDE.

cwzwarich 6y ago
I was only commenting on his claims about the academic literature on parsing, not whether he should use the techniques verbatim. The problem with structured approaches to incremental parsing is that you rarely want incremental parsing alone. You’re going to want to do something else with the resulting parse tree (name resolution, type checking, compilation, etc.) and no structured approach to incremental parsing will help you there. Once you’re stuck writing an incremental type checker by hand, you probably have the right framework for also writing an incremental parser. Rust has additional complications, e.g. the macro system and the fact that the language is defined by a single implementation.
- raphlinus 6y ago
  I can confirm that Rust's macro system presents massive difficulties. For example, rustfmt is currently broken for subdirectory in Druid because of the use of a `cfg_if!` macro. We filed a bug (https://github.com/rust-lang/rustfmt/issues/4266 https://github.com/rust-lang/rustfmt/issues/4266) but it got closed without (as far as I can tell) actually being fixed. Our present approach is to remove the use of the macro, but this is a bit of a bad sign: two features (macros and automatic formatting) that work fine individually, but their interactions break.
maxbrunsfeld 6y ago
While Tree-sitter is heavily influenced by Wagner's thesis, our error recovery strategy actually uses a novel approach, so it is fair to question whether Wagner's would have different properties. For error recovery, Tree-sitter is currently optimized for some goals that are a bit different from the goals of a single-language IDE like Rust-Analyzer: * Like RA, we want to minimize the impact of syntax errors on basic features like syntax highlighting and symbol name extraction (which are important to GitHub, and in lightweight text editors like Neovim and Atom). * Unlike RA, I wanted to avoid requiring grammar authors to think about error recovery at all. * We needed to tightly control the performance cost of pathological error recovery cases, like parsing a large Ruby file as Go (either accidentally or adversarially). My understanding is that Wagner's thesis is mostly concerned with "history-sensitive" error recovery in an IDE: using earlier syntax trees as an additional input to the error recovery process in order to better understand the user's intent when editing. I think this idea makes a lot of sense, but it doesn't address cases like Matklad has prevented here, where the IDE is presented with already-invalid file.