Код для разбора групп захвата в регулярных выражениях в дерево - PullRequest
Новая
       17

Код для разбора групп захвата в регулярных выражениях в дерево

1 голос
/ 16 сентября 2009

Мне нужно идентифицировать (потенциально вложенные) группы захвата в регулярных выражениях и создать дерево. Конкретной целью является Java-1.6, и в идеале я бы хотел Java-код. Простой пример:

"(а (Ь |) г (е (е * г)) ч)"

, который будет проанализирован до 

"a(b|c)d(e(f*g))h"
... "b|c"
... "e(f*g)"
     ... "f*g"

В идеале решение должно учитывать выражения подсчета, квантификаторы и т. Д. И уровни экранирования. Однако, если это не легко найти, может быть достаточно простого подхода, поскольку мы можем ограничить используемый синтаксис.

EDIT . Чтобы уточнить. Я хочу проанализировать саму строку регулярного выражения . Для этого мне нужно знать BNF или эквивалент для регулярных выражений Java 1.6. Я надеюсь, что кто-то уже сделал это.

Побочным продуктом результата будет то, что процесс будет проверять правильность регулярного выражения.

Ответы [ 2 ]

1 голос
/ 16 сентября 2009

Рассмотрите возможность перехода к фактическому парсеру / лексеру: http://www.antlr.org/wiki/display/ANTLR3/FAQ+-+Getting+Started

Это выглядит сложно, но если ваш язык довольно прост, он довольно прост. И если это не так, выполнение этого в регулярных выражениях, вероятно, сделает вашу жизнь адом:)

0 голосов
/ 17 сентября 2009

Я придумал частичное решение, используя инструмент XML (XOM, http://www.xom.nu) для хранения дерева. Сначала код, затем пример синтаксического анализа. Сначала экранированные символы (\, (и)) де -escaped (здесь я использую BS, LB и RB), затем оставшиеся скобки переводятся в теги XML, затем XML анализируется и символы снова экранируются. Что еще нужно для BNF для Java 1.6, выполняет регулярные выражения, такие как? :, {d, d} и т. д. 

public static Element parseRegex(String regex) throws Exception {
    regex = regex.replaceAll("\\\\", "BS");
    regex.replaceAll("BS\\(", "LB");
    regex.replaceAll("BS\\)", "RB");
    regex = regex.replaceAll("\\(", "<bracket>");
    regex.replaceAll("\\)", "</bracket>");
    Element regexX = new Builder().build(new StringReader(
         "<regex>"+regex+"</regex>")).getRootElement();
    extractCaptureGroupContent(regexX);
    return regexX;
}

private static String extractCaptureGroupContent(Element regexX) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < regexX.getChildCount(); i++) {
        Node childNode = regexX.getChild(i);
        if (childNode instanceof Text) {
            Text t = (Text)childNode;
            String s = t.getValue();
            s = s.replaceAll("BS", "\\\\").replaceAll("LB", 
                        "\\(").replaceAll("RB", "\\)");
            t.setValue(s);
            sb.append(s);
        } else {
            sb.append("("+extractCaptureGroupContent((Element)childNode)+")");
        }
    }
    String capture = sb.toString();
    regexX.addAttribute(new Attribute("capture", capture));
    return capture;
}

пример: 

@Test
public void testParseRegex2() throws Exception {
    String regex = "(.*(\\(b\\))c(d(e)))";
    Element regexElement = ParserUtil.parseRegex(regex);
    CMLUtil.debug(regexElement, "x");
}

дает: 

<regex capture="(.*((b))c(d(e)))">
  <bracket capture=".*((b))c(d(e))">.*
    <bracket capture="(b)">(b)</bracket>c
    <bracket capture="d(e)">d
      <bracket capture="e">e</bracket>
    </bracket>
  </bracket>
</regex>
...