Последовательный анализ структуры вложенных циклов v / s с использованием регулярных выражений

Question

Ввод может быть либо 1., либо 2., либо комбинацией обоих.

1. Последовательный

    ...
    startLoop
      setSomething
    endLoop

    startLoop
      setSomething
    endLoop
    ...

Регулярное выражение, которое я использую для этого: (startLoop. +? ENDLOOP) +?чтобы получить каждый блок цикла как мою группу соответствия.Это прекрасно работает для последовательного случая, когда я каждый раз обращаюсь к setSomething и изменяю его.

1. Вложенный

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

Я написал что-то вроде (startLoop. +? StartLoop)+?но это только позволяет мне получить доступ к setSomething1.1

Я не могу придумать регулярное выражение, которое позволяет мне обращаться к setSomething независимо от того, какой тип структуры цикла имеет вход.

Ценю вашу помощь.

Answer 1

Я не думаю, что можно захватить то, что вы описываете, с помощью регулярных выражений. Регулярные выражения могут захватывать только обычные языки, тогда как то, что вы описали для ситуации с вложенным циклом, очень похоже на язык без контекста. Согласно иерархии Хомского , обычные языки образуют строгое подмножество языков без контекста и, следовательно, не могут охватить все языки без контекста.

CFG против регулярных выражений

Контекстно-свободные грамматики строго более мощны, чем регулярные выражения.

Любой язык, который может быть сгенерирован с использованием регулярных выражений, может быть создан с помощью контекстно-свободной грамматики.
Существуют языки, которые могут генерироваться грамматикой без контекста, которая не может быть создана никаким регулярным выражением.

Ссылка: http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/cfg.html

Answer 2

попробовал это, сработало. Это нелепый способ, но пока работает.

private static String normalize(String input) {
    //Final string is held here
    StringBuilder markerString = new StringBuilder(input);
    //Look for the occurrences of startLoop-endLoop structures across lines
    Pattern p1 = Pattern.compile("(startLoop.+?\\endLoop)+?",Pattern.DOTALL);
    Matcher m1 = p1.matcher(markerString.toString());
    while(m1.find()){
        /* startLoop-endLoop structure found
         * Make sure length of StringBuilder remains same
         */
        markerString.setLength(input.length());
        //group will now contain the matched subsequence of the full string
        StringBuilder group = new StringBuilder(m1.group());
        /* Look for occurrences of startLoop within the matched group
         * and maintain a counter for the no of occurrences 
         */
        Pattern p2 = Pattern.compile("(startLoop)+?",Pattern.DOTALL);
        Matcher m2 = p2.matcher(group.toString());
        int loopCounter = 0;
        while(m2.find()){
            loopCounter++;
        }
        /* this takes care of the sequential loops scenario as well as matched group
         * in nested loop scenario
         */
        markerString.replace(m1.start(), m1.end(), m1.group().
                         replaceAll("setSomething", "setThisthing"));
        /* For the no of times that startLoop occurred in the matched group,
         * do the following
         * 1. Find the next index of endLoop after the matched group's end in the full string
         * 2. Read the subsequence between matched group's end and endIndex
         * 3. Replace all setSomething with setThisthing in the subsequence
         * 4. Replace subsequence in markerString
         * 5. Decrement forCounter
         */
        int previousEndIndex = m1.end();
        int currentEndIndex = -1;
        while(loopCounter>1){
            currentEndIndex = markerString.indexOf("endLoop",previousEndIndex);
            String replacerString  = markerString.substring(previousEndIndex,currentEndIndex);
            replacerString =  replacerString.replaceAll("setSomething", "setThisThing");
            markerString.replace(previousEndIndex, currentEndIndex, replacerString);
            previousEndIndex = currentEndIndex+7;
            loopCounter--;
        }
    }
    input = markerString.toString();
}