Skip to main content
Software Engineering

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

5
  • So that's how actual regex engine works. It creates an NFA but store states everytime it tries to "branch" out. Is this true? Commented Nov 9, 2015 at 14:41
  • @JimThio how exactly it does its backtracking is an implementation detail. One way would be to push the state on a stack another would be to use recursion and use the application stack as the stack. Commented Nov 9, 2015 at 14:53
  • so real regex engine uses stack. Interesting. Hmmm... Any references he he he he. Commented Nov 9, 2015 at 15:52
  • @JimThio the Java compiled regular expression state machine and stack can be seen in the Pattern class. Commented Nov 9, 2015 at 21:27
  • 1
    A practical article I like on this subject describes how the NFA of a regexp can be translated to instructions. The instructions are 'char c', 'match' 'jmp x' and 'split x,y'. The 'jmp x' instruction jumps to the label x. The 'split x,y' instruction jumps to both label x and label y. The article is here The article also describes a handful of interpreters for the instructions, in historic implementations. I myself branched off from it to write a glob matcher that implemented the characters of the glob pattern as the instructions. Commented Nov 9, 2015 at 23:54