10
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ Or without regex with an Aggregate like in my similar question LINQish command line parser ;-) \$\endgroup\$
    – t3chb0t
    Dec 7, 2016 at 19:21
  • \$\begingroup\$ Your regex does not work if the input string starts with a white space. e.g.: " there are multiple tokens" \$\endgroup\$
    – JanDotNet
    Dec 12, 2016 at 20:03
  • \$\begingroup\$ @JanDotNet Fixed, feel free to point out any other gaping holes I've missed. \$\endgroup\$
    – forsvarir
    Dec 12, 2016 at 22:21
  • \$\begingroup\$ Unfortunately I don't think there is a nice/easy way to handle the delimited quotes problem using a Regular Expression. I have implemented something similar in the past in the form of CSV parser. If you use a stack to keep track of starting double quotes, then pop from the stack when you have found an ending quote. (Or just use a single field if you aren't using nesting) \$\endgroup\$
    – Mike Rocke
    Dec 12, 2016 at 22:42
  • \$\begingroup\$ @MikeRocke I almost tried to support nested quotes, but after thinking about it, I don't really need nested support. I'm just allowing quotes to be used to allow a token to contain spaces. \$\endgroup\$
    – forsvarir
    Dec 12, 2016 at 22:46

2 Answers 2

7
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the suggestions, I figured loops would probably be faster but went with regex initially to try and make it more expressive (although I don't think that was actually the end outcome). \$\endgroup\$
    – forsvarir
    Jan 4, 2017 at 12:05
  • \$\begingroup\$ Regex is hard to read and maintain for most people, short regular expressions are completely fine, but yours is a bit longer for me at least. \$\endgroup\$
    – Denis
    Jan 4, 2017 at 20:18
2
\$\begingroup\$

Tokenizer as configurable instance

Instead of static methods, a constructed tokenizer or parser could have benefits:

  • reused as instance
  • easier to configure

For example:

public class CommandTokenizer
{
    string _input;
    Regex _pattern;

    public CommandTokenizer(string input) // default pattern
    {
        this(input, new Regex(@"((\s*""(?<token>[^""]*)(""|$)\s*)|(\s*(?<token>[^\s""]+)\s*))*", RegexOptions.Compiled | RegexOptions.ExplicitCapture);
    }

    public CommandTokenizer(string input, Regex tokenCaptions) // configurable by overloaded constructor
    {
        _input = input; 
        _pattern = tokenCaptions;
    }

    public string[] Tokenize() // no arg; renamed for consistency: 's' to 'z" like in class-name 
    {
       // apply algorithm to field _input
    }
}

Improving tests: simplify assertion

There is a guiding principle "one assertion per test" that can be followed here:

  • instead of asserting both length and each element, assert expected elements (in order) using CollectionAssert AreEqual (in order) or AreEquivalent
[Test]
public void SingleWordBecomesSingleToken()
{
    var tokens = CommandTokenizer.Tokenise("single");
    CollectionAssert.AreEqual("single", tokens);
}

Alternative implementations

The regex is a bit hard to understand, at least for me (experienced with regular-expressions). But I know, that almost each general-purpose language has built-in String-tokenizer, libraries for CSV- and CommandLine parsing (which comes close to your solution).

Since I am not experienced with C#, I did a bit of research.

  1. C++'s boost is a String-tokenizer library with the concept of escaped_list_separator which allows to separate lists (e.g. enquoted sub-strings) as coherent token.
  2. Visual Basic's TextFieldParser operates on Streams (commonly used for file I/O) but recognizes quoted strings. See the docs
  3. C#'s StringTokenizer is designed as configurable object which does return an enumeration
  4. A similar SO-answer suggests a pretty simple regex-split for escaped-delimiters (like here space, there comma): Regex.Split(value, @"\s*\"",\s*");
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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