Command Tokenizer

Question

I've written some code to tokenize a command string into its tokens.

A token is either:

• A block of any non-whitespace characters
• A block of characters, which may include whitespace, wrapped in quotes

So, for the input:

This is some text "with information" quoted.

I'd expect the tokens:

• This
• is
• some
• text
• with information
• quoted.

The tokenizer

using System.Collections.Generic;
using System.Text.RegularExpressions;

namespace MudCore
{
    public static class CommandTokenizer
    {
        static Regex _pattern;

        static CommandTokenizer()
        {
            _pattern = new Regex(@"((\s*""(?<token>[^""]*)(""|$)\s*)|(\s*(?<token>[^\s""]+)\s*))*", RegexOptions.Compiled | RegexOptions.ExplicitCapture);
        }

        public static string[] Tokenise(string input)
        {
            List<string> matches = new List<string>();
            var match = _pattern.Match(input);

            if(match.Success)
            {
                    foreach(Capture capture in match.Groups["token"].Captures)
                    {
                        matches.Add(capture.Value);
                    }
            }
            return matches.ToArray();
        }
    }
}

The Tests

using MudCore;
using NUnit.Framework;

namespace MudCoreTests
{
    [TestFixture]
    public class CommandTokenizerTests
    {
        [Test]
        public void SingleWordBecomesSingleToken()
        {
            var tokens = CommandTokenizer.Tokenise("single");
            Assert.AreEqual(1, tokens.Length);
            Assert.AreEqual("single", tokens[0]);
        }

        [Test]
        public void MultipleWordsReturnMultipleTokens()
        {
            var tokens = CommandTokenizer.Tokenise("there are multiple tokens");
            Assert.AreEqual(4, tokens.Length);
            Assert.AreEqual("there", tokens[0]);
            Assert.AreEqual("are", tokens[1]);
            Assert.AreEqual("multiple", tokens[2]);
            Assert.AreEqual("tokens", tokens[3]);
        }

        [Test]
        public void LeadingSpacesIgnored()
        {
            var tokens = CommandTokenizer.Tokenise(" there are multiple tokens");
            Assert.AreEqual(4, tokens.Length);
            Assert.AreEqual("there", tokens[0]);
            Assert.AreEqual("are", tokens[1]);
            Assert.AreEqual("multiple", tokens[2]);
            Assert.AreEqual("tokens", tokens[3]);
        }

        [TestCase("There are \"some quoted tokens\" in the text", 
                  new string[] {
                      "There",
                      "are",
                      "some quoted tokens",
                      "in",
                      "the",
                      "text" }, "quoted in middle")]
        [TestCase("\"some quoted tokens\" There are in the text", 
                  new string[] {
                      "some quoted tokens",
                      "There",
                      "are",
                      "in",
                      "the",
                      "text" }, "quoted at start")]
        [TestCase(" \"some quoted tokens\" There are in the text",
                  new string[] {
                      "some quoted tokens",
                      "There",
                      "are",
                      "in",
                      "the",
                      "text" }, "space then quoted at start")]
        [TestCase("There are in the text \"some quoted tokens\"", 
                  new string[] {
                      "There",
                      "are",
                      "in",
                      "the",
                      "text",
                      "some quoted tokens" }, "quoted at end")]
        [TestCase("There \"are\" in the text \"some quoted tokens\"", 
                  new string[] {
                      "There",
                      "are",
                      "in",
                      "the",
                      "text",
                      "some quoted tokens" }, "multiple quotes")]
        [TestCase("There are in the text \"some quoted tokens, that have punctionation.  And other stuff\"", 
                  new string[] {
                      "There",
                      "are",
                      "in",
                      "the",
                      "text",
                      "some quoted tokens, that have punctionation.  And other stuff" }, "punctuation in quote")]
        [TestCase("There are, in the text \"some quoted tokens\".", 
                  new string[] {
                      "There",
                      "are,",
                      "in",
                      "the",
                      "text",
                      "some quoted tokens",
                      "." }, "punctuation outside of quotes")]
        [TestCase("; There are \"some quoted tokens\" in the text", 
                  new string[] {
                      ";",
                      "There",
                      "are",
                      "some quoted tokens",
                      "in",
                      "the",
                      "text" }, "semi-colon recognised")]
        [TestCase("\"Outer quote\" nested quote \"back out\" really out", 
                  new string[] {
                      "Outer quote",
                      "nested",
                      "quote",
                      "back out",
                      "really",
                      "out" }, "nested quote")]
        [TestCase("Mismatched quotes \"are ignored",
                  new string[]
                  {
                      "Mismatched",
                      "quotes",
                      "are ignored"}, "unclosed quotes run to end of line")]
        public void QuotedStringsTreatedAsSingleToken(string inputText, string[] expectedTokens, string testName)
        {
            var tokens = CommandTokenizer.Tokenise(inputText);

            Assert.AreEqual(expectedTokens.Length, tokens.Length, testName);
            for (var i = 0; i < expectedTokens.Length; i++)
            {
                Assert.AreEqual(expectedTokens[i], tokens[i], testName);
            }
        }

    }
}

It seems like this should be a fairly common task, so maybe there's a better approach I've missed. Is the regex legible / am I missing any optimisations? Or of course, any other feedback's welcome.

Answer 1

You can shorten your Tokenise method using LINQ

public static string[] Tokenise(string input)
{
    List<string> matches = new List<string>();
    var match = _pattern.Match(input);

    if (match.Success)
    {
         foreach (Capture capture in match.Groups["token"].Captures)

         {
             matches.Add(capture.Value);
         }
     }
     return matches.ToArray();
}

Can become

public static string[] Tokenise(string input)
{
    var match = _pattern.Match(input);
    if (match.Success)
    {
        return (from Capture capture in match.Groups["token"].Captures select capture.Value).ToArray();
    }
    return default(string[]);
}

Or even shorter with the ternary operator

public static string[] Tokenise(string input)
{
    var match = _pattern.Match(input);
    return match.Success
        ? (from Capture capture in match.Groups["token"].Captures select capture.Value).ToArray()
        : default(string[]);
}

But if performance concerns you, you're better off with your own implementation instead of using regex, unless you are working with really long strings, in which case regex will probably win in performance.

I've made an alternative solution which works ~4 times faster than your regex version running 1,000,000 iterations with this string

"There are in the text \"some quoted tokens, that have punctionation. And other stuff\""

public static string[] Tokenise(string input)
{
    input = input.Trim();
    List<string> matches = new List<string>();
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < input.Length; i++)
    {
        if (input[i] == '"')
        {
            int nextQuoteIndex = input.IndexOf('"', i + 1);
            if (nextQuoteIndex != -1)
            {
                matches.Add(input.Substring(i + 1, nextQuoteIndex - i - 1));
                i = nextQuoteIndex;
            }
            else
            {
                matches.Add(input.Substring(i + 1, input.Length - i - 1));
                return matches.ToArray();
            }
        }
        else if (input[i] != ' ')
        {
            builder.Append(input[i]);
        }
        else if (builder.Length > 0)
        {
            matches.Add(builder.ToString());
            builder.Clear();
        }
    }
    if (builder.Length > 0)
    {
        matches.Add(builder.ToString());
    }
    return matches.ToArray();       
}

I will leave that here too

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

Jamie Zawinski