6
\$\begingroup\$

Requirements

A function is needed, that is able to parse a list of symbols with the following rules:

  • Symbols may be associated with numbers or not.
  • Numbers are defined by a comma separed list behind the symbol.
  • Numbers may be defined as range (e.g. 3-7 or also 7-3).
  • Whitespaces and invalid tokens should be ignored after token recognition finished.
  • Whitespaces are not needed as seperators.
  • The size / number of items to parse is not time critical.

Examples:

Available Symbols: ABC, CDE, A, B, C - A, B and C may be associated with numbers.

  • "ABC CDE A 1, 2 B" => [ABC], [CDE], [A{1,2}], [B].
  • "A1-4,6 CDE B C9-7,4,3" => [A{1,2,3,4,6}], [CDE], [B], [C{3,4,7,8,9}]
  • "ABCBCA5,4" => [ABC], [B], [C], [A{4,5}]

Approach

Yes, a parser is a little oversized for that kind of string analysis. However, it is very likely that the complexity of the syntax will grow in the course of time, so I decide to write a parse that scales better that regex or string operations.

The parsing process works in 2 steps.

  1. Split string in tokens (Symbols, Numbers, Separator ',', Range operator '-')
  2. Parse tokens to list of objects

Tokenizer

I created a general purpose regex based Tokenizer that produces a list of Token objects from an input string. Each token has a type (can be defined when creating the Tokenizer), an index (position of the token within the input string) and the actual value.

public class Token
{
    public Token(string type, string token, int index)
    {
        Value = token;
        Type = type;
        Index = index;
    }
    public string Value { get; private set; }
    public string Type { get; private set; }
    public int Index { get; private set; }
}

Usage of the tokenizer:

Tokenizer tokenizer = Tokenizer.Empty
        .WithToken(SYMBOL, "(ABC|CDE)")
        .WithToken(SYMBOL_AND_NUMBERS, "(A|B|C|D|E|F)")
        .WithToken(RANGE, "-")
        .WithToken(SEPARATOR, ",")
        .WithToken(NUMBER, "[0-9]+");

Token[] rokens = tokenizer.Parse("ABC B1,4-5");
// results in:
// Token (Value="ABC", Index=0, TYPE="SYMBOL")
// Token (Value="B", Index=4,   TYPE="SYMBOL_AND_NUMBERS")
// Token (Value="1", Index=5,   TYPE="NUMBER")
// Token (Value=",", Index=6,   TYPE="SEPARATOR")
// Token (Value="4", Index=7,   TYPE="NUMBER")
// Token (Value="-", Index=8,   TYPE="RANGE")
// Token (Value="5", Index=9,   TYPE="NUMBER")

Implementation of the Tokenizer:

public class Tokenizer
{
    private class TokenDefinition
    {
        private readonly Regex myRegex;
        public TokenDefinition(string type, string regex)
        {
            myRegex = new Regex(regex, RegexOptions.IgnoreCase | RegexOptions.Compiled);
            Type = type;
        }
        public string Type { get; set; }
        public MatchCollection Matches(string input)
        {
            return myRegex.Matches(input);
        }
    }

    private readonly List<TokenDefinition> myTokenDefinitions = new List<TokenDefinition>();

    public Tokenizer WithToken(string type, params string[] regexes)
    {
        foreach (var regex in regexes)
            myTokenDefinitions.Add(new TokenDefinition(type, regex));
        return this;
    }

    public Token[] Tokenize(string input)
    {
        if (input == null)
            input = string.Empty;

        var occupied = new bool[input.Length];

        return CollectTokens(input, occupied);
    }

    private Token[] CollectTokens(string input, bool[] occupied)
    {
        var tokens = new List<Token>();

        foreach (var tokenDefinition in myTokenDefinitions)
            foreach (var token in TokenizeInternal(input, occupied, tokenDefinition))
                tokens.Add(token);

        return tokens.OrderBy(t => t.Index).ToArray();
    }

    private static IEnumerable<Token> TokenizeInternal(string input, bool[] occupied, TokenDefinition tokenDefinition)
    {
        foreach (Match match in tokenDefinition.Matches(input))
        {
            if (!match.Success)
                continue;

            var indexRange = Enumerable.Range(match.Index, match.Length).ToList();
            if (indexRange.Any(idx => occupied[idx]))
                continue;

            indexRange.ForEach(idx => occupied[idx] = true);

            yield return new Token(tokenDefinition.Type, match.Value, match.Index);
        }
    }

    public static Tokenizer Empty
    {
        get { return new Tokenizer(); }
    }
}

Parser

The parser uses the Tokanizer internally and produces a list of ParserResult objects:

public class ParserResult
{
    public string Symbol { get; private set; }
    public int[] Numbers { get; private set; }

    public ParserResult(string symbol, params int[] numbers)
    {
        Symbol = symbol;
        Numbers = numbers.OrderBy(n => n).ToArray();
    }
}

The implementation of the Parser:

public class Parser
{
    public const string SYMBOL_WITH_NUMBERS = "SYMBOL_WITH_NUMBERS";
    public const string SYMBOL = "SYMBOL";
    public const string SEPARATOR = "SEPARATOR";
    public const string RANGE = "RANGE";
    public const string NUMBER = "NUMBER";

    private readonly Tokenizer myTokenizer;

    public Parser()
    {
        // note: first added token definitions have a higher prio (will be processed first).
        myTokenizer = Tokenizer.Empty
        .WithToken(SYMBOL, "(ABC|CDE)")
        .WithToken(SYMBOL_WITH_NUMBERS, "(A|B|C|D|E|F)")
        .WithToken(RANGE, "-")
        .WithToken(SEPARATOR, ",")
        .WithToken(NUMBER, "[0-9]+");
    }

    public IEnumerable<ParserResult> Parse(string input)
    {
        var tokens = myTokenizer.Tokenize(input);

        foreach (var result in ParseInternal(tokens).Where(r => r != null))
            yield return result;
    }

    private IEnumerable<ParserResult> ParseInternal(Token[] tokens)
    {
        var stack = new Stack<Token>();

        for (int i = 0; i < tokens.Length; i++)
        {
            Token current = tokens[i];

            switch (current.Type)
            {
                case NUMBER:
                    stack.Push(current);
                    break;
                case SYMBOL_WITH_NUMBERS:
                    if (stack.Count > 0)
                        yield return FromStack(stack);
                    stack.Push(current);
                    break;
                case RANGE:
                    stack.Push(current);
                    break;
                case SEPARATOR:
                    // nothing to do
                    break;
                case SYMBOL:
                    if (stack.Count > 0)
                        yield return FromStack(stack);
                    yield return new ParserResult(current.Value);
                    break;
                default:
                    throw new InvalidOperationException("Invalid type: '" + current.Type + "'");
            }
        }

        if (stack.Count > 0)
            yield return FromStack(stack);
    }

    private ParserResult FromStack(Stack<Token> stack)
    {
        var numbers = new List<int>();
        bool addRange = false;
        while (stack.Count > 0)
        {
            var token = stack.Pop();
            switch (token.Type)
            {
                case NUMBER:
                    AddNumber(numbers, int.Parse(token.Value), ref addRange);
                    break;
                case SYMBOL_WITH_NUMBERS:
                    return new ParserResult(token.Value, numbers.ToArray());
                case RANGE:
                    addRange = true;
                    break;
            }
        }

        return null;
    }

    private void AddNumber(List<int> numbers, int numberToAdd, ref bool addRange)
    {
        var last = addRange && numbers.Any() ? numbers.Last() : numberToAdd;
        var from = Math.Min(last, numberToAdd);
        var count = Math.Max(Math.Abs(last - numberToAdd), 1);
        foreach (var rangedNumberToAdd in Enumerable.Range(from, count))
            if (!numbers.Contains(rangedNumberToAdd))
                numbers.Add(rangedNumberToAdd);

        addRange = false;
    }
}

My first idea was to create a generic parser that can be configured (similar to the tokenizer), but that seems more difficult than thought. Therefore, I just created a specialized one for my problem. However I am not really happy with the implemention... so, all comments / suggestions for improvments are welcome.

\$\endgroup\$
  • 1
    \$\begingroup\$ Shouldn't "(ABC|DEF)" be rather "(ABC|CDE)"...? \$\endgroup\$ – CiaPan May 30 '16 at 10:31
  • 2
    \$\begingroup\$ "Whitespaces and invalid tokens should be ignored." So AB C and AB$C should both evaluate to [ABC], not [AB], [C], right? Does that currently work correctly? \$\endgroup\$ – Ben Aaronson May 30 '16 at 13:51
  • \$\begingroup\$ @BenAaronson: Good point.AB C and AB$C should both evaluate to [AB], [C]. Strictly speaking 'ignored' is not correct... "Whitespaces should be ignored after token recognition finished" describes it better. \$\endgroup\$ – JanDotNet May 30 '16 at 14:02
  • 1
    \$\begingroup\$ I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mathieu Guindon May 30 '16 at 18:21
  • 1
    \$\begingroup\$ It might seem like overkill right now, but I really recommend using a parser generator like Antlr for this. 1. It will force you to formalize your grammar. That process will flush out a lot of edge cases. 2. You seem to think that this grammar will evolve. It's much easier to evolve a grammar file than a homespun parser. \$\endgroup\$ – RubberDuck May 31 '16 at 0:47
5
\$\begingroup\$
  1. I don't like Empty property, as it makes things ambiguous. Is it safe to call Tokenizer.Empty.WithToken? Or will I modify some existing static field? Well I will have to go and check the implementation to know for sure. I would rather just call new Tokenizer().WithToken(...) instead. Or Tokenizer.Create().WithToken(...) if you have something against using default constructors.
  2. I think you should merge Tokenize and CollectTokens methods. It doesn't look like Tokenize does any meaningful work and you can easily declare bool array inside CollectTokens. Also since you already check for string being null, you might as well return early by calling:

    if(String.IsNullOrWhiteSpace(input)) return new Token[0];
    
  3. According to C# naming convention you should use PascalCase for constants (unless you are mirroring some external API which uses different naming convention). So It should be SymbolWithNumbers, etc. Also you might want to use enum instead of strings:

    enum TokenType
    {
        SymbolWithNumbers,
        Symbol,
        ...
    }
    
  4. my... prefix looks amateurish and adds this "hypothetical" flavor to your code. You should drop it.

  5. I think you can simplify things if you modify your range regex to look for "Number-Number" pattern (I'm sorry, I don't speak regex).

  6. You can use OOP to eliminate case operators.

For example:

interface ITokenParser
{
    bool TryParse(IList<Token> tokens, out ParserResult result);
}

class SymbolParser : ITokenParser
{
    public bool TryParse(IList<Token> tokens, out ParserResult result)
    {
        result = null;
        if (tokens.Count == 1 && tokens[0].Type == Parser.SYMBOL)
        {
            result = new ParserResult(tokens[0].Value);
            return true;
        }
        return false;
    }
}

The naive implementation of ParseInternal method might look like this:

private IEnumerable<ParserResult> ParseInternal(Token[] tokens)
{
    var stack = new List<Token>();
    var parsers = new ITokenParser[] {new SymbolParser(), ...};//implements other parsers

    foreach (var current in tokens)
    {
        stack.Add(current);
        foreach (var parser in parsers)
        {
            ParserResult result;
            if (parser.TryParse(stack, out result))
            {
                stack.Clear();
                yield return result;
                break;
            }
        }
    }
}

It just occurred to me though, that it won't quite work for numbers: for "A1,2" it will return "A[1]". So you'll need a more complex solution. You could add tokens to stack until you can no longer parse it, for example. And only when that happens you would yield last successful ParserResult and clear the stack. But there might be smarter way to do it, I'll think about it.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the great feedback! 1) good point (will be changed) 2) also a valid point. 3) I thought about it, but that would transform all classes into generic types (because the Tokenizer is used for other tasks also). 4) I like the my... prefix for instance variables... Why do you mean that it looks amateurish? ... brb \$\endgroup\$ – JanDotNet May 30 '16 at 14:47
  • \$\begingroup\$ Names should be descriptive. And while my prefix might mean something special for you, it does not describe the field in any way. it just makes the name longer. A common practice is to use underscores to mark fields, if that's what you are using my prefix for. For example, _tokenizer. My (or Your) prefix is something I would use to write a sample code on SO, along with Foo and Bar. That's probably why using those in production code feels weird. But maybe its just me. \$\endgroup\$ – Nikita B May 30 '16 at 15:06
  • \$\begingroup\$ 4.2) Ok, I am using my as prefix for instance variables in allmost all projects. So, it's interesting to see that it appears kind of 'amateurish' to other developers.6) That seems to be a better solution. It works fine if the tokens are iterated reverse for comma separated numbers. However, the ugly FromStack method remains for the range expressions. I am thinking about adding an another preprocessing step 'Expand' that removes all separator tokens and expands all range expressions to lists. \$\endgroup\$ – JanDotNet May 30 '16 at 16:48
  • \$\begingroup\$ @JanDotNet have you been programming in VB.NET before? That would explain why the my prefix because the this in VB.NET is called Me so if you switched the language you wouldn't need the prefix ;-) the my is also strange to me. Don't you know which variables are yours? Aren't they all yours? There aren't any other variables then mine so the prefix is unnecessary. \$\endgroup\$ – t3chb0t Jul 24 '16 at 0:24
  • \$\begingroup\$ @t3chb0t: No I didn't program VB.Net. There aren't any other variables then mine so the prefix is unnecessary: What about local variables which belong to the method and not to the class instance? What about static class variables that are shared by all instances? Actually it is just a special prefix for instance variables... '_' may be more common but I use 'my' because I have learned it that way ;) \$\endgroup\$ – JanDotNet Jul 24 '16 at 12:34
1
\$\begingroup\$

Bellow you'll find a revised version of the Parser class. It contains (inter alia) some refactoring proposals. Further more, all switch statments were removed. In return, I added another pre parsing step that prepares the list of tokens by removing seperators and expanding range expressions. Afterwards, the preprocessed token list will be parsed as proposed by Nikita B.

public class Parser
{
    public const string SYMBOL_AND_NUMBERS = "SYMBOL_AND_NUMBERS";
    public const string SYMBOL = "SYMBOL";
    public const string SEPARATOR = "SEPARATOR";
    public const string RANGE = "RANGE";
    public const string NUMBER = "NUMBER";

    private readonly Tokenizer myTokenizer = null;

    private readonly static ITokenParser[] theParsers = new ITokenParser[] { new SymbolParser(), new SymbolWithNumbersParser() };
    private readonly static IPreprocessor[] thePreprocessors = new IPreprocessor[] { new ExpandRangePreprocessor(), new RemoveSeparatorPreprocessor() };

    public Parser()
    {
        myTokenizer = Tokenizer.Create()
        .WithToken(SYMBOL, "(ABC|DEF)")
        .WithToken(SYMBOL_AND_NUMBERS, "(A|B|C|D|E|F)")
        .WithToken(RANGE, "-")
        .WithToken(SEPARATOR, ",")
        .WithToken(NUMBER, "[0-9]+");
    }

    private interface IPreprocessor
    {
        void Preprocess(LinkedListNode<Token> token);
        bool CanProcess(LinkedListNode<Token> token);
    }

    private class ExpandRangePreprocessor : IPreprocessor
    {
        public void Preprocess(LinkedListNode<Token> range)
        {
            var list = range.List;
            var num1 = int.Parse(range.Previous.Value.Value);
            var num2 = int.Parse(range.Next.Value.Value);
            var from = Math.Min(num1, num2);
            var to = from + Math.Abs(num1 - num2);

            for (int i = from + 1; i < to; i++)
                list.AddBefore(range, new Token(NUMBER, i.ToString(), -1));
            list.Remove(range);
        }

        public bool CanProcess(LinkedListNode<Token> token)
        {
            return token.Value.Type == RANGE &&
                   token.Previous.Value.Type == NUMBER &&
                   token.Next.Value.Type == NUMBER;
        }
    }

    private class RemoveSeparatorPreprocessor : IPreprocessor
    {
        public void Preprocess(LinkedListNode<Token> separator)
        {
            var list = separator.List;
            list.Remove(separator);
        }
        public bool CanProcess(LinkedListNode<Token> token)
        {
            return token.Value.Type == SEPARATOR;
        }
    }

    interface ITokenParser
    {
        bool TryParse(Stack<Token> tokens, out ParserResult result);
    }

    private class SymbolParser : ITokenParser
    {
        public bool TryParse(Stack<Token> tokens, out ParserResult result)
        {
            result = null;
            if (tokens.Count > 0 && tokens.Peek().Type == SYMBOL)
            {
                result = new ParserResult(tokens.Pop().Value);
                return true;
            }
            return false;
        }
    }

    private class SymbolWithNumbersParser : ITokenParser
    {
        public bool TryParse(Stack<Token> tokens, out ParserResult result)
        {
            result = null;
            if (tokens.Count > 0 && tokens.Peek().Type == SYMBOL_AND_NUMBERS)
            {
                var symbol = tokens.Pop().Value;
                var numbers = tokens.ToArray()
                    .Where(t => t.Type == NUMBER)
                    .Select(t => int.Parse(t.Value))
                    .Distinct()
                    .OrderBy(n => n).ToArray();
                result = new ParserResult(symbol, numbers);
                return true;
            }
            return false;
        }
    }

    public IEnumerable<ParserResult> Parse(string input)
    {
        if(String.IsNullOrWhiteSpace(input)) 
            yield break;

        var tokens = myTokenizer.Tokenize(input);

        tokens = Preprocess(tokens);

        foreach (var result in ParseInternal(tokens).Reverse())
            yield return result;
    }

    private IEnumerable<ParserResult> ParseInternal(Token[] tokens)
    {
        var result = (ParserResult)null;
        var stack = new Stack<Token>();
        foreach (var token in tokens.Reverse())
        {
            stack.Push(token);
            foreach (var parser in theParsers)
            {
                if (parser.TryParse(stack, out result))
                {
                    yield return result;
                    stack.Clear();
                    break;
                }
            }
        }
    }

    private Token[] Preprocess(Token[] tokens)
    {
        var list = new LinkedList<Token>(tokens);
        var item = list.First;
        do
        {
            // get next item before processing item
            var next = item.Next;
            foreach (var preprocessor in thePreprocessors.Where(p => p.CanProcess(item)))
                preprocessor.Preprocess(item);
            item = next;
        }
        while (item != null);

        return list.ToArray();
    }
}
\$\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.