Strings to array

Question

I've written a simple text tokenizer in JavaScript which works in my specific case, but I do not think it is maintainable (for example, if the requirement ever changed to allow newlines when surrounded by double quotes). How can I simplify the algorithm or abstract it better?

It should:

• strip out single-line comments (lines which begin with #)
• discard empty and whitespace-only tokens, except in the case where they are inside double quotes
• throw an error when there is an odd number of double quotes in the input

Example input:

# a "comment" with special characters
example 1

    "with multiple spaces" "    kept only inside double quotes"    and     not  outside
"side-by-side""double quotes without space in between""count as separate tokens"

Example output:

[
  "example",
  "1",
  "with multiple spaces",
  "    kept only inside double quotes",
  "and",
  "not",
  "outside",
  "side-by-side",
  "double quotes without space in between",
  "count as separate tokens"
]

A different approach I thought of instead of going through character-by-character is to use regular expressions (comments: ^#.*, quoted tokens: ".*", unquoted tokens: [^ ]+, token separators: \s).

const logTokens = (id) => console.log(parseTokens(id));

const parseTokens = (id) => {
  const input = document.getElementById(id).value;

  const tokens = [];

  var tokenBuffer = "";
  var insideDoubleQuote = false;
  var insideComment = false;

  for (const c of input) {
    // single-line comments end at EOF and upon new line
    if (insideComment) {
      if (c === "\n") {
        insideComment = false;
      }

      continue;
    }

    switch (c) {
      // single-line comments start with a "#"
      case "#":
        // single-line comments can only occur at the start of the line (token buffer empty)
        if (tokenBuffer === "") {
          insideComment = true;
        }
        break;

      case " ":
      case "\n":
        if (insideDoubleQuote) {
          if (c === "\n") {
            throw new Error("unterminated double quote");
          }

          // spaces inside double quotes should be kept (example: "this is a single token")
          tokenBuffer += c;
          break;
        }

        // ignore empty and whitespace-only tokens
        if (tokenBuffer.trim() !== "") {
          tokens.push(tokenBuffer);
        }

        // start next token
        tokenBuffer = "";
        break;

        // double quotes are not part of tokens
      case '"':
        // upon a matching double quote, it signifies the end of a token
        // this is the only case where empty and whitespace-only tokens are possible (i.e., "" and "  ")
        if (insideDoubleQuote) {
          tokens.push(tokenBuffer);

          // start next token
          tokenBuffer = "";
        }

        insideDoubleQuote = !insideDoubleQuote;

        break;

        // all other characters have no special meaning and are part of tokens
      default:
        tokenBuffer += c;
        break;
    }
  }

  if (insideDoubleQuote) {
    throw new Error("unterminated double quote");
  }

  // handle the case when the last line does not have a trailing newline
  if (tokenBuffer.trim() !== "") {
    tokens.push(tokenBuffer);
  }

  return tokens;
};

button,
textarea {
  box-sizing: border-box;
  width: 100%;
}

<textarea id="input" rows=10>
# a "comment" with special characters
example 1

    "with multiple spaces" "    kept only inside double quotes"    and     not  outside
"side-by-side""double quotes without space in between""count as separate tokens"
</textarea>
<button onclick="logTokens('input');">parse</button>

Answer 1

Firstly, I'd suggest separating your tokens from the parser completely. Create a new file, tokens.js and do something like:

export const SL_COMMENT = "#";
export const NEWLINE = "\n";
export const CRLF = "\r\n";
export const DOUBLE_QUOTE = '"';

You could do this in the same file if you choose but the separation makes natural sense to me.

Then in your parser.js import them like:

const { SL_COMMENT, NEWLINE, DOUBLE_QUOTE } = require('./tokens.js');

Then for the Parser class, the signature could look something like:

class Parser {
    input;
    pos;        // current position in input
    readPos;    // current reading position
    ch;         // current character in examination
    insideComment; 
    insideDoubleQuotes;

    constructor(input) {
        this.input = input;
        this.pos = 0;
        this.readPos = 1;
        this.ch = this.input[this.pos];
    }
    reset(newInput) {
        this.input = newInput;
        this.pos = 0;
        this.readPos = 1;
        this.ch = this.input[this.pos];
        this.insideComment = false;
        this.insideDoubleQuotes = false;
    }

    nextTok() {
        if (this.readPos >= this.input.length) {
            // TODO: handle end of input conditions
        }

        this.pos = this.readPos;
        this.readPos++;

        this.ch = this.input[this.pos];

        switch (this.ch) {
            case SL_COMMENT:
                // TODO: Handle SL_COMMENT
            case NEWLINE:
                // TODO: Handle NEWLINE
            case CRLF:
                // TODO: Handle CRLF
            case DOUBLE_QUOTE:
                // TODO: handle DOUBLE_QUOTE
        }        
    }

    consumeWhitespace() {
        for (let i = this.readPos; i < this.input.length; i++) {
            // NOTE: there might be other types of whitespace you want to ignore
            if (this.ch === ' ' || this.ch === '\r\n' || this.ch == '\n') {
                this.readPos++; 
            } else {
                break;
            }
        }
    }
}

The benefit of the above approach is that you can avoid having to maintain your tokenBuffer variable and instead use JS string.Slice() inbuilt function to return shallow copies of the original string. It's more memory efficient than having a separate string that you grow and shrink repeatedly. Instead, you just use slow and fast "pointers" into the original string and return 1 shallow copy, instead of creating an intermediary string before creating the return string. This reduces heap allocations/reallocations and copies, which in turn reduces GC burden and overall clock cycles.

This also opens up opportunities to make pipelines, where you can do intermediary operations on each returned token. Using this, you could then have (for example) a Compressor class, which takes a Parser for it's constructor, then calls Parser.nextToken() inside it's own methods. Then that compressor class could feed into an encryptor class... and so on and so forth.

This architecture is also very testable. You can write a test function similar to:

function runTest(inputString, expectedTokens) {
    const p = new Parser(inputString);
    for (let i = 0; i < expectedTokens.length; i++) {
        assert(p.nextTok() === expectedTokens[i]);
    }
}

Answer 2

You're complaining about this code, and that's good, it's the first step to fixing it.

The essential difficulty is that when we're asked to write down the single responsibility for parse_tokens(), we can't. You eloquently summarized its actions as:

1. strip out single-line comments (/^#/)
2. throw an error when there is an odd number of double quotes
3. discard whitespace-only characters while tokenizing words, except in the case where they are inside double quotes

That sounds like three single-responsibility functions:

1. stripComment()
2. validateQuotes()
3. findTokens()

There's a fourth item wrapping all that: a loop which reads newline-delimited lines and emits non-empty tokens. Presumably we fail the entire input file if even a single line fails to pass quote validation.

In bash we might organize this as a pipeline of three filter processes. In python we might have co-routines yielding strings or lists to each other; many languages have similar idioms for this pattern. In a language like C we might need some tedious (result, err_status) tuples, or rely on a global like errno. In JS or any other language that supports throwing exceptions we can always rely on composition of functions:

tokens = findTokens(validateQuotes(stripComment(line)))

Note that this is a partial function. That is, we won't produce tokens in the case where validation fails, and that's good. The outer loop that reads lines should deal with exceptions appropriately, perhaps by simply letting them propagate up the call stack so a single error will fail the whole input file.

Now we're in a good position to add three separate unit tests to our automated test suite.