4 ms·

Dealing with syntax errors in parsers is an interesting subject. To do it really well I think you “just” have to make the error into an AST node similar to the

by db48x 4y ago

Dealing with syntax errors in parsers is an interesting subject. To do it really well I think you “just” have to make the error into an AST node similar to the other nodes in the tree, so that you always have some kind of AST to work with.

dan-robertson 4y ago
The problem is that you want parsing to be tolerant of errors in the sense that a single syntax error doesn’t cascade to incorrect parses far away. “Just” having an error mode means your grammar is very ambiguous and so you want a parser that will stably choose “reasonable” parses, which I think is hard. (But maybe it’s harder in the abstract and easier with heuristics on indentation and suchlike) Though, to be clear, I think you put the word in quotes because you think the problem isn’t trivial.
- db48x 4y ago
  No, it’s not trivial and it does require thinking about your grammar before you decide to lock down your language design. A lot of languages have some pretty obvious synchronization points though, like semicolons and curly braces. If all else fails you can always read up to the next semicolon or curly brace and dump whatever you get into a syntax error node, then keep going. This is especially true if you are implementing an LSP server and so you expect to regularly see incomplete lines simply because the user hasn’t finished typing them in yet. Ultimately what you really want is many different kinds of specialized error (and warning) nodes for different mistakes users might make. For example, in C++ the statement `auto x = 1,000,000;` is technically correct but probably not in the way the user wanted. So you put a warning node there to record that they might want to use `1'000'000` instead. If you see something like `auto x = 42\n if (y) {…`, then you might guess that there is a missing semicolon before the newline. If a speculative parse of the next line succeeds, then you put a MissingSemicolon node into the AST (instead of one saying that the “if” was unexpected), followed by whatever the speculative parse found. Now repeat that process for five years as you polish your compiler into a sparking user–friendly gem.
Wilfred 4y ago
tree-sitter has first class support for parsing errors as ERROR nodes in the output tree. I treat these as just another atom in the s-expression. In practise I haven't noticed any issues yet. I suspect that difftastic doesn't see many syntax errors because users have fixed most of them by the time they run the diff. When you look at diffs of committed code you hopefully have no parse errors at all. The tree-sitter parsers could still reject valid code I suppose. I worry slightly more about the parsers getting precedence/associativity wrong, but it would be hard to construct an example that produce identical parse trees due to incorrect precedence.

by db48x 4y ago

dan-robertson 4y ago

The problem is that you want parsing to be tolerant of errors in the sense that a single syntax error doesn’t cascade to incorrect parses far away. “Just” having an error mode means your grammar is very ambiguous and so you want a parser that will stably choose “reasonable” parses, which I think is hard. (But maybe it’s harder in the abstract and easier with heuristics on indentation and suchlike) Though, to be clear, I think you put the word in quotes because you think the problem isn’t trivial.

db48x 4y ago
No, it’s not trivial and it does require thinking about your grammar before you decide to lock down your language design. A lot of languages have some pretty obvious synchronization points though, like semicolons and curly braces. If all else fails you can always read up to the next semicolon or curly brace and dump whatever you get into a syntax error node, then keep going. This is especially true if you are implementing an LSP server and so you expect to regularly see incomplete lines simply because the user hasn’t finished typing them in yet. Ultimately what you really want is many different kinds of specialized error (and warning) nodes for different mistakes users might make. For example, in C++ the statement `auto x = 1,000,000;` is technically correct but probably not in the way the user wanted. So you put a warning node there to record that they might want to use `1'000'000` instead. If you see something like `auto x = 42\n if (y) {…`, then you might guess that there is a missing semicolon before the newline. If a speculative parse of the next line succeeds, then you put a MissingSemicolon node into the AST (instead of one saying that the “if” was unexpected), followed by whatever the speculative parse found. Now repeat that process for five years as you polish your compiler into a sparking user–friendly gem.

Wilfred 4y ago

tree-sitter has first class support for parsing errors as ERROR nodes in the output tree. I treat these as just another atom in the s-expression. In practise I haven't noticed any issues yet. I suspect that difftastic doesn't see many syntax errors because users have fixed most of them by the time they run the diff. When you look at diffs of committed code you hopefully have no parse errors at all. The tree-sitter parsers could still reject valid code I suppose. I worry slightly more about the parsers getting precedence/associativity wrong, but it would be hard to construct an example that produce identical parse trees due to incorrect precedence.