Building A Tokenizer in Typescript
Tags: typescript, javascript, programming
Published: 2023-03-18 14:49:36

A tokenizer also known as a lexical analyzer, or lexer, in compiler design, is the first phase of the compiler. It is at this stage that the source code is scanned and broken down into a sequence of tokens. The tokens created by the tokenizer are usually designed according to the programming language's syntax being processed and they represent the basic building blocks of the language, such as keywords, identifiers, operators, and literals.

The primary function of the tokenizer in compiler design is to eliminate superfluous information from the source code and transform it into a format that is simpler for the compiler's later stages to process. It is here where Regular expressions, which specify the patterns for identifying the various sorts of tokens in the source code, are typically used to accomplish tokenization. The tokenizer may also handle white space and comments, detect errors, report them, and create symbol tables for the parser.

In this article, we are going to attempt to build a tokenizer function using Typescript! Our Tokenizer will try to tokenize a string of simple arithmetic procedures like addition, subtraction, division and multiplication, this can be used as part of a calculator program. A sample string would be `"2+2"` or `"2 * (2 + 4)"`

```typescript
const tokenRef = {
  number: /\d+/,
  operand: /[\+\-\*\/]/,
  openBracket: /\(/,
  closeBracket: /\)/,
} as const;
```

We create an object stores a group of regular expressions that would tokenize a mathematical phrase. The expression has different token kinds, including numbers, operators, and parentheses, this regular expressions are going to be used to identity specific tokens that matches our program definition.

```typescript
const types = {
  number: 'Number',
  operand: 'Operand',
  openBracket: 'OpenBracket',
  closeBracket: 'CloseBracket',
} as const;
```

The `types` object is used to provide more detail about the types of tokens that can be recognized by the tokenizer. It will be used to map the regular expressions used by the tokenizer in the `tokenRef` object to the specific token types that they represent. For example, the `number` regular expression will be mapped to the `Number` token type, the `operand` regular expression will be mapped to the `Operand` token type, and so on. Observe closely that the two objects have the same keys, we'll create a utility function that will help us get an array of the keys any object we pass to it since we are writing typescript.

```typescript
const objKeys = function <T extends Object>(obj: T): (keyof T)[] {
  return Object.keys(obj) as (keyof T)[];
};

```

We want the array to be strongly typed by infering the type of the keys to the items in the array.

```typescript
const ALLOWED_TOKENS = objKeys(tokenRef);

type token = {
  token: string;
  type: typeof ALLOWED_TYPES[number];
};

const ALLOWED_TYPES = [
  types.number,
  types.operand,
  types.closeBracket,
  types.openBracket,
] as const;
```
The `token` type is the type for a token object, the `ALLOWED_TYPES` constant is used to store an array of token types that the tokenizer will recognize. This provides a clear set of rules for the tokenizer to follow, allowing it to only recognize tokens of the specified types, let's write the function that will produce the tokens.

```typescript
const generateToken = function* (
  str: string
): Generator<{ token: string; type: typeof ALLOWED_TYPES[number] }> {
  const charArr = Array.from(str);
  let cursor: number = 0;
  const tokenKeys = objKeys(tokenRef);
  while (cursor !== charArr.length) {
    for (let i = 0; i < tokenKeys.length; i++) {
      if (tokenRef[tokenKeys[i]].test(charArr[cursor])) {
        yield { token: charArr[cursor], type: types[tokenKeys[i]] };
        cursor++;
      }
    }
  }
};
```

Our function above `generateToken` takes a string as an argument and returns a generator that yields the tokens of the string. The `tokenKeys` array contains the keys of the `tokenRef` object. The `types` object is then used to map the regular expressions to their specific token types. The `generateToken` function then iterates through the tokens of the string and tests them against the regular expressions for a particular. If a token matches one of the regular expressions, it is yielded with its associated token type. This allows the tokenizer to accurately tokenize a mathematical expression.

```typescript
const str = `2+2`;
let _tokens: token[] = [];
const tokenIterator = generateToken(str);
_tokens = [...tokenIterator];
console.log(_tokens);
/* [ 
  { token: '2', type: 'Number' },
  { token: '+', type: 'Operand' },
  { token: '2', type: 'Number' },
] */
```

We have successfully created a tokenizer function, however there are some drawbacks associated with our code, we can improve the efficiency of our code by adding an optimization that checks for overlapping regular expressions and prefers the longest matching expression. We can also add error handling to the `generateToken` function to ensure that it fails gracefully if an invalid token is encountered. Finally, we can add an optimization that allows the `generateToken` function to skip over tokens that have already been processed. These optimizations will help the tokenizer to be more accurate and efficient

See you in the next article where we'll optimize the tokenizer and move into the next stage of compiling.