3 ms·

I think I read somewhere incremental parsers are better off being written with bottomup parsers rather than topdown parsers. The reason was that when a small ed

by vorg 12y ago

I think I read somewhere incremental parsers are better off being written with bottomup parsers rather than topdown parsers. The reason was that when a small edit is made to the code being parsed, the artifact from a bottomup parser often only needs a minor change that ripples only as far as it needs to, whereas the topdown parser needs to be completely rerun because it can't tell whether the effect of one small edit is large or localized. Anyone out there who can verify or refute this?

seanmcdirmid 12y ago
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.
- vorg 12y ago
  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.
  - seanmcdirmid 12y ago
    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).
    - skybrian 12y ago
      Could you expand on this? What's a memoized token stream?
      - seanmcdirmid 12y ago
        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).
        vorg 12y ago
        > 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!
  - rab_oof 12y ago
    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.

by vorg 12y ago

seanmcdirmid 12y ago

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.

vorg 12y ago
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.
- seanmcdirmid 12y ago
  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).
  - skybrian 12y ago
    Could you expand on this? What's a memoized token stream?
    - seanmcdirmid 12y ago
      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).
      - vorg 12y ago
        > 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!
- rab_oof 12y ago
  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.