# Optimal string literal tokenizing algorithm

I have a tokenizer, where one of the token types happens to be a C# string type. It takes a TextReader as its input, which is created from a StringReader, and it needs to support the basic stuff C# strings supports, such as "jo dude", "joe \"dudes\"", "this is a backslash \\ token" and of course "this is carriage return \r\nthis is next line"

Currently my method looks like this;

private string ReadSingleLineStringLiteral ()
{
StringBuilder buffer = new StringBuilder ();
while (nextChar != -1) {
buffer.Append ((char)nextChar);
if (nextChar == '"' &&
(buffer.Length == 1 ||
buffer [buffer.Length - 1] != '\\' ||
(buffer.Length - buffer.ToString ().TrimEnd ('\\').Length) % 2 == 0)) {
break;
}
}
if (buffer [buffer.Length - 1] != '"')
throw new ArgumentException ("unclosed string literal in hyperlisp file");
return buffer.ToString ().Substring (0, buffer.Length - 1)
.Replace ("\n", "\r\n") // normalizing carriage returns
.Replace ("\r\r\n", "\r\n")
.Replace ("\\\"", "\"")
.Replace ("\\\\", "\\");
}


It works I think, however, I suspect this is far from optimal, among other things, I hate that buffer.ToString ().TrimEnd ('\\').Length) % 2 part of it.

The _reader is the TextReader object, that at the entry of my methods are at the first character within the content of my string literal.

Can anyone figure out the optimal solution for parsing a C# type of string literal, and optimize my method?

Please don't tell me to use some library, since I don't want to bring in the overhead of any libraries to perform a task I think should be easily possible to implement with some 10-20 lines of code.

For bonus points, I'd love to also have a solution to my "multiline string literal algo" too. This method should read string the same way C# reads them when given @"some string". Currently it looks like this:

private string ReadMultiLineStringLiteral ()
{
StringBuilder buffer = new StringBuilder ();
while (nextChar != -1) {
buffer.Append ((char)nextChar);
if (nextChar != '"' && (buffer.Length - buffer.ToString ().TrimEnd ('"').Length) % 2 == 1)
break;
}
if (buffer.Length == 0 || buffer [buffer.Length - 1] != '"')
throw new ArgumentException ("unclosed multiline string literal in hyperlisp close to end of hyperlisp");
return buffer.ToString ().Substring (0, buffer.Length - 1)
.Replace (@"""""", @"""")
.Replace ("\n", "\r\n") // normalizing carriage returns
.Replace ("\r\r\n", "\r\n");
}


Both methods starts on the first character of the actual string content, e.g. for string @"xyz" the multiline method has the TextReader reader position being at "x", for string "abc" the singleline string literal method has the reader position being at "a".

This is probably unnecessary to say, but obviously Regex is a no-no.

• Please provide us with some test cases (input and desired output) for your methods. – Dmitry Nov 23 '14 at 21:31
• This doesn't work on your second example, "joe \"dudes\"". It returns "joe \". Code is on ideone. – mjolka Nov 23 '14 at 22:45
• "jo dude" should return; jo dude "joe \"dudes\"" should return; joe "dudes" "this is a backslash \\ token" should return; this is a backslash \ token basically they're supposed to mimic the behavior of C# strings, more or less. with the latter version taking an @ sign, it is supposed to mimic the behavior of @"" C# strings I don't know how to provide better examples than that ...? @mjolka - oops ... bug in code, thx. Anyway, the same problem still remains the same. – Imam Isa Nov 23 '14 at 23:29

A rule of thumb for performance in C# is to avoid allocations. In this case, we should try to remove buffer.ToString ().TrimEnd ('\\'), as well as the calls to Substring and Replace that appear at the end.

Of course you need to set performance goals and profile the code yourself on realistic input. Single line strings can reasonably be expected to be quite short (say 200 chars?), so what you have already might be performant enough, but I'll illustrate an alternative way.

First let's make this a static method so it will be easier to unit test. As I mentioned in the comments, there's a bug in the code -- unit testing can help you catch such bugs.

private static string ReadSingleLineStringLiteral(TextReader reader)


And a convenience method for testing

private static string ReadSingleLineStringLiteral(string line)
{
{
}
}


Now let's just handle the simple case, where there are no escape characters. Let's write some unit tests

Assert.AreEqual("", ReadSingleLineStringLiteral("\""));


And write the simplest thing that gets them to pass

var sb = new StringBuilder();
{
switch (c)
{
case '"':
return sb.ToString();
default:
sb.Append((char)c);
break;
}
}

throw new ArgumentException("Unexpected end of input");


Single line strings shouldn't contain new lines, so let's add a new test case

Assert.Throws<ArgumentException>(() => ReadSingleLineStringLiteral("\n\""));


And a matching case to our method

    switch (c)
{
case '"':
return sb.ToString();
case '\n':
throw new ArgumentException("Single line string contains new line");
default:
sb.Append((char)c);
break;
}


Now let's move on to escape sequences.

Assert.AreEqual("jo \"dude\"", ReadSingleLineStringLiteral("jo \\\"dude\\\"\""));
Assert.AreEqual("this is a backslash \\ token", ReadSingleLineStringLiteral("this is a backslash \\\\ token\""));
Assert.AreEqual("this is a carriage return \r\nthis is next line", ReadSingleLineStringLiteral("this is a carriage return \\r\\nthis is next line\""));


    switch (c)
{
case '"':
return sb.ToString();
case '\\':
break;
case '\n':
throw new ArgumentException("Single line string contains new line");
default:
sb.Append((char)c);
break;
}


And the corresponding method

private static void AppendEscapeCharacter(TextReader reader, StringBuilder sb)
{
switch (c)
{
case -1:
throw new ArgumentException("Unexpected end of input");
case '"':
case '\'':
case '\\':
sb.Append((char)c);
break;
case 'n':
sb.Append('\n');
break;
case 'r':
sb.Append('\r');
break;
default:
throw new ArgumentException(string.Format("Invalid escape sequence '\\{0}'", (char)c));
}
}


There are more cases to handle, but this should be enough to get you started.

• your code was almost perfect, and highly likely performing a gazillion times better than what I originally created. one tiny detail though, since I don't need escape sequence for single quotes, I dropped the case '\'' part, since my strings can only be created using double quotes anyway. also I need "normalizing" logic of cr/lf, meaning \n becomes transformed to \r\n when read. if you wish to see the end result I ended up with, you can check it out here, line 178; github.com/polterguy/phosphorus-five/blob/master/plugins/… - Thank You Sir :) – Imam Isa Nov 24 '14 at 10:21
• btw, @mjolka i also rewrote the multiline tokenizer logic in the spirit of your suggestion, it can be found at the same link, line 229. ps, loved your for loop :D – Imam Isa Nov 24 '14 at 10:49
• @ImamIsa glad I could help :) I finally tracked down Roslyn's code for lexing string literals which may be of interest to you. – mjolka Nov 25 '14 at 0:11
• Thanks yet again @mjolka :) - I've seen that code before, and unfortunately it's too complex [and long] to be of any particular use for me. Besides, your solution is better I think ... ;) But if you have a list laying somewhere about all the different escape characters I need to support in my "single line literal parser" logic, I'd love to see it. Probably a list of all the escape characters C# supports would do. Though anyway, thx for a brilliant solution. Your "for loop" deserves a medal btw ... ;) – Imam Isa Nov 25 '14 at 8:33
• ps, I've started using Unit Tests now, and I've got tons of different tests testing the different permutations ... – Imam Isa Nov 25 '14 at 8:33