Fighting f̶i̶r̶e̶ regex with f̶i̶r̶e̶ regex

Question

So someone requested a Regex Builder / Assistant for Rubberduck and since my CS class had been covering the topic only recently I was thinking to myself: "This sounds interesting, you should do this".

Long story short, a day of designing and a weekend of implementation (and some more polishing) as well as a few reviews later Rubberduck has a fully working Regex Assistant (which even supports i18n).

It can be given a VBA Regular Expression pattern and tells you what it does in a manner similar to other well-known assistants (regex101, expresso, ...)

This means it can parse a given syntactically correct Regex and recognize the separate Atoms and Quantifiers. It analyzes said Atoms and builds a structure that allows displaying useful information about the pattern.
This is accomplished by parsing the expression into a Tree-Structure.

Any Regular Expression is built by either the smallest possible unit you have (an Atom) or other regular expressions. This definition allows us to "abuse" the syntax into building our Design.

We basically need to handle two (well three) things to represent any arbitrary Regular Expression.

1. Atoms
2. Regular Expressions
3. Quantifiers

to be fully correct, Quantifiers actually belong in cahoots with Atoms, but they're.. different, so we'll treat them differently.

This sets the stage for our "data holders":

Atom.cs

using Rubberduck.RegexAssistant.i18n;
using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;

namespace Rubberduck.RegexAssistant
{
    public interface IAtom : IDescribable
    {
        string Specifier { get; }
    }

    internal class CharacterClass : IAtom
    {
        public static readonly string Pattern = @"(?<!\\)\[(?<expression>.*?)(?<!\\)\]";
        private static readonly Regex Matcher = new Regex("^" + Pattern + "$");

        private readonly bool _inverseMatching;
        public bool InverseMatching { get { return _inverseMatching; } }
        private readonly IList<string> _characterSpecifiers;
        public IList<string> CharacterSpecifiers { get { return _characterSpecifiers; } }
        private readonly string _specifier;

        public CharacterClass(string specifier)
        {
            Match m = Matcher.Match(specifier);
            if (!m.Success)
            {
                throw new ArgumentException("The given specifier does not denote a character class");
            }
            this._specifier = specifier;
            string actualSpecifier = m.Groups["expression"].Value;
            _inverseMatching = actualSpecifier.StartsWith("^");
            _characterSpecifiers= ExtractCharacterSpecifiers(InverseMatching ? actualSpecifier.Substring(1) : actualSpecifier);
        }

        public string Specifier
        {
            get
            {
                return _specifier;
            }
        }

        private static readonly Regex CharacterRanges = new Regex(@"(\\[dDwWsS]|(\\[ntfvr]|\\([0-7]{3}|x[\dA-F]{2}|u[\dA-F]{4}|[\\\.\[\]])|.)(-(\\[ntfvr]|\\([0-7]{3}|x[A-F]{2}|u[\dA-F]{4}|[\.\\\[\]])|.))?)");
        private IList<string> ExtractCharacterSpecifiers(string characterClass)
        {
            MatchCollection specifiers = CharacterRanges.Matches(characterClass);
            var result = new List<string>();

            foreach (Match specifier in specifiers)
            {
                if (specifier.Value.Contains("\\"))
                {
                    if (specifier.Value.EndsWith("-\\"))
                    {
                        throw new ArgumentException("Character Ranges that have incorrectly escaped characters as target are not allowed");
                    }
                    else if (specifier.Value.Length == 1)
                    {
                        // Something's bork with the Pattern. For now we skip this it shouldn't affect anyone
                        continue;
                    }
                }
                result.Add(specifier.Value);
            }
            return result;
        }

        public string Description
        {
            get
            {
                return string.Format(InverseMatching 
                    ? AssistantResources.AtomDescription_CharacterClass_Inverted 
                    : AssistantResources.AtomDescription_CharacterClass
                    , HumanReadableClass());
            }
        }

        private string HumanReadableClass()
        {
            return string.Join(", ", CharacterSpecifiers); // join last with and?
        }

        public override bool Equals(object obj)
        {
            if (obj is CharacterClass)
            {
                return (obj as CharacterClass)._specifier.Equals(_specifier);
            }
            return false;
        }

        public override int GetHashCode()
        {
            return _specifier.GetHashCode();
        }
    }

    public class Group : IAtom
    {
        public static readonly string Pattern = @"(?<!\\)\((?<expression>.*(?<!\\))\)";
        private static readonly Regex Matcher = new Regex("^" + Pattern + "$");

        private readonly IRegularExpression _subexpression;
        private readonly string _specifier;

        public Group(string specifier) {
            Match m = Matcher.Match(specifier);
            if (!m.Success)
            {
                throw new ArgumentException("The given specifier does not denote a Group");
            }
            _subexpression = RegularExpression.Parse(m.Groups["expression"].Value);
            _specifier = specifier;
        }

        public IRegularExpression Subexpression { get { return _subexpression; } }

        public string Specifier
        {
            get
            {
                return _specifier;
            }
        }

        public string Description
        {
            get
            {
                return string.Format(AssistantResources.AtomDescription_Group, _specifier);
            }
        }

        public override bool Equals(object obj)
        {
            if (obj is Group)
            {
                return (obj as Group)._specifier.Equals(_specifier);
            }
            return false;
        }

        public override int GetHashCode()
        {
            return _specifier.GetHashCode();
        }
    }

    internal class Literal : IAtom
    {
        public static readonly string Pattern = @"(?<expression>\\(u[\dA-F]{4}|x[\dA-F]{2}|[0-7]{3}|[bB\(\){}\\\[\]\.+*?1-9nftvrdDwWsS])|[^()\[\]{}\\*+?^$])";
        private static readonly Regex Matcher = new Regex("^" + Pattern + "$");
        private static readonly ISet<char> EscapeLiterals = new HashSet<char>();
        private readonly string _specifier;

        static Literal() {
            foreach (char escape in new char[]{ '.', '+', '*', '?', '(', ')', '{', '}', '[', ']', '|', '\\' })
            {
                EscapeLiterals.Add(escape);
            }
            _escapeDescriptions.Add('d', AssistantResources.AtomDescription_Digit);
            _escapeDescriptions.Add('D', AssistantResources.AtomDescription_NonDigit);
            _escapeDescriptions.Add('b', AssistantResources.AtomDescription_WordBoundary);
            _escapeDescriptions.Add('B', AssistantResources.AtomDescription_NonWordBoundary);
            _escapeDescriptions.Add('w', AssistantResources.AtomDescription_WordCharacter);
            _escapeDescriptions.Add('W', AssistantResources.AtomDescription_NonWordCharacter);
            _escapeDescriptions.Add('s', AssistantResources.AtomDescription_Whitespace);
            _escapeDescriptions.Add('S', AssistantResources.AtomDescription_NonWhitespace);
            _escapeDescriptions.Add('n', AssistantResources.AtomDescription_Newline);
            _escapeDescriptions.Add('r', AssistantResources.AtomDescription_CarriageReturn);
            _escapeDescriptions.Add('f', AssistantResources.AtomDescription_FormFeed);
            _escapeDescriptions.Add('v', AssistantResources.AtomDescription_VTab);
            _escapeDescriptions.Add('t', AssistantResources.AtomDescription_HTab);
        }

        public Literal(string specifier)
        {
            Match m = Matcher.Match(specifier);
            if (!m.Success)
            {
                throw new ArgumentException("The given specifier does not denote a Literal");
            }
            _specifier = specifier;
        }

        public string Specifier
        {
            get
            {
                return _specifier;
            }
        }


        private static readonly Dictionary<char, string> _escapeDescriptions = new Dictionary<char, string>();
        public string Description
        {
            get
            {
                // here be dragons!
                // keep track of:
                // - escaped chars
                // - escape sequences (each having a different description)
                // - codepoint escapes (belongs into above category but kept separate)
                // - and actually boring literal matches
                if (_specifier.Length > 1)
                {
                    string relevant = _specifier.Substring(1); // skip the damn Backslash at the start
                    if (relevant.Length > 1) // longer sequences
                    {
                        if (relevant.StartsWith("u"))
                        {
                            return string.Format(AssistantResources.AtomDescription_Literal_UnicodePoint, relevant.Substring(1)); //skip u
                        }
                        else if (relevant.StartsWith("x"))
                        {
                            return string.Format(AssistantResources.AtomDescription_Literal_HexCodepoint, relevant.Substring(1)); // skip x
                        }
                        else
                        {
                            return string.Format(AssistantResources.AtomDescription_Literal_OctalCodepoint, relevant); // no format specifier to skip
                        }
                    }
                    else if (EscapeLiterals.Contains(relevant[0]))
                    {
                        return string.Format(AssistantResources.AtomDescription_Literal_EscapedLiteral, relevant);
                    }
                    else if (char.IsDigit(relevant[0]))
                    {
                        return string.Format(AssistantResources.AtomDescription_Literal_Backreference, relevant);
                    }
                    else
                    {
                        return _escapeDescriptions[relevant[0]];
                    }
                }
                if (_specifier.Equals("."))
                {
                    return AssistantResources.AtomDescription_Dot;
                }
                return string.Format(AssistantResources.AtomDescription_Literal_ActualLiteral, _specifier);

            }
        }

        public override bool Equals(object obj)
        {
            if (obj is Literal)
            {
                return (obj as Literal)._specifier.Equals(_specifier);
            }
            return false;
        }

        public override int GetHashCode()
        {
            return _specifier.GetHashCode();
        }
    }
}

IRegularExpression.cs

using Rubberduck.RegexAssistant.Extensions;
using Rubberduck.RegexAssistant.i18n;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rubberduck.RegexAssistant
{
    public interface IRegularExpression : IDescribable
    {
        Quantifier Quantifier { get; }
        IList<IRegularExpression> Subexpressions { get; }
    }

    public class ConcatenatedExpression : IRegularExpression
    {
        private readonly Quantifier _quantifier;
        private readonly IList<IRegularExpression> _subexpressions;

        public ConcatenatedExpression(IList<IRegularExpression> subexpressions)
        {
            _subexpressions = subexpressions;
            _quantifier = new Quantifier(string.Empty); // these are always exactly once. Quantifying happens through groups
        }

        public string Description
        {
            get
            {
                return AssistantResources.ExpressionDescription_ConcatenatedExpression;
            }
        }

        public Quantifier Quantifier
        {
            get
            {
                return _quantifier;
            }
        }

        public IList<IRegularExpression> Subexpressions
        {
            get
            {
                return _subexpressions;
            }
        }
    }

    public class AlternativesExpression : IRegularExpression
    {
        private readonly Quantifier _quantifier;
        private readonly IList<IRegularExpression> _subexpressions;

        public AlternativesExpression(IList<IRegularExpression> subexpressions)
        {
            _subexpressions = subexpressions;
            _quantifier = new Quantifier(string.Empty); // these are always exactly once. Quantifying happens through groups
        }

        public string Description
        {
            get
            {
                return string.Format(AssistantResources.ExpressionDescription_AlternativesExpression, _subexpressions.Count);
            }
        }

        public Quantifier Quantifier
        {
            get
            {
                return _quantifier;
            }
        }

        public IList<IRegularExpression> Subexpressions
        {
            get
            {
                return _subexpressions;
            }
        }
    }

    public class SingleAtomExpression : IRegularExpression
    {
        public readonly IAtom Atom;
        private readonly Quantifier _quantifier;

        public SingleAtomExpression(IAtom atom, Quantifier quantifier)
        {
            Atom = atom;
            _quantifier = quantifier;
        }

        public string Description
        {
            get
            {
                return string.Format("{0} {1}.", Atom.Description, Quantifier.HumanReadable());
            }
        }

        public Quantifier Quantifier
        {
            get
            {
                return _quantifier;
            }
        }

        public IList<IRegularExpression> Subexpressions
        {
            get
            {
                return new List<IRegularExpression>(Enumerable.Empty<IRegularExpression>());
            }
        }

        public override bool Equals(object obj)
        {
            if (obj is SingleAtomExpression)
            {
                SingleAtomExpression other = obj as SingleAtomExpression;
                return other.Atom.Equals(Atom) && other.Quantifier.Equals(Quantifier);
            }
            return false;
        }

        public override int GetHashCode()
        {
            return Atom.GetHashCode() ^ Quantifier.GetHashCode();
        }

    }

    public class ErrorExpression : IRegularExpression
    {
        private readonly string _errorToken;

        public ErrorExpression(string errorToken)
        {
            _errorToken = errorToken;
        }

        public string Description
        {
            get
            {
                return string.Format(AssistantResources.ExpressionDescription_ErrorExpression, _errorToken);
            }
        }

        public Quantifier Quantifier
        {
            get
            {
                return new Quantifier(string.Empty);
            }
        }

        public IList<IRegularExpression> Subexpressions
        {
            get
            {
                return new List<IRegularExpression>();
            }
        }
    }
}

and for the curious:

Quantifier.cs

using System;
using System.Text.RegularExpressions;

namespace Rubberduck.RegexAssistant
{
    public class Quantifier
    {
        public static readonly string Pattern = @"(?<quantifier>(?<!\\)[\?\*\+]|(?<!\\)\{(\d+)(,\d*)?(?<!\\)\})";
        private static readonly Regex Matcher = new Regex(@"^\{(?<min>\d+)(?<max>,\d*)?\}$");

        public readonly QuantifierKind Kind;
        public readonly int MinimumMatches;
        public readonly int MaximumMatches;

        public Quantifier(string expression)
        {
            if (expression.Length == 0)
            {
                Kind = QuantifierKind.None;
                MaximumMatches = 1;
                MinimumMatches = 1;
            }
            else if (expression.Length > 1)
            {
                Kind = QuantifierKind.Expression;
                Match m = Matcher.Match(expression);
                if (!m.Success)
                {
                    throw new ArgumentException(string.Format("Cannot extract a Quantifier from the expression {1}", expression));
                }
                int minimum;
                // shouldn't ever happen
                if (!int.TryParse(m.Groups["min"].Value, out minimum))
                {
                    throw new ArgumentException("Cannot Parse Quantifier Expression into Range");
                }
                MinimumMatches = minimum;

                string maximumString = m.Groups["max"].Value; // drop the comma
                if (maximumString.Length > 1)
                {
                    int maximum;
                    // shouldn't ever happen
                    if (!int.TryParse(maximumString.Substring(1), out maximum))
                    {
                        throw new ArgumentException("Cannot Parse Quantifier Expression into Range");
                    }
                    MaximumMatches = maximum;
                }
                else if (maximumString.Length == 1) // got a comma, so we're unbounded
                {
                    MaximumMatches = int.MaxValue;
                }
                else // exact match, because no comma
                {
                    MaximumMatches = minimum;
                }
            }
            else
            {
                switch (expression.ToCharArray()[0])
                {
                    case '*':
                        MinimumMatches = 0;
                        MaximumMatches = int.MaxValue;
                        Kind = QuantifierKind.Wildcard;
                        break;
                    case '+':
                        MinimumMatches = 1;
                        MaximumMatches = int.MaxValue;
                        Kind = QuantifierKind.Wildcard;
                        break;
                    case '?':
                        MinimumMatches = 0;
                        MaximumMatches = 1;
                        Kind = QuantifierKind.Wildcard;
                        break;
                    default:
                        throw new ArgumentException("Passed Quantifier String was not an allowed Quantifier");
                }
            }
        }

        public override bool Equals(object obj)
        {
            if (obj is Quantifier)
            {
                var other = obj as Quantifier;
                return other.Kind == Kind && other.MinimumMatches == MinimumMatches && other.MaximumMatches == MaximumMatches;
            }
            return false;
        }

        public override int GetHashCode()
        {
            return MinimumMatches ^ MaximumMatches ^ Kind.GetHashCode();
        }

        public override string ToString()
        {
            return string.Format("Quantifier[{0}: {1} to {2}", Kind, MinimumMatches, MaximumMatches);
        }
    }

    public enum QuantifierKind
    {
        None, Expression, Wildcard
    }
}

Now all of this must critically support internationalization. That's why each of these is inherently coupled with some internationalization. I'm aware that this could be somewhat avoided with extension methods or by introducing a separate class to handle the mess. I decided against that to keep the simplicity of the design.

Last but not least, we'll need to actually build a tree from these "data holders". That's done ... well I have a big comment there, it explains how it works:

internal static class RegularExpression
{

    /// <summary>
    /// We basically run a Chain of Responsibility here. At first we try to parse the whole specifier as one Atom.
    /// If this fails, we assume it's a ConcatenatedExpression and proceed to create one of these.
    /// That works well until we encounter a non-escaped '|' outside of a CharacterClass. Then we know that we actually have an AlternativesExpression.
    /// This means we have to check what we got back and add it to a List of subexpressions to the AlternativesExpression. 
    /// We then proceed to the next alternative (ParseIntoConcatenatedExpression consumes the tokens it uses) and keep adding to our subexpressions.
    /// 
    /// Note that Atoms (or more specifically Groups) can request a Parse of their subexpressions. 
    /// Also note that TryParseAtom is responsible for grabbing an Atom <b>and</b> it's Quantifier.
    /// If there is no Quantifier following (either because the input is exhausted or there directly is the next atom) then we instead pair with `new Quantifier("")` 
    /// </summary>
    /// <param name="specifier">The full Regular Expression specifier to Parse</param>
    /// <returns>An IRegularExpression that encompasses the complete given specifier</returns>
    public static IRegularExpression Parse(string specifier)
    {
        IRegularExpression expression;
        // ByRef requires us to hack around here, because TryParseAsAtom doesn't fail when it doesn't consume the specifier anymore
        string specifierCopy = specifier;
        if (TryParseAsAtom(ref specifierCopy, out expression) && specifierCopy.Length == 0)
        {
            return expression;
        }
        List<IRegularExpression> subexpressions = new List<IRegularExpression>();
        while (specifier.Length != 0)
        {
            expression = ParseIntoConcatenatedExpression(ref specifier);
            // ! actually an AlternativesExpression
            if (specifier.Length != 0 || subexpressions.Count != 0)
            {
                // flatten hierarchy
                var parsedSubexpressions = (expression as ConcatenatedExpression).Subexpressions;
                if (parsedSubexpressions.Count == 1)
                {
                    expression = parsedSubexpressions[0];
                }
                subexpressions.Add(expression);
            }
        }
        return (subexpressions.Count == 0) ? expression : new AlternativesExpression(subexpressions);
    }
    /// <summary>
    /// Successively parses the complete specifer into Atoms and returns a ConcatenatedExpression after the specifier has been exhausted or a single '|' is encountered at the start of the remaining specifier.
    /// Note: this may fail to work if the last encountered token cannot be parsed into an Atom, but the remaining specifier has nonzero lenght
    /// </summary>
    /// <param name="specifier">The specifier to Parse into a concatenated expression</param>
    /// <returns>The ConcatenatedExpression resulting from parsing the given specifier, either completely or up to the first encountered '|'</returns>
    private static IRegularExpression ParseIntoConcatenatedExpression(ref string specifier)
    {
        List<IRegularExpression> subexpressions = new List<IRegularExpression>();
        string currentSpecifier = specifier;
        int oldSpecifierLength = currentSpecifier.Length + 1;
        while (currentSpecifier.Length > 0 && currentSpecifier.Length < oldSpecifierLength)
        {
            oldSpecifierLength = currentSpecifier.Length;
            IRegularExpression expression;
            // we actually have an AlternativesExpression, return the current status to Parse after updating the specifier
            if (currentSpecifier[0].Equals('|'))
            {
                specifier = currentSpecifier.Substring(1); // skip leading |
                return new ConcatenatedExpression(subexpressions);
            }
            if (TryParseAsAtom(ref currentSpecifier, out expression))
            {
                subexpressions.Add(expression);
            }
            else if (currentSpecifier.Length == oldSpecifierLength)
            {
                subexpressions.Add(new ErrorExpression(currentSpecifier.Substring(0, 1)));
                currentSpecifier = currentSpecifier.Substring(1);
            }
        }
        specifier = ""; // we've exhausted the specifier, tell Parse about it to prevent infinite looping
        return new ConcatenatedExpression(subexpressions);
    }

    private static readonly Regex groupWithQuantifier = new Regex("^" + Group.Pattern + Quantifier.Pattern + "?");
    private static readonly Regex characterClassWithQuantifier = new Regex("^" + CharacterClass.Pattern + Quantifier.Pattern + "?");
    private static readonly Regex literalWithQuantifier = new Regex("^" + Literal.Pattern + Quantifier.Pattern + "?");
    /// <summary>
    /// Tries to parse the given specifier into an Atom. For that all categories of Atoms are checked in the following order:
    ///  1. Group
    ///  2. Class
    ///  3. Literal
    /// When it succeeds, the given expression will be assigned a SingleAtomExpression containing the Atom and it's Quantifier.
    /// The parsed atom will be removed from the specifier and the method returns true. To check whether the complete specifier was an Atom, 
    /// one needs to examine the specifier after calling this method. If it was, the specifier is empty after calling.
    /// </summary>
    /// <param name="specifier">The specifier to extract the leading Atom out of. Will be shortened if an Atom was successfully extracted</param>
    /// <param name="expression">The resulting SingleAtomExpression</param>
    /// <returns>True, if an Atom could be extracted, false otherwise</returns>
    // Note: could be rewritten to not consume the specifier and instead return an integer specifying the consumed length of specifier. This would remove the by-ref passed string hack
    internal static bool TryParseAsAtom(ref string specifier, out IRegularExpression expression)
    {
        Match m = groupWithQuantifier.Match(specifier);
        if (m.Success)
        {
            string atom = m.Groups["expression"].Value;
            string quantifier = m.Groups["quantifier"].Value;
            specifier = specifier.Substring(atom.Length + 2 + quantifier.Length);
            expression = new SingleAtomExpression(new Group("("+atom+")"), new Quantifier(quantifier));
            return true;
        }
        m = characterClassWithQuantifier.Match(specifier);
        if (m.Success)
        {
            string atom = m.Groups["expression"].Value;
            string quantifier = m.Groups["quantifier"].Value;
            specifier = specifier.Substring(atom.Length + 2 + quantifier.Length);
            expression = new SingleAtomExpression(new CharacterClass("["+atom+"]"), new Quantifier(quantifier));
            return true;
        }
        m = literalWithQuantifier.Match(specifier);
        if (m.Success)
        {
            string atom = m.Groups["expression"].Value;
            string quantifier = m.Groups["quantifier"].Value;
            specifier = specifier.Substring(atom.Length + quantifier.Length);
            expression = new SingleAtomExpression(new Literal(atom), new Quantifier(quantifier));
            return true;
        }
        expression = null;
        return false;
    }
}

Do note that this class is packed into the same file (and namespace-declaration) as IRegularExpression.

Questions:

• Is this design obvious?
• Is the code maintainable?
• Could i18n be handled cleaner?

I am 100% sure this code works, because regular expressions are methodically simple, and I've verified a significant number of edge-cases in an extensive test-suite, that can be found alongside the code on github

Answer 1

Validation

A public method should validate its method parameters. It doesn't matter if it is only used inside one project like RubberDuck or if it is used by other projects or developers.

public CharacterClass(string specifier)
{
    Match m = Matcher.Match(specifier);  

here Matcher.Match() would throw an ArgumentNullException which I would throw as well if specifier would be null but if you throw it at your own validation you wouldn't expose that you use a Regex.

The same is true for the constructors of Group and Literal.

A bigger issue will come in RegularExpression.Parse(string) because here you are exposing internal details of your implementation. If the passed in specifier == null the stacktrace would contain that you have called a method named TryParseAsAtom() and that the exception had been thrown by calling the Regex.Match() method.

---

Regex

I don't know how often the Regexes are used but you should consider to use the overloaded constructor Regex(string, RegexOptions) so you could use the Compiled enum for the RegexOptions to have the regex compiled which will be faster if called often.

---

CharacterClass

public static readonly string Pattern = @"(?<!\\)\[(?<expression>.*?)(?<!\\)\]";
private static readonly Regex Matcher = new Regex("^" + Pattern + "$");

private readonly bool _inverseMatching;
public bool InverseMatching { get { return _inverseMatching; } }
private readonly IList<string> _characterSpecifiers;
public IList<string> CharacterSpecifiers { get { return _characterSpecifiers; } }
private readonly string _specifier;

Instead of adding a private backing field for your properties you could simply have a private set; which would read nicer like so

public static readonly string Pattern = @"(?<!\\)\[(?<expression>.*?)(?<!\\)\]";
private static readonly Regex Matcher = new Regex("^" + Pattern + "$");

public bool InverseMatching { get; private set; }
public IList<string> CharacterSpecifiers { get; private set; }
private readonly string _specifier;

If you are using C# 6 then you could get rid of the private set; all together which would make it nicer.

Maybe I would let the public IList<string> CharacterSpecifiers { get { return _characterSpecifiers; } } stay with a backing field but would return either as a ReadOnlyCollection<string> like so

public ReadOnlyCollection<string> CharacterSpecifiers { get { return _characterSpecifiers.AsReadOnly(); } }   

or at least would return a new List<string> like so

public IList<string> CharacterSpecifiers { get { return new List<string>(_characterSpecifiers); } } 

This prevents that items of the IList could be changed.

While we are speaking about properties, you should stick to one style. Right now you have single lined properties like above and also multi lined properties like

public string Specifier
{
    get
    {
        return _specifier;
    }
}  

---

Equals()

I avoid the is operator if I later on cast the object. The is operator just tries to cast the object to the desired type and returns true if it can be casted. So a softcast using as and a null check is doing the same but involves less casting like so

public override bool Equals(object obj)
{
    var item = obj as CharacterClass
    if (item != null)
    {
        return item._specifier.Equals(_specifier);
    }
    return false;
}

---

Quantifier constructor

if expression.Length == 0 you should return early following with the check expression.Length == 1 and returning early as well. This saves you one horizontal identation level which makes your code more readable like so

public Quantifier(string expression)
{
    if (expression.Length == 0)
    {
        Kind = QuantifierKind.None;
        MaximumMatches = 1;
        MinimumMatches = 1;
        return;
    }
    if (expression.Length == 1)
    {
        switch (expression[0])
        {
            case '*':
                MinimumMatches = 0;
                MaximumMatches = int.MaxValue;
                Kind = QuantifierKind.Wildcard;
                break;
            case '+':
                MinimumMatches = 1;
                MaximumMatches = int.MaxValue;
                Kind = QuantifierKind.Wildcard;
                break;
            case '?':
                MinimumMatches = 0;
                MaximumMatches = 1;
                Kind = QuantifierKind.Wildcard;
                break;
            default:
                throw new ArgumentException("Passed Quantifier String was not an allowed Quantifier");
        }
        return;
    }

    Kind = QuantifierKind.Expression;
    Match m = Matcher.Match(expression);
    if (!m.Success)
    {
        throw new ArgumentException(string.Format("Cannot extract a Quantifier from the expression {1}", expression));
    }
    int minimum;
    // shouldn't ever happen
    if (!int.TryParse(m.Groups["min"].Value, out minimum))
    {
        throw new ArgumentException("Cannot Parse Quantifier Expression into Range");
    }
    MinimumMatches = minimum;

    string maximumString = m.Groups["max"].Value; // drop the comma
    if (maximumString.Length > 1)
    {
        int maximum;
        // shouldn't ever happen
        if (!int.TryParse(maximumString.Substring(1), out maximum))
        {
            throw new ArgumentException("Cannot Parse Quantifier Expression into Range");
        }
        MaximumMatches = maximum;
    }
    else if (maximumString.Length == 1) // got a comma, so we're unbounded
    {
        MaximumMatches = int.MaxValue;
    }
    else // exact match, because no comma
    {
        MaximumMatches = minimum;
    }

}

I have replaced the expression.ToCharArray()[0] with just expression[0] as well.

We also could remove small code duplication if we preset some of the properties outside of the switch like so

if (expression.Length == 1)
{
    MinimumMatches = 0;
    MaximumMatches = int.MaxValue;
    Kind = QuantifierKind.Wildcard;

    switch (expression[0])
    {
        case '*':
            break;
        case '+':
            MinimumMatches = 1;
            break;
        case '?':
            MaximumMatches = 1;
            break;
        default:
            throw new ArgumentException("Passed Quantifier String was not an allowed Quantifier");
    }
    return;
}

Answer 2

Ridiculously Large Bug

Okay this is a tiny bit embarrassing, but apparently I'm an idiot.

Remember when I said I recently had this in CS class? Well apparently I hadn't been paying attention. In the slightest... Regular expressions have parentheses. To be syntactically valid, these parentheses need to be correctly balanced.

How this makes for a ridiculously large bug? For that we need to realize that Regular expressions can't recognize syntactically valid regular expressions. To determine whether partentheses in an arbitrary string are balanced, you need some way to count the opening and closing parens. That's simply not possible with regular expressions.

That leads to the "unfortunate" circumstance that the following regular expression is not correctly recognized by the Parser:

(a)(b)

BEHOLD! The true ridiculousness of the bug. This is not even remotely complicated an expression. It's just that this doesn't get dealt with correctly.

The solution is to do one of the following things:

• Rewrite the whole parser as a "recursive descent parser" (which is what I did in the end
• Use something like ANTLR (which conveniently is already in the project) to generate a parser that can deal with parenthesized expressions
• Change how groups are recognized (this may have been the easiest instant fix)

The following is how groups are now extracted:

    private static string DescendGroup(string specifier)
    {
        int length = 0;
        int openingCount = 0;
        bool escapeToggle = false;
        foreach (var digit in specifier) 
        {
            if (digit == '(' && !escapeToggle)
            {
                openingCount++;
                escapeToggle = false;
            }
            if (digit == ')' && !escapeToggle)
            {
                openingCount--;
                escapeToggle = false;
                if (openingCount <= 0)
                {
                    return openingCount == 0 ? specifier.Substring(0, length + 1) : "";
                }
            }
            if (digit == '\\')
            {
                escapeToggle = !escapeToggle;
            }
            length++;
        }
        return "";
    }

Minor additional corrections

While I was at this rewrite, I also extracted the Expressions and Atoms into dedicated files, which reduces the knowledge required to correctly deal with the project.

I also changed Group to no longer invoke the parser in it's constructor. That is tight coupling and not even really the job of Group.

Answer 3

Design Flaw:

  _quantifier = new Quantifier(string.Empty); // these are always exactly once. Quantifying happens through groups

This one in IRegularExpression is really, really smelly. Why is there a property that's only used for one special incarnation of IRegularExpression?

Move Quantifier from IRegularExpression into IAtom, where it's actually meaningful.

It might even be worth considering to have IAtom extend IRegularExpression. This goes better in line with the inductive definition of RegularExpressions you may know from CS Theory classes.

new Quantifier("");

well ... this could be semantically more meaningful as something like this:

Quantifier.None

This is a bit more in line with things like string.Empty, IEnumerable.Empty() and generally all "Null-Object-Patterns"

Missing localization

In the Quantifier constructor the error messages are not localized. Since this must critically support i18n, why is that the case?