6 ms·

I have a somewhat controversial opinion on this. This paper, like some others that I've seen, treats parsing as an academic/algorithmic topic. Given some token

I have a somewhat controversial opinion on this. This paper, like some others that I've seen, treats parsing as an academic/algorithmic topic. Given some token stream we'd like to minimize some error criteria. However, these papers ignore the fact that people don't write token streams: they write code that is formatted using whitespace. I don't know any programmer that writes their source code on a single line. On the contrary, pretty much every programmer formats their source code to some reasonable (if not complete) degree. In other words: parsing error recovery is not primarly an algorithmic problem: it's a usability problem. Newlines and indentation are a source of extra information that we can use to infer what the programmer meant. Why throw all that away during tokenization? That's crazy! We can totally use it for error recovery/error message generation. I decided to play around with this idea in the design my programming language Muon [1]. The language uses redundant significant whitespace for parser error recovery. This simple approach by itself has turned out to work surprisingly well! In my admittedly biased opinion, it frequently surpasses the error recovery quality in mature compilers such as the C# compiler, which has had tons of effort poured into error recovery. Of course, a purely whitespace based recovery scheme is not perfect: there are rough edges, like having to deal with tabs vs spaces, and recovering inside a line is not usually possible. But the fact that such a simple approach has led to good results makes me think this would be a great area for future research, that can perhaps combine the best of both worlds here. [1] https://github.com/nickmqb/muon https://github.com/nickmqb/muon

thechao 6y ago
Pseudo-regular parsing combined with hand-written pratt-parsers is a nice sweet-spot: easy to read, very robust, and produce great error messages. The technique was, I am told, moderately popular in the 80s and 90s. (My familiarity with them comes from a language called Spad.)
estebank 6y ago
I think you hit the nail right in the head, but I would say that whitespace is only one source of signal. Lately I've become convinced that languages need redundancy in their grammar to help with error recovery. Having a more flexible syntax actually hurts usability because valid but semantically incorrect code can't be caught early enough and makes it much harder to give friendly errors. rustc uses whitespace for error recovery in several places, although the most prevalent is checking whether two different elements are on different lines, like when detecting a `:` when a statement ending `;` was actually meant[1]. [1]: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d5dd5baca37797bf8be381e45ced1ce9 https://play.rust-lang.org/?version=stable&mode=debug&editio...
- pjungwir 6y ago
  > languages need redundancy in their grammar IMO extra redundancy makes Greek much easier to read than Latin. The upfront learning is a bit more effort, but then reading it is much easier. Unlike Latin it has articles (which are declined and agree with the nouns/adjectives), and the endings on verbs & nouns have way less ambiguity. I can certainly see how the same would apply to programming languages.
- Gibbon1 6y ago
  Somewhat related is my belief that text based languages have long since outlived their usefulness. With text based languages the compiler creates an abstract syntax tree and a bunch of metadata and then throws it all away afterwords. Oh sure you can save an object file if and ONLY if it didn't change and it's cached locally. A perfect system if you edit a file and save it 90% of the compilers work would already done and saved as part of the file format. Topical is the parser would usually have access to the previously unbroken file.
  - estebank 6y ago
    In my experience parsing is pretty robust and fast already, to the point where optimizing that stage of the compiler isn't worth it. Regarding the discrepancy between the AST and the source code, I think that it is worth noting that although there's a relationship between the syntax and the semantics, there need not be a 1:1 mapping between these, both allowing different features look similar (because they are pedagogically similar, like in impl Trait in Rust in argument position and return position) or dissimilar. I could see leveraging ASTs for more accurate diffing algorithms and fancy tools, but none of these would require that the AST be the source of truth.
    - Gibbon1 6y ago
      If you have ABI stability you don't need to do any of that stuff either to code that hasn't changed. The fastest way to compile code is to not constantly recompile it from scratch.
  - qppo 6y ago
dan-robertson 6y ago
I sort-of do write source code in one long line: I use an autoformatter so when I want to insert something, I usually just write it in one long line and hit save. If I have a syntax error the line won’t get formatted and then I have to stare at it. That said, I think whitespace-based error recovery is a good idea and would probably still help in my case.
chmaynard 6y ago
Tip: Don't ask visitors to your repo to follow you on Twitter. Some of us don't use Twitter and find this advice rather annoying. Start a blog or something.
cwzwarich 6y ago
An even bigger flaw with most academic research into parser error recovery is that the vast majority of syntax errors occur from modifying a valid program to produce an invalid program, but the recovery algorithms are oblivious to this.
- tux1968 6y ago
  Which suggests that parsing should be done while editing, supporting many other refactoring tools as well. The key feature enabling this facility is incremental parsing.
- estebank 6y ago
  Approaching this from the opposite side, language designers should also take into account how code with slight mistakes (typos and confused use of features) could be detected. Sometimes adding small things to the grammar can pay a lot of dividends when writing the production ready compiler. Alternatively when adding a new feature they should be thinking "what common mistakes will be made to produce worse errors if we introduce this with this syntax".
  - zffr 6y ago
    I think in some cases they do. Python3’s parser can detect when people use the old print syntax for example.
- ComputerGuru 6y ago
  Have a look at this writeup by the author of lezer, if you haven't already: https://marijnhaverbeke.nl/blog/lezer.html https://marijnhaverbeke.nl/blog/lezer.html
  - ltratt 6y ago
    tree-sitter is excellent stuff! It's heavily inspired by Tim Wagner's PhD thesis (original site seems to be down, but https://web.archive.org/web/20150919164029/https://www.cs.berkeley.edu/Research/Projects/harmonia/papers/twagner-thesis.pdf https://web.archive.org/web/20150919164029/https://www.cs.be... works). IMHO more people should know about that work, and the sequence of work from Susan Graham's lab that led up to it. We have also been heavily inspired by Tim's work and Lukas's thesis extends and updates a number of aspects of that seminal work including, in Chapter 3, error recovery (https://diekmann.co.uk/diekmann_phd.pdf https://diekmann.co.uk/diekmann_phd.pdf). All that said, it's surprisingly difficult to compare error recovery in an online parser (i.e. one that's parsing as you type) to a batch parser. In the worst case (e.g. load a file with a syntax error in), online parsers have exactly the same problems as a batch parser; however, once they've built up sufficient context they have different, sometimes more powerful, options available to them (but they also need to be cautious about rewriting the tree too much as that baffles users).
m463 6y ago
> Newlines and indentation are a source of extra information that we can use to infer what the programmer meant. in the case of python, this is part of the language. :)
daemin 6y ago
It works as long as people actually care about the formatting of their code. I've seen far too many cases where people just don't care or care about the wrong things when it comes to formatting. Like they copy/cut & paste some code and now the indentation is off by a space or a tab, but they don't care. There's also the space vs tabs rabbit hole.
- littlestymaar 6y ago
  > There's also the space vs tabs rabbit hole. This one is easily fixable: just emit a parse error if you encounter a space used as an indentation character…
deleted 6y ago
[deleted]
poidos 6y ago
Hey Nick, Project looks great! I see on your README you're working on an LLVM backend. I'm doing the same for an unrelated language, would love to contribute to Muon if you're looking for extra hands.

thechao 6y ago

Pseudo-regular parsing combined with hand-written pratt-parsers is a nice sweet-spot: easy to read, very robust, and produce great error messages. The technique was, I am told, moderately popular in the 80s and 90s. (My familiarity with them comes from a language called Spad.)

estebank 6y ago

I think you hit the nail right in the head, but I would say that whitespace is only one source of signal. Lately I've become convinced that languages need redundancy in their grammar to help with error recovery. Having a more flexible syntax actually hurts usability because valid but semantically incorrect code can't be caught early enough and makes it much harder to give friendly errors. rustc uses whitespace for error recovery in several places, although the most prevalent is checking whether two different elements are on different lines, like when detecting a `:` when a statement ending `;` was actually meant[1]. [1]: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d5dd5baca37797bf8be381e45ced1ce9 https://play.rust-lang.org/?version=stable&mode=debug&editio...

pjungwir 6y ago
> languages need redundancy in their grammar IMO extra redundancy makes Greek much easier to read than Latin. The upfront learning is a bit more effort, but then reading it is much easier. Unlike Latin it has articles (which are declined and agree with the nouns/adjectives), and the endings on verbs & nouns have way less ambiguity. I can certainly see how the same would apply to programming languages.
Gibbon1 6y ago
Somewhat related is my belief that text based languages have long since outlived their usefulness. With text based languages the compiler creates an abstract syntax tree and a bunch of metadata and then throws it all away afterwords. Oh sure you can save an object file if and ONLY if it didn't change and it's cached locally. A perfect system if you edit a file and save it 90% of the compilers work would already done and saved as part of the file format. Topical is the parser would usually have access to the previously unbroken file.
- estebank 6y ago
  In my experience parsing is pretty robust and fast already, to the point where optimizing that stage of the compiler isn't worth it. Regarding the discrepancy between the AST and the source code, I think that it is worth noting that although there's a relationship between the syntax and the semantics, there need not be a 1:1 mapping between these, both allowing different features look similar (because they are pedagogically similar, like in impl Trait in Rust in argument position and return position) or dissimilar. I could see leveraging ASTs for more accurate diffing algorithms and fancy tools, but none of these would require that the AST be the source of truth.
  - Gibbon1 6y ago
    If you have ABI stability you don't need to do any of that stuff either to code that hasn't changed. The fastest way to compile code is to not constantly recompile it from scratch.
- qppo 6y ago

dan-robertson 6y ago

I sort-of do write source code in one long line: I use an autoformatter so when I want to insert something, I usually just write it in one long line and hit save. If I have a syntax error the line won’t get formatted and then I have to stare at it. That said, I think whitespace-based error recovery is a good idea and would probably still help in my case.

chmaynard 6y ago

Tip: Don't ask visitors to your repo to follow you on Twitter. Some of us don't use Twitter and find this advice rather annoying. Start a blog or something.

cwzwarich 6y ago

An even bigger flaw with most academic research into parser error recovery is that the vast majority of syntax errors occur from modifying a valid program to produce an invalid program, but the recovery algorithms are oblivious to this.

tux1968 6y ago
Which suggests that parsing should be done while editing, supporting many other refactoring tools as well. The key feature enabling this facility is incremental parsing.
estebank 6y ago
Approaching this from the opposite side, language designers should also take into account how code with slight mistakes (typos and confused use of features) could be detected. Sometimes adding small things to the grammar can pay a lot of dividends when writing the production ready compiler. Alternatively when adding a new feature they should be thinking "what common mistakes will be made to produce worse errors if we introduce this with this syntax".
- zffr 6y ago
  I think in some cases they do. Python3’s parser can detect when people use the old print syntax for example.
ComputerGuru 6y ago
Have a look at this writeup by the author of lezer, if you haven't already: https://marijnhaverbeke.nl/blog/lezer.html https://marijnhaverbeke.nl/blog/lezer.html
- ltratt 6y ago
  tree-sitter is excellent stuff! It's heavily inspired by Tim Wagner's PhD thesis (original site seems to be down, but https://web.archive.org/web/20150919164029/https://www.cs.berkeley.edu/Research/Projects/harmonia/papers/twagner-thesis.pdf https://web.archive.org/web/20150919164029/https://www.cs.be... works). IMHO more people should know about that work, and the sequence of work from Susan Graham's lab that led up to it. We have also been heavily inspired by Tim's work and Lukas's thesis extends and updates a number of aspects of that seminal work including, in Chapter 3, error recovery (https://diekmann.co.uk/diekmann_phd.pdf https://diekmann.co.uk/diekmann_phd.pdf). All that said, it's surprisingly difficult to compare error recovery in an online parser (i.e. one that's parsing as you type) to a batch parser. In the worst case (e.g. load a file with a syntax error in), online parsers have exactly the same problems as a batch parser; however, once they've built up sufficient context they have different, sometimes more powerful, options available to them (but they also need to be cautious about rewriting the tree too much as that baffles users).

m463 6y ago

> Newlines and indentation are a source of extra information that we can use to infer what the programmer meant. in the case of python, this is part of the language. :)

daemin 6y ago

It works as long as people actually care about the formatting of their code. I've seen far too many cases where people just don't care or care about the wrong things when it comes to formatting. Like they copy/cut & paste some code and now the indentation is off by a space or a tab, but they don't care. There's also the space vs tabs rabbit hole.

littlestymaar 6y ago
> There's also the space vs tabs rabbit hole. This one is easily fixable: just emit a parse error if you encounter a space used as an indentation character…

deleted 6y ago

[deleted]

poidos 6y ago

Hey Nick, Project looks great! I see on your README you're working on an LLVM backend. I'm doing the same for an unrelated language, would love to contribute to Muon if you're looking for extra hands.