What does it do?

The parser will take in the list of tokens from the previous section, and make a tree representation of the code.

This tree representation is what is called an Abstract Syntax Tree, and we will learn a lot about them in this entire learning endeavor. More about that here:

What is an AST?

The tree does a really good job at relating sections of the code to each other. For example, a "Function Call" node has a property called "arguments" which is a list of children nodes that represent the arguments the code is passing to a function when calling it.

Nodes in this tree also encompass more than a single token each, as it was the case in the Token section. Leaf nodes represent a single logical "unit" like a variable name, a number literal, or string literal, but other nodes can represent the whole program or entire expressions.

The Goal

Here is what the nodes in our tree will each look like:

interface NumberLiteralNode {
  type: "NumberLiteral";

  /** String representation of a number */
  value: string;
}

interface StringLiteralNode {
  type: "StringLiteral";

  value: string;
}

export interface CallExpressionNode {
  type: "CallExpression";

  /** Name of the calling function */
  name: string;

  params: (NumberLiteralNode | StringLiteralNode | CallExpressionNode)[];
}

/** Abstract Syntax Tree, the node tree after being parsed by the Parser */
export interface SimpleAST {
  type: "Program";

  body: (NumberLiteralNode | StringLiteralNode | CallExpressionNode)[];
}

/** Single Node, after being processed by the Parser */
export type ParserNode =
  | NumberLiteralNode
  | StringLiteralNode
  | CallExpressionNode
  | SimpleAST;

Where:

  1. The root node is a SimpleAST
  2. The children of a SimpleAST are a list of nodes of any type
  3. The arguments of a CallExpressionNode can be any node.
    1. However, in reality, there is only one SimpleAST node even though a ParserNode can be a SimpleAST.

As with the Tokens from the previous section, each node has a "type" property that identifies the node and properties that are dependent on the node. The "type" property will allow us to perform the correct action when we see any one node.

Example

We start with the Tokenizer output we got from the previous section, a list of Tokens

[
	{type: "paren", value: "("},
	{type: "name", value: "concat"},
	{type: "string", value: "Number: "},
	{type: "paren", value: "("},
	{type: "name", value: "add"},
	{type: "paren", value: "("},
	{type: "number", value: "2"},
	{type: "number", value: "3"},
	{type: "paren", value: ")"},
	{type: "paren", value: ")"},
]

Inside our parser, we will first define the new AST by declaring the root node and giving it an empty body:

const ast: SimpleAST = {
	type: "Program",
	body: []
};

We then go through the token list and process each node and add the results to the body property.