Simple Tokenizer + Parser

Question

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.

Answer 1

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.

Answer 2

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