5 ms·

Pratt or TDOP parsers are my favorite design when coding the parser directly in a host language, with parser combinators a close second (but it edges ahead depe

Pratt or TDOP parsers are my favorite design when coding the parser directly in a host language, with parser combinators a close second (but it edges ahead depending on the host language). But when it comes to writing a larger parser with many production rules, I'd rather use a parser generator based around an Earley parser. You can split production rules and organize their post-processing into an AST a lot easier .. but providing good error statements is still a bit of a hassle. I haven't found a parser generator that makes it painless to provide good error messages. Writing the parser directly in the host language has always been much easier in that regard.

nickpsecurity 3y ago
sklogic told us here that his strategy was to use two parsers: a fast, generated one by default; a separate one for good, error handling. If using that strategy, then we might be able to build some error handling in as part of the grammar. The generator ignores it for one engine and uses it for another.
- kevindamm 3y ago
  That's good advice.. it's especially useful in an Earley design because it is much faster when it doesn't have to keep explicit back references for derivation, but those references are needed for explaining the current context. Adding a switch for keeping/discarding history (and a compiler pass for whether or not to fold the epsilon-DFA into collapsed states, "NNF" style) would automate the fast-vs-slow|informative variants. Add in some debug-only output in postprocessors and it wouldn't really need any syntactical changes to the parser generator. I may try this soon..
danybittel 3y ago
I've been working on a parser that parses while typing and gives type and syntax errors as soon as possible but never any false positives. I didn't expect it to be that difficult. I still haven't really grokked it and any bugfix usually ends in a game of whack a mole over integration tests. Any hints?
- ReleaseCandidat 3y ago
  It depends on the language you're parsing, of course. But the most important thing is to know when your parser is on the right track again. The (most of the time) easiest (but not necessarily first possible) such point is the next definition statement. And make sure to _always_ consume (at least) one token (even if just adding it to the error expression in the AST), so there is no possibility of an endless loop.
- ivanjermakov 3y ago
  I can recommend this article: https://matklad.github.io/2023/05/21/resilient-ll-parsing-tutorial.html https://matklad.github.io/2023/05/21/resilient-ll-parsing-tu...
- orthoxerox 3y ago
  Roslyn (C# compiler) has been designed to quickly parse invalid code while still providing intellisense.
- ww520 3y ago
  One way I found helpful in giving precise parsing errors without causing excessive false errors is to have the parser auto-completing the missing tokens with placeholder error nodes. E.g. if (cond1 And ) { ... } The And operator is missing its right operand, but everything else is valid. The parser knows the And operator needs two arms. It can complete the missing arm with an error node. fn parseCondition() { let leftNode = parseBoolExpr() if (lookaheadToken() is And) return parseAnd(leftNode) if (lookaheadToken() is Or) ... return leftNode } fn parseAnd(leftNode) { consumeToken() let rightNode = parseBoolExpr() if (rightNode != null) return AndNode(leftNode, rightNode) else return AndNode(leftNode, ErrorNode("missing operand", location)) } In this way, the conditional expression is parsed to completion without interruption. Multiple errors can be handled with completion and recorded. At the end it's a matter of traversing the AST to print out all the ErrorNodes.
  - danybittel 3y ago
ReleaseCandidat 3y ago
> I haven't found a parser generator that makes it painless to provide good error messages. This. And letting the user add their own infix function with configurable precedence and associativity is easy using Pratt too.

nickpsecurity 3y ago

sklogic told us here that his strategy was to use two parsers: a fast, generated one by default; a separate one for good, error handling. If using that strategy, then we might be able to build some error handling in as part of the grammar. The generator ignores it for one engine and uses it for another.

kevindamm 3y ago
That's good advice.. it's especially useful in an Earley design because it is much faster when it doesn't have to keep explicit back references for derivation, but those references are needed for explaining the current context. Adding a switch for keeping/discarding history (and a compiler pass for whether or not to fold the epsilon-DFA into collapsed states, "NNF" style) would automate the fast-vs-slow|informative variants. Add in some debug-only output in postprocessors and it wouldn't really need any syntactical changes to the parser generator. I may try this soon..

danybittel 3y ago

I've been working on a parser that parses while typing and gives type and syntax errors as soon as possible but never any false positives. I didn't expect it to be that difficult. I still haven't really grokked it and any bugfix usually ends in a game of whack a mole over integration tests. Any hints?

ReleaseCandidat 3y ago
It depends on the language you're parsing, of course. But the most important thing is to know when your parser is on the right track again. The (most of the time) easiest (but not necessarily first possible) such point is the next definition statement. And make sure to _always_ consume (at least) one token (even if just adding it to the error expression in the AST), so there is no possibility of an endless loop.
ivanjermakov 3y ago
I can recommend this article: https://matklad.github.io/2023/05/21/resilient-ll-parsing-tutorial.html https://matklad.github.io/2023/05/21/resilient-ll-parsing-tu...
orthoxerox 3y ago
Roslyn (C# compiler) has been designed to quickly parse invalid code while still providing intellisense.
ww520 3y ago
One way I found helpful in giving precise parsing errors without causing excessive false errors is to have the parser auto-completing the missing tokens with placeholder error nodes. E.g. if (cond1 And ) { ... } The And operator is missing its right operand, but everything else is valid. The parser knows the And operator needs two arms. It can complete the missing arm with an error node. fn parseCondition() { let leftNode = parseBoolExpr() if (lookaheadToken() is And) return parseAnd(leftNode) if (lookaheadToken() is Or) ... return leftNode } fn parseAnd(leftNode) { consumeToken() let rightNode = parseBoolExpr() if (rightNode != null) return AndNode(leftNode, rightNode) else return AndNode(leftNode, ErrorNode("missing operand", location)) } In this way, the conditional expression is parsed to completion without interruption. Multiple errors can be handled with completion and recorded. At the end it's a matter of traversing the AST to print out all the ErrorNodes.
- danybittel 3y ago

ReleaseCandidat 3y ago

> I haven't found a parser generator that makes it painless to provide good error messages. This. And letting the user add their own infix function with configurable precedence and associativity is easy using Pratt too.