Search code examples
javaregexquantifiers

Sequential v/s Nested loop structure parsing using regex

The input can be either 1. or 2. or a combination of both.

  1. Sequential
    ...
    startLoop
      setSomething
    endLoop

    startLoop
      setSomething
    endLoop
    ...

The regex I use for this is (startLoop.+?endLoop)+? to get each loop block as my matcher group. This works fine for the sequential case where I access setSomething each time and alter it.

  1. Nested
    ...
    startLoop
      setSomething1.1
      startLoop
        setSomething2.1
        startLoop
          setSomething3
        endLoop
        setSomething2.2
      endLoop
      setSomething1.2
    endLoop
    ...

I wrote something like (startLoop.+?startLoop)+? but that only lets me access setSomething1.1

I'm not able to come up with a regex that lets me access setSomething no matter what type of loop structure the input has.

Appreciate your help.

Solution

  • I don't think it is possible to capture what you're describing with the help of regular expressions. Regular expressions can only capture regular languages whereas what you described for the nested loop situation is quite similar to a context-free language. According to the Chomsky hierarchy, regular languages form a strict subset of context-free languages and, therefore, cannot capture all context-free languages.

    CFGs vs Regular Expressions

    Context-free grammars are strictly more powerful than regular expressions.

  • Any language that can be generated using regular expressions can be generated by a context-free grammar.
  • There are languages that can be generated by a context-free grammar that cannot be generated by any regular expression.

    • Reference: http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/cfg.html