Hacker News Reader

Comment by seanmcdirmid | Hacker News Reader

I've written parsers both as top down and bottom up. Nite that neither is naturally incremental and some memoization is required, so for bottom up, you see if the parent you want to create already exists, for top down, your child. It is sort of a wash which one is better, but both are pretty trivial.

I use top down recursive descent these days backed up with memoization. When a change to the token stream comes, you simply damage the most inner tree that contains the token, or if on a boundary, damage multiple trees.

View on HN

Thanks. I've been writing and using recursive descent parsers a little lately, both Parsec-style and Packrat-style. If it's possible to do decent incremental parsing without wrapping my head around LR-parsing, then I'll give it a try sometime.

It is actually quite easy if you have a memoized token stream to work on. Just store your trees based on their first token. When you do a parse, check to see if a tree of that type already exists for that token. If it does, just reuse it, and if there is any context to consider, dirty the tree if the context of its creation has changed.

There are more advanced incremental parsing algorithms that do not require memoization, but they really aren't worth it (the ability to parse incrementally is not really a performance concern, but in keeping around state associated with the tree and in doing better error recovery).

Could you expand on this? What's a memoized token stream?

A token stream that preserves token identities. Say you have a token stream of [t0, t1] and add a new token t2 between t0 and t1 to get [t0, t2, t1]. What you want is to be able to identify t0 and t1 in the new stream as being the same tokens as in the old stream. If you simply re-lex to get new tokens, that won't happen, and if you use character offsets as your token identities, t1 in the new and old stream will have different identities.

Incremental lexing is pretty easy: just convert the tokens around the damage back into text, re-lex that text, and then work from front and back of the new partial stream to replace new tokens with old existing tokens if their lexical categories match (e.g. an old identifier's text can be updated with a new identifier's contents, but that is ok because parsing only depends on the fact that the token is an identifier). You might not win any performance awards, but those reused old tokens make very good keys into various data structures for incremental parsing, incremental type checking, and even incremental re-execution (if you are into live programming).

> convert the tokens around the damage back into text, re-lex that text, and then work from front and back of the new partial stream

I haven't tried it and I'm no parsing expert but it seems when a rule is specified "forwards" (i.e. beginning-to-end) then it can be used for lexing (or parsing) forwards but there'd be problems using it to lex (or parse) backwards. Hence the first "L" in "LL" and "LR" parsing.

Maybe an algorithm could use both directions running in parallel and create 2 structures/memoizations, one for the forward parse and one for the backward, hence a dual LL/RL or LR/RR parse, and access both structures to repair "damage". However, there could be another problem: if the lookahead for some lex or parse rule is 1, couldn't that translate to any lookbehind value when lexing or parsing backwards? An LL(1) grammar might require an equivalent RL(k) grammar for some very high k. Of course you'd also need to avoid right recursion as well as left recursion for topdown parsing.

I haven't tried any of this but these are the things that cross my mind whenever I think of incremental parsing!

Thanks. To figure out what's damaged, it seems like you have to do a diff somewhere? It sounds like this is done at the character level rather than the token level?

No diff, just do the re-lex and damage the tree on the boundaries of where the user typed. My techniques (also, see glitch) usually just assume change has happened since the reprocessing is incremental anyways and won't cascade if nothing has really changed (when reprocessing a tree, the parent is damaged if the end token changed, I guess you could call that a diff).

The subset LALR(1) is pretty simple. Table with states that can shift or reduce, and finally accept or error. It's not too hard to get the dragon book and write an LALR(1) parser for a calculator by hand. Plenty of lectures out there that explain it. If I can write a lexer/parser from scratch after hearing the explanation of LALR(1), anyone can.

LR(k) would be more complicated. Start with the smaller CFG subset and work up to it.

Reply on news.ycombinator.com