Code pour analyser des groupes de capture dans des expressions régulières dans un arbre

Question

Je dois identifier (potentiellement imbriqué) des groupes de capture dans des expressions régulières et créer un arbre. La cible particulière est Java-1.6 et j'aimerai idéalement le code Java. Un exemple simple est:

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

qui serait analysé à

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

La solution doit prendre en compte idéalement pour les expressions de compte, les quantificateurs, etc. et les niveaux d'échappement. Cependant, si cela n'est pas facile à trouver, une approche plus simple pourrait suffire car nous pouvons limiter la syntaxe utilisée.

EDIT. Clarifier. Je veux analyser la chaîne d'expressions régulières elle-même. Pour ce faire, j'ai besoin de connaître le BNF ou équivalent pour les expressions rationnelles Java 1.6. J'espère que quelqu'un l'a déjà fait.

Un sous-produit d'un résultat serait que le processus teste la validité de l'expression régulière.

Answer 1

envisager de renforcer un analyseur réel/lexer: http://www.antlr.org/wiki/display/ANTLR3/FAQ+-+Getting+Started

Il semble compliqué, mais si votre langue est assez simple, il est assez simple. Et si ce n'est pas le cas, le faire dans les expressions régulières va probablement faire votre vie enfer :)

Answer 2

Je suis venu avec une solution partielle en utilisant un outil XML (XOM, http://www.xom.nu) pour tenir l'arbre. D'abord le code, puis un exemple d'analyse. D'abord les caractères échappés (\, (et)) sont échappés (ici j'utilise BS, LB et RB), alors les crochets restants sont traduits en balises XML, puis le XML est analysé et les caractères rééchappés. Ce qui est nécessaire est en outre un BNF pour Java 1.6 expressions regexes quantificateurs tels que?:, {D, d} et ainsi de suite.

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; 
} 

exemple:

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

donne:

<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>