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:
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.
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:
SimpleAST
SimpleAST
are a list of nodes of any typeCallExpressionNode
can be any node.
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.
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.