2
\$\begingroup\$

As I started to learn about regular expressions, and as part of bigger project, I wrote a regex analyzer, which:

  1. takes the PROPER regular expression,
  2. takes the String already MATCHED by this regex,
  3. visualize with (random) colors which parts of given regex are responsible for matching a particular fragment of given string,

As said above, it works only with regex and already matched text. It works with simple patterns, it does not support more advanced regex features like: look around, named groups, reluctant and possessive quantifiers, repeated greedy quantifiers for same characters or atomic grouping. Other parts of app are responsible for dealing with these cases. I test it with regular expressions like:

  • ^[_A-Za-z0-9-]+(\.[_A-Za-z0-9-]+)*@[A-Za-z0-9]+(\.[A-Za-z0-9]+)*(\.[A-Za-z]{2,})$,
  • \d+(\.\d+),
  • ^([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])$,
  • (\D+)(\d+)c\1\2
  • [+-]\d+\s{2,3}-(\w+/)\1\1\1

and many more. Nothing really tricky, but in my opinion results are satisfying. As I wrote above, it is a part of much bigger app, the Main class below is only for presentation purposes, but Analyzer and Grouper classes are from source code, with really minor changes, to fit it to MVCE.

Main

import javax.swing.*;
import javax.swing.text.BadLocationException;
import javax.swing.text.DefaultHighlighter;
import javax.swing.text.Highlighter;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Random;
import java.util.TreeMap;

public class Main {
    JFrame frame;
    JTextField regex;
    JTextField example;
    Analyzer analyzer;
    private Highlighter forRegex;
    private Highlighter forExample;
    Highlighter.HighlightPainter pointer;

    public static void main(String[] args){
        Main main = new Main();
        main.displayGUI();
    }

    public void displayGUI(){
        frame = new JFrame();
        frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
        JPanel panel = new JPanel(new GridLayout(3,1,2,2));

        Font font = new Font("Arial", Font.BOLD, 26);


        regex = new JTextField(50);
        example = new JTextField(50);
        JButton analyze = new JButton("ANALYZE");
        regex.setFont(font);
        example.setFont(font);
        panel.add(regex);
        panel.add(example);
        panel.add(analyze);

        forExample = example.getHighlighter();
        forRegex = regex.getHighlighter();

        analyze.addActionListener(new ActionListener() {
            @Override
            public void actionPerformed(ActionEvent e) {
                analyzer = new Analyzer(regex.getText(),example.getText());
                forExample.removeAllHighlights();
                forRegex.removeAllHighlights();

                highlightAnalyzedElements(analyzer.analyze());
            }
        });

        frame.add(panel);
        frame.pack();
        frame.setVisible(true);
    }

    public void highlightAnalyzedElements(TreeMap<Integer, Integer> elements){
        int r = 0;
        Highlighter.HighlightPainter pointer;
        for(int i : elements.keySet()){
            pointer = getPainter();
            try{
                forExample.addHighlight(elements.get(r),elements.get(i),pointer);
                forRegex.addHighlight(r,i,pointer);
            }catch (BadLocationException ex){
                ex.toString();
            }
            r = i;
        }

    }

    public static Highlighter.HighlightPainter getPainter(){
        Random random = new Random();
        int mod = 76;
        int red = random.nextInt(256-mod)+mod;
        int green = random.nextInt(256-mod)+mod;
        int blue = random.nextInt(256-mod)+mod;

        return new DefaultHighlighter.DefaultHighlightPainter(new Color(red,green,blue));
    }
}

Analyzer

import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Divide the regular expression, and matched text example into related parts: fragment of expression with part of
 * example, matched by this particular fragment.
 */
public class Analyzer{
    private String regex;
    private String example;
    private Pattern pattern;
    private Matcher matcher;
    private static TreeMap<Integer,String> groups;

    public Analyzer(String regex, String analyzed){
        this.regex = regex;
        this.example = analyzed;
        Grouper grouper = new Grouper();
        groups = grouper.getExampleGroups(regex, example);
    }

    /**
     * Marge the results of analyzeForward() and analyzeBackward() methods to ensure the most correct results of
     * analysis. The junction of results corrects errors caused by analyzing only front to back, or back to front.
     * @return TreeMap with connected results
     */
    public TreeMap<Integer,Integer> analyze(){             // merge two versions
        TreeMap<Integer,Integer> merged = new TreeMap<Integer, Integer>();
        TreeMap<Integer,Integer> forward = analyzeForward();
        TreeMap<Integer,Integer> backward = analyzeBackward();
        merged.putAll(forward);
        for(int key : backward.keySet()){
            if((!(backward.get(key)==0))
                    && merged.containsKey(key) && forward.get(key)==example.length()){
                merged.put(key,backward.get(key));
            }
        }
        merged = validate(merged);
        merged = checkForEndOfALina(merged);
        merged = checkForBeginningOfALina(merged);

        return merged;
    }

    /**
     *Divides used pattern and text into parts, depending on which part was responsible for matching of particular
     *text fragment.
     *
     *Takes two Strings: Pattern (regular expression for matching purposes), and Example (text to match), and use
     *multiple sub-strings of the Pattern (from a range: [0 - pattern.length()]) as separate regular expression
     *patterns, for matching in given Example. If a particular substring matches to fragment of Example, it writes:
     *end index of match in Example, and start index of substring in Patter; into TreeMap, which holds record for
     *all matches for particular pattern-example set.
     *Method throws PatternSyntax and IllegalState Exceptions, as a part of regular method flow, to distinguish invalid
     *patterns, from valid pattern which are then recorded.
     * @return TreeMap\<Integer,Integer\> with two sets of indices - for Pattern and Example Strings.
     */
    private TreeMap<Integer, Integer> analyzeForward(){
        TreeMap<Integer, Integer> matched = new TreeMap<Integer, Integer>();

        for(int i = 0; i <= regex.length() ; i++){    // int i decide about length of substring
            try{
                pattern = Pattern.compile(regex.substring(0,i));
                matcher = pattern.matcher(example);
                matcher.find();
                matched.put(i, matcher.end());
            }catch (Exception ex){
                System.out.println(ex.toString());
            }
        }

        return matched;
    }

    /**
     *Divides used pattern and text into parts, depending on which part was responsible for matching of particular
     *text fragment.
     *
     *Takes two Strings: Pattern (regular expression for matching purposes), and Example (text to match), and use
     *multiple sub-strings of the Pattern (from a range: [pattern.length() - 0) as separate regular expression
     *patterns, for matching in given Example. If a particular substring matches to fragment of Example, it writes:
     *start index of match in Example, and start index of substring in Patter; into TreeMap, which holds record for
     *all matches for particular pattern-example set.
     *Method throws PatternSyntax and IllegalState Exceptions, as a part of regular method flow, to distinguish invalid
     *patterns, from valid pattern which are then recorded.
     * @return TreeMap\<Integer,Integer\> with two sets of indices - for Pattern and Example Strings.
     */
    private TreeMap<Integer, Integer> analyzeBackward(){
        TreeMap<Integer, Integer> matched = new TreeMap<Integer, Integer>();
        for(int i = regex.length(); i >= 0 ; i--){    // int i decide about length of substring
            try{
                String temp = getProperSample(regex.substring(i));
                pattern = Pattern.compile(temp+"$");
                matcher = pattern.matcher(example);
                matcher.find();
                if(i == regex.length() && matcher.start()==0){      //is it necessary with merge?
                    matched.put(i, example.length());
                    continue;
                }
                matched.put(i, matcher.start());
            }catch (Exception ex){
                System.out.println(ex.toString());
            }
        }
        matched = checkForEndOfALina(matched);
        return matched;
    }

    /**
     * Changes the calls for captured groups (for example \1,\2,\3) for exact literal content of captured particular
     * group to ensure successful match during backward analyzing. Without that, the call fragments would not match
     * for any example text part.
     * @param str  String containing call for captured group
     * @return String with calls for capturing groups replaced by groups literal content
     */
    private String getProperSample(String str){

        String sample = str;
        if(str.length()>1 && str.substring(0,2).matches("\\\\\\d")){
            for(int key : groups.keySet()){
                if(groups.get(key)!=null){
                    String temp = "(" + groups.get(key).replace("\\","\\\\\\\\") + ")";         //this is a crucial part to replece single "\"!!!
                    sample = sample.replaceAll("\\\\"+key, temp);
                }
            }
        }
        return sample;
    }

    /**
     * If "$"( - end of a line) mark is present in pattern, it ensure that a last matched text part is properly
     * distinguished and highlighted.
     * @param toCheck TreeMap with indexes of matched pattern-example set,
     * @return TreeMap toCheck, modified if pattern ends with "$".
     */
    private TreeMap<Integer,Integer> checkForEndOfALina(TreeMap<Integer,Integer> toCheck){
        if(regex.endsWith("$")){
            int lastMatch = getLastMatch();
            for(int i : toCheck.keySet()){                                    //loop ensure that only one index will
                if(toCheck.get(i)==example.length() && i!=regex.length()){    //be the last index of last character
                    toCheck.put(i,lastMatch);                                 //in pattern
                }
            }
            toCheck.remove(regex.length()-1);     //this line remove one before last index, because without it, the
        }                                         //last character of pattern("$") would not be highlighted.
        return toCheck;
    }

    /**
     * Creates sub-patterns from last characters of original regular expression pattern. First sub-pattern which will
     * match is therefore directly connected with "$"( - the end of line) mark, and match last required by pattern
     * fragment of text.
     * @return index of first character in text, which match with "end of line" sub-pattern.
     */
    private int getLastMatch(){

        for(int i = regex.length(); i >= 0 ; i--){    // int i decide about length of substring
            try{

                pattern = Pattern.compile(regex.substring(i,regex.length()));
                matcher = pattern.matcher(example);
                matcher.find();
                if(matcher.start() != 0 && matcher.start() != example.length()){
                    return matcher.start();
                }

            }catch (Exception ex){
                System.out.println(ex.toString());
            }
        }
        return example.length();
    }

    /**
     * If "^" ( - beginning of a line) mark is present in pattern, it ensures that first character of pattern is
     * correctly highlighted with first distinguished part of matched text.
     * @param toCheck TreeMap with indexes of matched pattern-example set
     * @return TreeMap to Check, modified if pattern ends with "^".
     */
    private TreeMap<Integer,Integer> checkForBeginningOfALina(TreeMap<Integer,Integer> toCheck){
        if(regex.startsWith("^")){
            toCheck.remove(1,0);
        }
        return toCheck;
    }

    /**
     * Checks if in returned by analyzing methods TreeMaps are results which will cause BadLocationException. If
     * some part of regular expression is able to match whole example(for example by use of greedy
     * *+ or ?), results of match will distort the match values given by next checked regular expressions parts. To
     * avoid BadLocationExceptions such indices are replaced by beginning index of next successful match.
     * @param sample TreeMap with indices of successful matches by various regex parts
     * @return checked and validated TreeMap
     */
    private TreeMap<Integer,Integer> validate(TreeMap<Integer,Integer> sample){
        ArrayList<Integer> keys = new ArrayList<Integer>(sample.keySet());
        Collections.reverse(keys);

        int lastValue = example.length();

        for(int key : keys){
            if(sample.get(key) > lastValue){
                sample.put(key,lastValue);
            }
            lastValue = sample.get(key);
        }

        return sample;
    }
}

Grouper

import java.util.ArrayList;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Operates on regular expression and an example text to provide regex fragments responsible for capturing groups
 * and example fragments match by particular regex fragments.
 */
public class Grouper {
    int escape;
    String regex;

    /**
     * Provide a set of regex fragments, which are responsible for capturing groups.
     * @param pattern matching pattern.
     * @return TreeMap with capturing fragments of regular expression.
     */
    public TreeMap<Integer,String> getPatternsGroups(String pattern){
        this.regex = pattern;
        TreeMap<Integer,StringBuilder> temp = new TreeMap<Integer,StringBuilder>();
        int level = 0;              // to determine level of nested parenthesis, and which strings update
        int place = 1;              // to determine 'key' for group, group 0 is always whole regular expression
        escape = 0;                 // to count backslash occurrence, to determine if it is escape for parenthesis or for
        // other backslash

        ArrayList<StringBuilder> builders = new ArrayList<StringBuilder>();
        for(int i = 0; i < regex.length(); i++){
            String current = regex.substring(i,i+1);

            if(current.equals("\\")){
                escape++;
            }

            if(isOpeningParenthesis(i)){
                StringBuilder builder = new StringBuilder();
                builders.add(level++, builder);
                if(isGrouping(i)) {
                    temp.put(place++, builder);
                    System.out.println(builder.toString());
                }
            }

            for(int k = 0; k<=level-1; k++){
                builders.get(k).append(current);
            }

            if(isClosingParenthesis(i)){
                level --;
            }
        }

        return toProperFormat(temp);
    }

    /**
     * Convert a temporary Map from getPatternGroups() method into final return object.
     * @param toConvert Map to convert
     * @return converted Map object
     */
    private TreeMap<Integer,String> toProperFormat(TreeMap<Integer,StringBuilder> toConvert){
        TreeMap<Integer,String> groups = new TreeMap<Integer, String>();
        groups.put(0, regex);
        for(int key : toConvert.keySet()){
            groups.put(key, toConvert.get(key).toString());
        }
        return groups;
    }

    /**
     * Provide a set of captured regex groups from given pattern and String example pair.
     * @param regex pattern to match.
     * @param example String to match by pattern.
     * @return TreeMap with captured Strings.
     */
    public TreeMap<Integer,String> getExampleGroups(String regex,String example){
        TreeMap<Integer,String> groups = new TreeMap<Integer, String>();
        try{
            Pattern pattern = Pattern.compile(regex);
            Matcher matcher = pattern.matcher(example);
            matcher.find();
            for(int i = 0; i <= matcher.groupCount(); i++){
                groups.put(i,matcher.group(i));
            }
        }catch (Exception ex){
            ex.toString();
        }
        return groups;
    }

    /**
     * Determine if character on given position is a metacharacter in regex.
     * @param i position of character in String,
     * @return true if character is metacharacter.
     */
    private boolean isMetacharacter(int i){
        return (i>0 && (!regex.substring(i-1,i).equals("\\")));
    }

    /**
     * Determine if a character on a given index position in String i a simple opening parenthesis character.
     * @param i position of character in String,
     * @return true i character is opening parenthesis.
     */
    private boolean isOpeningParenthesis(int i){
        return regex.substring(i,i+1).equals("(") && (i==0 || (i>0 && isMetacharacter(i)));
    }

    /**
     * Determine if a character on a given index position in String i a simple closing parenthesis character.
     * @param i position of character in String,
     * @return true i character is closing parenthesis.
     */
    private boolean isClosingParenthesis(int i){
        return regex.substring(i,i+1).equals(")")&& (!regex.substring(i-1,i).equals("\\"));
    }

    /**
     * Determine if a String, which starts from given index, is a beginning of a grouping parentheses.
     * @param i index of character which is currently checking
     * @return true if group is capturing
     */
    private boolean isGrouping(int i){
        return !(regex.length() >= i +4 && regex.substring(i,i+3).equals("(?:") && regex.substring(i,i+4).matches("\\(\\?[ixmsud]\\)"));
    }
}

I aware that this is a quite long code, however I would be very grateful if someone would review it. I am especially interested in:

  1. Class and methods structure - are these to complex? should be divided?
  2. Readability of code, method naming, indentation, etc.
  3. Comments, aren't they reveal too much about interior design of methods?
  4. Any obvious (but not for me) mistakes?.

I would appreciate any comments!

\$\endgroup\$
2
\$\begingroup\$

Favor interfaces over implementations

    public void highlightAnalyzedElements(TreeMap<Integer, Integer> elements){

You don't need to call elements a TreeMap here. It would be sufficient to use a Map.

    public void highlightAnalyzedElements(Map<Integer, Integer> elements) {

As a general rule, you are better off putting the interface everywhere but the new allocation. That way you can easily change implementations if needed. The exception would of course be if there was some method that was only on TreeMap that you were using. But in this method you use only keySet and get, which are both on Map.

You have the same issue with ArrayList. E.g.

        ArrayList<Integer> keys = new ArrayList<Integer>(merged.keySet());

could become

        List<Integer> keys = new ArrayList<Integer>(merged.keySet());

Declare variables as restricted as possible

        Highlighter.HighlightPainter pointer;
        for(int i : elements.keySet()){
            pointer = getPainter();

It's a bit confusing to make a second, local variable with the same name as a field. Also, since you never use the variable outside the loop or across iterations, you can define it inside the loop:

        for (int i : elements.keySet()) {
            final Highlighter.HighlightPainter painter = getPainter();

Also, since you never change it after declaration, the variable can be final.

I added additional whitespace for readability.

Do you need TreeMap?

A TreeMap takes \$O(\log n)\$ time for inserts, removals, and finds. You can get constant time for each of these with HashMap if you don't need the sorted nature of a TreeMap.

You may have already profiled this and found TreeMap better for your application, but I thought I'd mention it as something to consider.

Avoid extra work if you can

    private TreeMap<Integer,String> toProperFormat(TreeMap<Integer,StringBuilder> toConvert){
        TreeMap<Integer,String> groups = new TreeMap<Integer, String>();
        groups.put(0, regex);
        for(int key : toConvert.keySet()){
            groups.put(key, toConvert.get(key).toString());
        }
        return groups;
    }

There's actually a construct just for this type of iteration, the entrySet.

    private Map<Integer, String> toProperFormat(Map<Integer, StringBuilder> toConvert) {
        Map<Integer, String> groups = new TreeMap<>();

        groups.put(0, regex);
        for (Map.Entry<Integer, StringBuilder> entry : toConvert.entrySet()){
            groups.put(entry.getKey(), entry.getValue().toString());
        }

        return groups;
    }

You might want to profile this. It should certainly be faster for a TreeMap, which is easily iterable. It may or may not be faster for a HashMap.

Not needed in Javadoc

    /**
     * Marge the results of analyzeForward() and analyzeBackward() methods to ensure the most correct results of
     * analysis. The junction of results corrects errors caused by analyzing only front to back, or back to front.
     * @return TreeMap with connected results
     */
    public TreeMap<Integer,Integer> analyze(){             // merge two versions

You could just say

    /**
     * Analyze front to back and back to front.
     * The junction of results corrects errors caused by analyzing only one direction.
     * @return Map with connected results
     */
    public Map<Integer, Integer> analyze() {

Also removed the extraneous comment at the end and adjusted return type and spacing.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.