3 ms·

Regular expression parser and compiler for a VM regex implementation similar to the one described in [1]. Part of a larger project, and the VM doesn't actually

Regular expression parser and compiler for a VM regex implementation similar to the one described in [1]. Part of a larger project, and the VM doesn't actually operate on a normal string data structure. [1] http://swtch.com/~rsc/regexp/regexp2.html http://swtch.com/~rsc/regexp/regexp2.html

stevejohnson 17y ago
Update: The parser is generating a correct AST. I mean, not that anyone really cares, but I am getting some work done, which is nice.
- sunir 17y ago
  Hey, sweet. High five! Now I'm very curious. What kind of underlying string representation does your VM have that you require your own regexp engine? Actually, more importantly, what is the VM for?
  - stevejohnson 17y ago
    Thanks! But you misunderstand me. The VM is the thing that is executing the DFA which represents the regular expression. That's what the paper I linked to explains. The DFA is represented by simple instructions like char, split, and jump (see the paper). Actually, I originally found that paper via - you guessed it - HN! It applies directly to the problem I am trying to solve. The VM was already implemented. I had to compile a canonical regular expression into the instructions I listed. Why? Well, let me see if my partner will let me talk about it. For now, I'll just say that we are using a completely un-string-like data structure, and we might use this engine for things which actually aren't strings. But it works on strings for now. Our demo code will currently take a regular expression (supported operators are (), ?, *, +, and |) and a list of strings, and return the strings which match the expression. I had never written a compiler before, but the code is very clean, well-documented, and doesn't have any grammar issues. So I consider this a productive week already! Next up: character classes, and maybe some character class shortcuts (\d, etc).

stevejohnson 17y ago

Update: The parser is generating a correct AST. I mean, not that anyone really cares, but I am getting some work done, which is nice.

sunir 17y ago
Hey, sweet. High five! Now I'm very curious. What kind of underlying string representation does your VM have that you require your own regexp engine? Actually, more importantly, what is the VM for?
- stevejohnson 17y ago
  Thanks! But you misunderstand me. The VM is the thing that is executing the DFA which represents the regular expression. That's what the paper I linked to explains. The DFA is represented by simple instructions like char, split, and jump (see the paper). Actually, I originally found that paper via - you guessed it - HN! It applies directly to the problem I am trying to solve. The VM was already implemented. I had to compile a canonical regular expression into the instructions I listed. Why? Well, let me see if my partner will let me talk about it. For now, I'll just say that we are using a completely un-string-like data structure, and we might use this engine for things which actually aren't strings. But it works on strings for now. Our demo code will currently take a regular expression (supported operators are (), ?, *, +, and |) and a list of strings, and return the strings which match the expression. I had never written a compiler before, but the code is very clean, well-documented, and doesn't have any grammar issues. So I consider this a productive week already! Next up: character classes, and maybe some character class shortcuts (\d, etc).