Build a WebAssembly Language for Fun and Profit: Parsing

1
“(“, “add”, “3”, “(“, “sub”, “2”, “1”, “)”, “)”

1
// src/types/ast.mts
2

3
export type IntNode = {
4
  type: "int";
5
  value: number;
6
};
7

8
export type FloatNode = {
9
  type: "float";
10
  value: number;
11
};
12

13
export type IdentifierNode = {
14
  type: "identifier";
15
  identifier: string;
16
};
17

18
export type TypedIdentifierNode = {
19
  type: "typed-identifier";
20
  // Note that here, we break down the identifier into its components
21
  identifier: string;
22
  typeIdentifier: string;
23
};

1
// src/types/ast.mts
2

3
export type BlockNode = {
4
  type: "block";
5
  expressions: AstNode[];
6
};

1
export type AstNode = IntNode | FloatNode | IdentifierNode | TypedIdentifierNode | BlockNode;

1
// src/types/index.mts
2
export * from "./token.mjs";
3
export * from "./ast.mjs";

1
// src/parser.mts
2
import {
3
  Token,
4
  IdentifierNode,
5
  TypedIdentifierNode,
6
  IdentifierToken,
7
  TypedIdentifierToken,
8
  FloatToken,
9
  FloatNode,
10
  IntToken,
11
  IntNode,
12
  AstNode,
13
  BlockNode,
14
} from "./types/index.mjs";

1
// src/parser.mts
2
export const parse = (tokens: Token[]): BlockNode => {
3
  const blocks: BlockNode[] = [];
4

5
  // This loop is run as long as there are tokens to consume
6
  while (tokens.length) {
7
    // consumeTokenTree converts an array of tokens into a tree of tokens, more on that later.
8
    const tree = consumeTokenTree(tokens);
9

10
    // parseBlock turns our new tree of tokens into an actual BlockNode, recursively. More on that later as well.
11
    blocks.push(parseBlock(tree));
12
  }
13

14
  // Finally we return the top level BlockNode
15
  return {
16
    type: "block",
17
    expressions: blocks,
18
  };
19
};

1
(add (sub 3 1) (sub 5 2))

1
// Note: I've simplified the Token format to just be strings to keep things short
2
["(", "add", "(", "sub", "3", "1", ")", "(", "sub", "5", "2", ")", ")"];

1
["add", [, "sub", "3", "1"], ["sub", "5", "2"]];

1
// src/parser.mts
2

3
// This is token besides for the bracket tokens
4
export type NonBracketToken = Exclude<Token, "parenthesis" | "square-bracket">;
5

6
// The token tree is made of NonBracketTokens and other TokenTrees
7
export type TokenTree = (NonBracketToken | TokenTree)[];
8

9
const consumeTokenTree = (tokens: Token[]): TokenTree => {
10
  const tree: TokenTree = [];
11

12
  // Ensures the first token is a left bracket and then discards it, defined below this function.
13
  consumeLeftBracket(tokens);
14

15
  while (tokens.length) {
16
    // Preview the next token
17
    const token = tokens[0];
18

19
    // Check to see if the next token is a left bracket.
20
    if (token.type === "bracket" && getBracketDirection(token) === "left") {
21
      // If it is, we just ran into a sub-TokenTree. So we can simply call this function within
22
      // itself. Gotta love recursion.
23
      tree.push(consumeTokenTree(tokens));
24
      continue;
25
    }
26

27
    // Check to see if the next token is a right bracket
28
    if (token.type === "bracket" && getBracketDirection(token) === "right") {
29
      // If it is, we just found the end of the tree on our current level
30
      tree.shift(); // Discard the right bracket
31
      break; // Break the loop
32
    }
33

34
    // If the token isn't a bracket, it can simply be added to the tree on this level
35
    tree.push(token);
36

37
    // Consume / discard the token from the main tokens array
38
    tokens.shift();
39
  }
40

41
  // Return the tree. Don't forget to check out the helper functions below!
42
  return tree;
43
};
44

45
const consumeLeftBracket = (tokens: Token[]) => {
46
  const bracketDirection = getBracketDirection(tokens[0]);
47

48
  if (bracketDirection !== "left") {
49
    throw new Error("Expected left bracket");
50
  }
51

52
  return tokens.shift();
53
};
54

55
const getBracketDirection = (token: Token): "left" | "right" => {
56
  if (token.type !== "bracket") {
57
    throw new Error(`Expected bracket, got ${token.type}`);
58
  }
59

60
  // If we match a left bracket return left
61
  if (/[\(\[]/.test(token.value)) return "left";
62

63
  // Otherwise return right
64
  return "right";
65
};

1
const parseBlock = (block?: TokenTree): BlockNode => {
2
  return {
3
    type: "block",
4
    // This is where the recursive magic happens
5
    expressions: block.map(parseExpression),
6
  };
7
};

1
const parseExpression = (expression?: TokenTree | NonBracketToken): AstNode => {
2
  // If the expression is an Array, we were passed another TokenTree, so we can
3
  // pass the expression back to the parseBlock function
4
  if (expression instanceof Array) {
5
    return parseBlock(expression);
6
  }
7

8
  // The mapping here is pretty straight forward. Match the token type and pass the
9
  // expression on to a more specific expression parser.
10
  if (isTokenType(expression, "identifier")) return parseIdentifier(expression);
11
  if (isTokenType(expression, "typed-identifier")) return parseTypedIdentifier(expression);
12
  if (isTokenType(expression, "float")) return parseFloatToken(expression);
13
  if (isTokenType(expression, "int")) return parseIntToken(expression);
14

15
  throw new Error(`Unrecognized expression ${JSON.stringify(expression)}`);
16
};

1
export const isTokenType = <T extends Token["type"]>(
2
  item: TokenTree | NonBracketToken | undefined,
3
  type: T
4
): item is Extract<Token, { type: T }> => {
5
  return isToken(item) && item.type === type;
6
};
7

8
const isToken = (item?: TokenTree | NonBracketToken): item is NonBracketToken => {
9
  return !(item instanceof Array);
10
};

1
const parseFloatToken = (float: FloatToken): FloatNode => ({ ...float });
2

3
const parseIntToken = (int: IntToken): IntNode => ({ ...int });
4

5
const parseIdentifier = (identifier: IdentifierToken): IdentifierNode => {
6
  return {
7
    type: "identifier",
8
    identifier: identifier.value,
9
  };
10
};

1
const parseTypedIdentifier = (identifier: TypedIdentifierToken): TypedIdentifierNode => {
2
  const vals = identifier.value.split(":");
3

4
  return {
5
    type: "typed-identifier",
6
    identifier: vals[0],
7
    typeIdentifier: vals[1],
8
  };
9
};

1
// src/index.mts
2
#!/usr/bin/env node
3
import { readFileSync } from "fs";
4
import { lex } from "./lexer.mjs";
5
import { parse } from "./parser.mjs";
6

7
const file = process.argv[2];
8
const input = readFileSync(file, "utf8");
9

10
const tokens = lex(input);
11
const ast = parse(tokens);
12
console.log(JSON.stringify(tokens, undefined, 2));

1
npx tsc
2
wispy example.wispy