Comments on A Neighborhood of Infinity: Beyond Regular Expressions: More Incremental Strin...

Wei Hu, To make this idea work requires that the ...

2009-12-22T10:34:24.853-08:00

Wei Hu,

To make this idea work requires that the internal state of a parser be simple enough. I guess you could roughly characterise it like this: consider the set of possible transitions the parser could make from one state to another as a result of reading n characters. We need this set to grow slowly with n. For finite state machines it remains at finite size. For the example shown in this article it grows roughly as log(n) (the number of bits needed to represent an integer n). But for a LALR parser, say, I think the size of this set grows fast with n, and so it couldn't be implemented reasonably.

So it's good enough for incrementally lexing a language like C++ or Haskell. But not for parsing it.

You showed one particular example beyond regular e...

2009-12-22T00:03:37.001-08:00

You showed one particular example beyond regular expression matching. Will it generalize to any context-free language?

I know this is a bit off subject but I am a gradua...

2009-02-02T23:49:00.000-08:00

I know this is a bit off subject but I am a graduate student at UNLV as well as a weekly math based podcast called Combinations and Permutations where we start with a mathematical topic and spin off onto as many tangents as we can. You can follow the previous link to the blog page of our podcast, search for us on iTunes, or take a trip over to our host site http://cppodcast.libsyn.com. Give us a try I do think that you will enjoy what you hear.

jag,

You're right about the second point. I...

2009-01-31T19:14:00.000-08:00

jag,

You're right about the second point. I wrote the code a few days before the commentary!

jag,

On your first point:

max b c+mi...

2009-01-31T19:13:00.000-08:00

jag,

On your first point:

max b c+min b c = b+c

While I can see that it works, I don't quite see w...

2009-01-31T18:53:00.000-08:00

While I can see that it works, I don't quite see where the max comes from in "B (a-b+max b c) (d-c+max b c)". My attempt at it was "B (a+c-min b c) (b+d-min b c)", basically take the total ')'s and total '('s and subtract the b,c pairs.

Also, I'm a bit confused by "we only need to test whether or not p=q" (which would suggest that ")(" is balanced) but then in the code you test whether both p and q are 0 (which is what I expected the test to be).