使用regex进行顺序v/s嵌套循环结构解析

Question

输入可以是1。或2。或者两者的组合。

1. 顺序

。。。startLoopsetSomethingendLoopstartLoopsetSomethingendLoop。。。

我为此使用的正则表达式是（startLoop.+？endLoop）+？以获得每个循环块作为我的匹配器组。这适用于我每次访问setSomething并更改它的顺序情况

1. 嵌套

。。。startLoop设置某些内容1.1startLoop设置某些2.1startLoop设置某些内容3endLoop设置某些2.2endLoop设置某些内容1.2endLoop。。。

我写了一些类似（startLoop.+？startLoop）+？但这只能让我访问setSomething1.1

无论输入的循环结构是什么类型，我都无法想出一个regex来访问setSomething。

感谢你的帮助。

Answer 1

我认为借助正则表达式不可能捕获您所描述的内容。正则表达式只能捕获正则语言，而您所描述的嵌套循环情况与上下文无关的语言非常相似。根据乔姆斯基层次结构，正则语言是上下文无关语言的严格子集，因此不能捕获所有上下文无关语言。

CFGs与正则表达式

上下文无关语法严格来说比正则表达式更强大

任何可以使用正则表达式生成的语言都可以通过上下文无关语法生成

有些语言可以由上下文无关语法生成，而任何正则表达式都无法生成。

参考：http://www.cs.rochester.edu/~nelson/courses/csc_173/grasms/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();
}