5 ms·
Error recovery with parser combinators, using Rust and nom
- ezekiel68 6y agoAnd best of all, the final parsers are much shorter, easier to reason about, and are more directly analogous to their PEG equivalents... I enjoyed the author's style, which made me feel as if I were following along with him on the journey of discovery. This quote, in particular, was delightful -- it revealed a scholar willing to let go of attachment to his preferred solution in exchange for something pragmatic which was "close enough". A lesson I take to heart.
- thechao 6y agoNaively implemented directly-executed parser-combinators aren't any more powerful than recursive-descent. One thing I find interesting is that most discussions of recursive-descent don't actually show the algorithm. Let a grammar be a list of rules; let a rule be a list of prods (alternates); let a prod be a list of terms (references to rules, or terminals). Then, the recursive-descent algorithm is something along the lines of: def Parse(G, U): ''' G: the grammar; U: the user's state. ''' r = G.StartRule() return ParseRule(G, U, r) def ParseRule(G, U, r): potentials = [ ] for p in r: q = ParseProd(G, U, p) if q.success: potentials.append(q) return U.pickBest(potentials) def ParseProd(G, U, p): res = [ ] U.markTokens() for t in p: if t.isTerminal(): T = U.getToken() if t != T: return (False, [ ]) res.append(T) else: q = ParseRule(G, U, G.GetRule(t)) if not q[0]: return (False, [ ]) res.append(q[1]) U.commitTokens() return (True, res) I'm 100% sure this code leaves a lot off the table, but a reasonably complete recursive-descent algorithm is very close to this. I use the operator-overloading thing a lot of parser-combinators design as a way to specify the grammar in the native code, without going through a stringy-API.
- ookdatnog 6y ago> Naively implemented directly-executed parser-combinators aren't any more powerful than recursive-descent. Parser combinators are recursive descent, as in, they are just a neat way to write down a recursive descent parser using a compositional style. The reason they're popular is because they compose well and feel more declarative than traditional recursive descent.
- thechao 6y agoNaively implemented directly-executed parser-combinators are recursive-descent. More sophisticated parser-combinators are usually lowered to PEGs, GLRs, or PEPs.
- MaxBarraclough 6y ago'PEP'?
- thechao 6y agoPractical Earley Parsers. If you memoize the algorithm I presented you get the Earley parser; if you convert the itemsets of an Earley parser into tables you get a PEP. PEPs are as fast as other LL/LR/LALR table parsers, but also accept all CFGs. They’ve lost the “mental space war” to YACCen, PEGs, and parsecs.
- deleted 6y ago[deleted]
- mlazos 6y agoI’m curious at how it a actually possible to have partial autocompletion and still have some static analysis tools work with syntax errors in badly formed ASTs. Even visual studio, an IDE with massive resources behind it can’t accomplish this with c++. Is this even possible? At face value it seems possible but I’m surprised that more IDEs don’t have this support.