4 ms·

Fascinating. I don't understand it all yet - I'm reading it carefully but it'll be weeks before I really get it. However ... I'm getting the feeling that thi

Fascinating. I don't understand it all yet - I'm reading it carefully but it'll be weeks before I really get it. However ... I'm getting the feeling that this encompasses properly a feeling I've had about parsing for some time, that there should be a way of parsing the entire text, with the parse settling onto the text all at the same time. I don't know if this is what it's saying, but that's the sense I get from it. But even if it isn't, it looks intriguing.

jerf 16y ago
You mean something like this?: http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html 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.
- RiderOfGiraffes 16y ago
  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.
- StrawberryFrog 16y ago
  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-tags-except-xhtml-self-contained-tags/1732454#1732454 http://stackoverflow.com/questions/1732348/regex-match-open-...
  - jerf 16y ago
    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.
    - pjscott 16y ago
      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/ 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.
- pjscott 16y ago
  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.
  - fierarul 16y ago
    Is it me or this would fit quite nicely into an IDE (ie. the language-specific editor) ?
    - jules 16y ago
      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?

jerf 16y ago

You mean something like this?: http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html 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.

RiderOfGiraffes 16y ago
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.
StrawberryFrog 16y ago
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-tags-except-xhtml-self-contained-tags/1732454#1732454 http://stackoverflow.com/questions/1732348/regex-match-open-...
- jerf 16y ago
  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.
  - pjscott 16y ago
    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/ 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.
pjscott 16y ago
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.
- fierarul 16y ago
  Is it me or this would fit quite nicely into an IDE (ie. the language-specific editor) ?
  - jules 16y ago
    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?