How Desmos uses Pratt Parsers

engineering.desmos.com

51 points·jwmerrill··6 comments

"In computer science, a Pratt parser is an improved recursive descent parser that associates semantics with tokens instead of grammar rules." (Wikipedia)

Skip over the large introduction to what parsing is and the reasons for switching are listed: Avoid the parser generator special syntax and compilation, better error messages, have the parser in the same language as the rest of their code, avoid having two grammar definitions (another for CodeMirror), faster and smaller JS bundle than generated code.

Actually, having two parsers doesn't seem like a bad thing; it means that you can test one trivial property on arbitrary, randomized input: That they produce the same output!

Shameless plug: Single-file Java Pratt expression parser library: https://github.com/stefanhaustein/expressionparser

One of the disadvantages they list is that recursive-descent parsers are harder to read than e.g. DSLs.

So the best of both worlds, it sounds to me, would be parser combinators: They're both native to the language, and they're DSLs. So there's only one set of syntax for the programmer, and they still compose declaratively as opposed to writing recursive parsers manually.

Or maybe a Pratt parser dsl?

What I think is how provide a common parser layer yet allow to get the same benefits of a hand-made one. For some reason, this look like is impossible?

Personally, while I do find DSLs easier to read, I find writing them harder than recursive descent. The problem is that a DSL will still have theoretical limitations (ie shift shift or shift reduce errors, left recursion, performance). In order to deal with these limitations you still have to know how everything works under the hood.

With recursive descent, you can always start adding break points until you understand the forces involved.

Reply on news.ycombinator.com