Note that the post has 'prerequisites' at the beginning, which you will need to read, but they are actually pretty cool.
Also I am not saying this is exactly what you mean, I'm just suggesting it as a possible connection.
This sort of thing is one of the admittedly-rare exceptions where computer science is actually making surprising amounts of progress in relatively practical fields. Parsing has gotten noticeably easier in the past ten years, if you know where to look for the right libraries, and it has been affecting my programming quite a bit. Often, a parser is the "correct" solution, but we used to reach up for hacked up crap with regular expressions or worse because it was ten times easier and did 80% of the job (and ignore the 10% that is a serious security vulnerability since everybody always does). Now it's maybe twice as hard, or, given how easy it is to underestimate the difficulty of getting the hacked up crap to actually work everywhere in the real world you need it to, sometimes it's just flat-out easier if you make a full accounting of costs to actually do it correctly.
Here's a quick summary of the broader implications of that link, because I had trouble wrapping my head around it at first.
Suppose you have the ability to take a chunk of text and construct a partial parse state from it. In the case of regexp matching, these partial parse states are functions mapping one state of the regexp matching automaton to another. You need one more thing: the ability to append two of these partial parse states, combining them into one. In the regexp example, this is just function composition. The key here is that this operation must be associative, and there must be an identity element: some partial parse state such that combining it with another state doesn't change anything. And its result must also be a partial parse state. This combination of parse states and an associative binary operation is called a monoid.
Once you have these conditions fulfilled, you can do all sorts of fun stuff. For instance, you can represent a string as a tree of chunks, and cache partial parse states at the nodes in the tree. That way, when you change the string, you can recompute the changed parse states in something like O(lg n) time, rather than going through and re-parsing the entire string. Or you can almost trivially parallelize your parser.
A week ago, I did exactly this: I had a language that needed parsing, and I wanted to incrementally reparse when I changed the (potentially very long) string, so I used a finger tree and wrote an incremental parser. It works beautifully.
I think it would but regexps are not enough to parse most interesting languages. Perhaps you could extend it to general parsers, but I think it may be impossible to do it efficiently for general context sensitive parsers, because unlike regular expressions the parser can be in infinitely many different states when it arrives at the substring. Perhaps laziness can do some tricks though. Anyone have some ideas?
Did you actually read the linked stuff, or did you just trigger on the keywords "parse" and "regular expression"? I did say it wasn't exactly what was looked for, but it would be interesting to see if someone could extend the results in the linked post from a regular expression to a parse tree. It isn't immediately obvious to me whether you could or could not.
This guy figured out how to turn parsers written with Parsec (an excellent collection of parser combinators; truly a pleasure to use) into monoidal parsers that you can use for incremental and/or parallel parsing.
Comments
You mean something like this?: http://blog.sigfpe.com/2009/01/fast-incremental-regular-expr...
Note that the post has 'prerequisites' at the beginning, which you will need to read, but they are actually pretty cool.
Also I am not saying this is exactly what you mean, I'm just suggesting it as a possible connection.
This sort of thing is one of the admittedly-rare exceptions where computer science is actually making surprising amounts of progress in relatively practical fields. Parsing has gotten noticeably easier in the past ten years, if you know where to look for the right libraries, and it has been affecting my programming quite a bit. Often, a parser is the "correct" solution, but we used to reach up for hacked up crap with regular expressions or worse because it was ten times easier and did 80% of the job (and ignore the 10% that is a serious security vulnerability since everybody always does). Now it's maybe twice as hard, or, given how easy it is to underestimate the difficulty of getting the hacked up crap to actually work everywhere in the real world you need it to, sometimes it's just flat-out easier if you make a full accounting of costs to actually do it correctly.
Here's a quick summary of the broader implications of that link, because I had trouble wrapping my head around it at first.
Suppose you have the ability to take a chunk of text and construct a partial parse state from it. In the case of regexp matching, these partial parse states are functions mapping one state of the regexp matching automaton to another. You need one more thing: the ability to append two of these partial parse states, combining them into one. In the regexp example, this is just function composition. The key here is that this operation must be associative, and there must be an identity element: some partial parse state such that combining it with another state doesn't change anything. And its result must also be a partial parse state. This combination of parse states and an associative binary operation is called a monoid.
Once you have these conditions fulfilled, you can do all sorts of fun stuff. For instance, you can represent a string as a tree of chunks, and cache partial parse states at the nodes in the tree. That way, when you change the string, you can recompute the changed parse states in something like O(lg n) time, rather than going through and re-parsing the entire string. Or you can almost trivially parallelize your parser.
A week ago, I did exactly this: I had a language that needed parsing, and I wanted to incrementally reparse when I changed the (potentially very long) string, so I used a finger tree and wrote an incremental parser. It works beautifully.
Is it me or this would fit quite nicely into an IDE (ie. the language-specific editor) ?
I think it would but regexps are not enough to parse most interesting languages. Perhaps you could extend it to general parsers, but I think it may be impossible to do it efficiently for general context sensitive parsers, because unlike regular expressions the parser can be in infinitely many different states when it arrives at the substring. Perhaps laziness can do some tricks though. Anyone have some ideas?
Cool reference, and I'll be working on that too over the next week or so to see if that's close to what I mean.
Thanks.
regular expressions are always the wrong tool for the job of parsing languages with recursive syntax. See, for instance, http://stackoverflow.com/questions/1732348/regex-match-open-...
Did you actually read the linked stuff, or did you just trigger on the keywords "parse" and "regular expression"? I did say it wasn't exactly what was looked for, but it would be interesting to see if someone could extend the results in the linked post from a regular expression to a parse tree. It isn't immediately obvious to me whether you could or could not.
Yes, it's possible to extend the method in the linked post to parse trees. Check out monoidal parsing:
http://comonad.com/reader/2009/iteratees-parsec-and-monoid/
This guy figured out how to turn parsers written with Parsec (an excellent collection of parser combinators; truly a pleasure to use) into monoidal parsers that you can use for incremental and/or parallel parsing.