4 ms·

I'm the author of the article. I was aware of the research you link to. I enjoyed it, but research is too often focused on the formal side and too little on the

by jng 18y ago

I'm the author of the article. I was aware of the research you link to. I enjoyed it, but research is too often focused on the formal side and too little on the user-experience side. I even mention it succintly in the article (not by name): "I had a look at what was available on incremental parsing, and found a few research initiatives, and even mentions of a few products. But it turns out none of them was focused on the kind of problem I was trying to solve. They were either trying to improve the performance [...] or they were trying to study the formal mathematics of incremental parsing" I mean to include other research initiatives in the above description. Their technique is based in not accepting text edits until they parse properly, a technique which I describe in the article and which I dismissed as a hack and too basic for my goals. My system is more sophisticated and powerful: I actually incorporate partially-wrong stuff into the parse tree! My tool highlights an incomplete 'if' block with the correct if-color, because it knows what it's dealing with! I can also apply heuristics to choose the prefered parsing, which they don't. There's plenty of work pending in incremental parsing, and that thesis just skims the surface (even if the academic-looking presentation may seem like it's going very deep).

wallflower 18y ago
I enjoyed reading your article about parsing. Any thoughts on open sourcing your parsing work? When you mention "lifetimes of research pending to be done in parsing" are you extending the reach of parsing to beyond text - to speech - human conversational analysis, baby acquiring language or maybe even to more abstract communication - like automatically parsing patterns visually.
- jng 18y ago
  Thanks for the kind comment. Nowadays, my products are my source of funding, so no chance to open source anything. In the future, I'm sure some things will make their way into more open forms (not totally sure about what form). Every computation can be seen as an exercise of parsing. The cases you mention, and many other ones. I'm working in a new computation model, a new programming language and a new type of VM. But I don't want to talk much about it until work is more advanced.
  - owinebarger 18y ago
    I found myself thinking I could see the answer as you were describing the problem. That's good writing! My guess would be that you'd need to have a new data structure for the text (or pointing into the straight text) that tracked the order of editing, then a corresponding set of new lexemes and reductions "sitting on top" of the existing parse tree, until the new edits + intervening test/parse tree reduces into something acceptable for the node of the parse tree in which the new text lives. Fun stuff.
    - jng 18y ago
      Thanks for the compliment! Actually, I'd think it's probably due to writing the article "after the fact", rather than to good writing. The proper approach to a problem seems so obvious once you know it...
scottdw2 18y ago
I'd be interested in learning more how you implemented this. I reccomended something similar to this for use as the parser for the VB.NET IDE, back around the start of the VS 2008 development cycle. It ended up being kind of expensive , because it required pushing changes all the way down to the text representation. All the IDE schedule time for Orcas went into supporting the LINQ features, so nobody was really interested in hearing about expensive IDE changes (by the way, I'm not disputing the choice, from a product perspective, it was the right one). I was trying to make the parser faster, and to minimize rebinding of declarations, rather than on improving intermediate states, but I can see how it might be possible to make your stuff work. My idea was based on several things: 1) Incremental tokenization, using a specialized editor text representation 2) Knowledge of the amount of lexical and syntantic lookahead needed by the VB grammar 3) An index from tokens to parse tree nodes When an edit happend, the incremental scanner would then move backwards a constant number of tokens (based on some grammar properties) and then scan forward patching up the token stream until the scanner produced a duplicate token in the appropriate offset position. The parse tree index would then be used to figure out where to restart parsing, again based on some properties of the grammar. My focus was on producing the same trees as the existing parser, and on minimizing changes to declarations (because of all the rebinding that needs to be done), and so my incremental termination condition was based on entering a method (in the top-down hand written parser) that would generate a node of the same type as the "current position"(offset based on the edit), with the same parent, in the existing parse tree with the same starting token (based on object identity). This all worked because the scanner was incremental, which required the editor to structure it's data in a certain way I would imagine that you probably used something similar to this, but with different termination conditions. I would really want to see how similar (or not) what you did was to the scheme I came up with.
- JabavuAdams 18y ago
  I'm kind of working on something similar. One thing that struck me about C++ is that although template parsing, etc, is pretty hard, you can get a long way by segmenting the source into delimited regions. This might also speed up your semantic analysis, by allowing you to write code that's operating on a known kind of region. For instance after pre-processing, it should be easy to find nested "{", "[", "(", "\"", "'", and "<". Segmenting the source in this way, first, might make further processing easier. It seems that the standard parsing methods we learn in CS are optimized for single-pass speed, but not for maintainability or development efficiency. Computers have gotten fast. Using multiple passes of simpler operators seems like a good promising approach. I see the process of parsing as some kind of folding, where you start with a linear sequence of chars and gradually fold it over and over into a "lumpy" tree.

by jng 18y ago

wallflower 18y ago

I enjoyed reading your article about parsing. Any thoughts on open sourcing your parsing work? When you mention "lifetimes of research pending to be done in parsing" are you extending the reach of parsing to beyond text - to speech - human conversational analysis, baby acquiring language or maybe even to more abstract communication - like automatically parsing patterns visually.

jng 18y ago
Thanks for the kind comment. Nowadays, my products are my source of funding, so no chance to open source anything. In the future, I'm sure some things will make their way into more open forms (not totally sure about what form). Every computation can be seen as an exercise of parsing. The cases you mention, and many other ones. I'm working in a new computation model, a new programming language and a new type of VM. But I don't want to talk much about it until work is more advanced.
- owinebarger 18y ago
  I found myself thinking I could see the answer as you were describing the problem. That's good writing! My guess would be that you'd need to have a new data structure for the text (or pointing into the straight text) that tracked the order of editing, then a corresponding set of new lexemes and reductions "sitting on top" of the existing parse tree, until the new edits + intervening test/parse tree reduces into something acceptable for the node of the parse tree in which the new text lives. Fun stuff.
  - jng 18y ago
    Thanks for the compliment! Actually, I'd think it's probably due to writing the article "after the fact", rather than to good writing. The proper approach to a problem seems so obvious once you know it...

scottdw2 18y ago

I'd be interested in learning more how you implemented this. I reccomended something similar to this for use as the parser for the VB.NET IDE, back around the start of the VS 2008 development cycle. It ended up being kind of expensive , because it required pushing changes all the way down to the text representation. All the IDE schedule time for Orcas went into supporting the LINQ features, so nobody was really interested in hearing about expensive IDE changes (by the way, I'm not disputing the choice, from a product perspective, it was the right one). I was trying to make the parser faster, and to minimize rebinding of declarations, rather than on improving intermediate states, but I can see how it might be possible to make your stuff work. My idea was based on several things: 1) Incremental tokenization, using a specialized editor text representation 2) Knowledge of the amount of lexical and syntantic lookahead needed by the VB grammar 3) An index from tokens to parse tree nodes When an edit happend, the incremental scanner would then move backwards a constant number of tokens (based on some grammar properties) and then scan forward patching up the token stream until the scanner produced a duplicate token in the appropriate offset position. The parse tree index would then be used to figure out where to restart parsing, again based on some properties of the grammar. My focus was on producing the same trees as the existing parser, and on minimizing changes to declarations (because of all the rebinding that needs to be done), and so my incremental termination condition was based on entering a method (in the top-down hand written parser) that would generate a node of the same type as the "current position"(offset based on the edit), with the same parent, in the existing parse tree with the same starting token (based on object identity). This all worked because the scanner was incremental, which required the editor to structure it's data in a certain way I would imagine that you probably used something similar to this, but with different termination conditions. I would really want to see how similar (or not) what you did was to the scheme I came up with.

JabavuAdams 18y ago
I'm kind of working on something similar. One thing that struck me about C++ is that although template parsing, etc, is pretty hard, you can get a long way by segmenting the source into delimited regions. This might also speed up your semantic analysis, by allowing you to write code that's operating on a known kind of region. For instance after pre-processing, it should be easy to find nested "{", "[", "(", "\"", "'", and "<". Segmenting the source in this way, first, might make further processing easier. It seems that the standard parsing methods we learn in CS are optimized for single-pass speed, but not for maintainability or development efficiency. Computers have gotten fast. Using multiple passes of simpler operators seems like a good promising approach. I see the process of parsing as some kind of folding, where you start with a linear sequence of chars and gradually fold it over and over into a "lumpy" tree.