4 ms·
I get the quest for more elegant and powerful parsing techniques, but it seems that some very interesting real-world problems - mostly arising in code editors -
by xiaq 8y ago
I get the quest for more elegant and powerful parsing techniques, but it seems that some very interesting real-world problems - mostly arising in code editors - don't get enough academic love:
* Fast re-parsing when part of the input changes;
* Parsing of incomplete input, and enumerating possible ways to continue the input.
These can be very useful for code editors, for syntax highlighting and code completion. Some editors work around this by using a more restricted lexical syntax and avoiding to build a complete parse tree (Vim); newer editors - JetBrain and VS Code AFAIK - do have some pretty good techniques, but they don't seem to get a lot of academic treatise.
- danharaj 8y agoYou might like this page: http://okmij.org/ftp/continuations/differentiating-parsers.html http://okmij.org/ftp/continuations/differentiating-parsers.h...
- catpolice 8y agoFast re-parsing is tricky. I'm building a JS IDE for a simple language, and it needs to only re-parse the part of the syntax tree that an edit affects (and only update the minimal number of affected DOM nodes). Writing the (recursive descent) lexer/parser by hand was easy. Being able to stream text diffs to the lexer/parser and have it rebuild only the appropriate part of the AST took... a bit of work. Writing unit tests might kill me.
- xiaq 8y agoI cannot find the link now, but I remember reading a recent article saying that what VSCode does is basically storing some context information for each line. When input changes, the line is reparsed, and then the context provides enough information on how to modify the parse tree.
- catpolice 8y agoYeah, that's pretty similar to what I ended up doing - it comes pretty natural with recursive descent to just store enough of the parser state on relevant nodes that you can restart it at natural breaks. For my application, I end up having to make expensive async queries about the expressions the user writes. In order to minimize server load/make things responsive/avoid invalidating perfectly good caches, this means that I have to know exactly what to keep and what to throw out with each edit, which means that I never want to replace any node in the AST with an identical one that was needlessly re-parsed if I can help it. So my lexer does a lot of work trying not to throw out parts of lines that the user hasn't touched, and the parser can figure out what changes are relevant to invalidate my caches. Oddly the restartable lexer has turned out to be the most frustrating part - selectively diffing parts of two doubly linked lists and snipping them together in the way I ended up having to is one of those things that isn't conceptually very difficult but has the potential for unusually subtle bugs.
- blake8086 8y agoYou will probably be interested in this explanation of how xi-editor does it: https://google.github.io/xi-editor/docs/rope_science_11.html https://google.github.io/xi-editor/docs/rope_science_11.html
- xiaq 8y agoThanks! The entire site is very interesting.
- nly 8y agoI feel you are right. Most AOT parsing jobs (compiled languages etc.) are well-solved by straightforward, 'inefficient' recursive descent. Untrusted inputs with complex grammars or realtime parsing like the IDE use-case are vastly more interesting.
- chubot 8y agoThis feels like it's fairly far removed from practice, but this talk addresses reparsing in an algebraic fashion: Monoidal Parsing - Ed Kmett https://www.youtube.com/watch?v=Txf7swrcLYs https://www.youtube.com/watch?v=Txf7swrcLYs
- Promarged 8y agoI think these issues were directly tackled on by Roslyn team, that wanted something more than just compiler black box (text goes in, machine code goes out). There are some interesting videos on Channel9 about Roslyn internals (sorry no access now ).