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*

11
  • 7
    Actually, that is wrong. A pure Regex can be implemented without need for backtracking using either a Finite State Automata, or a Pushdown Finite State Automata. Take a look here at a good write-up by Russ Cox. Commented Mar 19, 2020 at 8:03
  • @Kain0_0 Sure they can, but typically you then lose the interesting functionality that you actually want while programming, such as capturing and backreferencing. I assume that OP wants to capture information, not just Booleans. Commented Mar 19, 2020 at 9:07
  • @KilianFoth Thanks! For my current case 14GB memory is not enough. I have a massive JSON and I want to extract URLs from it. I have the right constraints to be able to use what I wrote in my question, I was just curious if there is a general solution. According to your answer a non-backtracking regex engine would solve this. It is interesting, because I was looking for a way to solve the redos issue too. I did not realize there are engines without backtracking. github.com/uhop/node-re2 Commented Mar 19, 2020 at 10:27
  • @KilianFoth Warning sour ppl arrived to downvote. :D Commented Mar 19, 2020 at 10:30
  • 2
    @KilianFoth Again incorrect. Push down automata can stow position information in the stack, you can even stow the relevant pieces of information captured from the text and apply relevant transformations. Run these automata in parallel, sharing portions of the stack between instances. These can support look around, back reference, and CF Grammars. Need only provide group level operations such as branch, anchor, cut, join, token, and production-rule, that work on the group of automata branching from the same shared base stack. Commented Mar 20, 2020 at 0:02