ContactLog In

Start Routing Notifications Today!

Courier is a notification service that centralizes all of your templates and messaging channels in one place which increases visibility and reduces engineering time.



Build a WebAssembly Language for Fun and Profit: Parsing

Drew Youngwerth

August 25, 2022

In the last post of this series on how to build a WebAssembly programming language, we constructed a lexer. In this post, we’ll cover the next phase of our compiler, parsing. Parsing is the portion of our compiler that takes the token stream generated by the lexer and converts it into an abstract syntax tree (AST).

An AST is a tree-like data structure that organizes the tokens into a logical hierarchy that can more easily be translated into machine code. Thankfully, because wispy is an S-expression language, our code is essentially already an AST. Take the following stream of tokens:

Each set of parentheses represents a subtree, where the first token is the operator node and the following tokens are its operands. If we run into another opening parenthesis before the current set is closed, we know it represents an operand that itself is a subtree. The above stream of tokens would be organized into a tree that looks like this:

AST explanation

If you're interested in writing a parser for a more complex C-like syntax, see my previous Building A Programming Language series.

More About AST

As we did with the lexer, we'll start by defining our types. These types will define the structure of our AST. Each type represents a “Node”, the circle from our diagram in the intro. Here are the basic nodes. We'll gloss over them, as they aren't a lot different from the tokens we defined in the lexer:

A new concept to the AST is the BlockNode. A BlockNode is an expression made up of a group of other nodes.

For example, (add 1 2) is a block of three nodes:

  1. An identifier that evaluates to a function, add.
  2. An Int that simply evaluates to the number 1.
  3. An Int that simply evaluates to the number 2.

How the block itself gets evaluated is up to the compiler. We'll get to that in the next post.

Here's the definition:

Finally, we define the AstNode. Like the Token type from the lexer, AstNode is a discriminated union that can be one of any other node we previously defined:

You may have noticed that BlockNode has an array of AstNodes, Since AstNode can be a BlockNode, BlockNodes can contain child BlockNodes. In other words, BlockNode is a recursive type. This ability to recursively represent children that can have children is the foundation of our AST. It's where the tree in AST is allowed to form.

At this point src/types/ast.mts is finished and should look like this file.

Now export the types from src/types/index.mts as we did with the token types:

Constructing the AST

Now that we've defined the AST, it's time to build one.

Create a new src/parser.mts file and add all the imports we'll use:

Now we can define our top level parse function. The parse function takes the tokens generated by the lexer and returns a BlockNode that acts as our tree’s root.

Next we define the consumeTokenTree function. consumeTokenTree converts a flat array of tokens, into a tree of tokens.

Given this wispy expression:

The lexer will produce this array of tokens:

consumeTokenTree will take that flat array and turn it into a tree. This is as simple as putting every token in between a set of bracket tokens () into an array. So our token array from above becomes this token tree:

Here's the actual definition of consumeTokenTree:

Now that we have a token tree, we need to turn it into a block. To do so, we create a parseBlock function that takes the tree as its input and returns a BlockNode:

As you may have noticed, parseBlock maps each item of the tree with a yet to be written parseExpression function. parseExpression takes either a TokenTree or a NonBracketToken and transforms it to its corresponding AstNode type.

Here's the definition:

Let's define the isTokenType function. This function is pretty neat and demonstrates one of the most powerful features of TypeScript, custom type guards. Simply put, isTokenType tests the expression and narrows down the type to a specific TokenType. This allows TypeScript to be certain we are passing the correct tokens to their corresponding parser functions down the line.

Here's the definition:

There's a lot happening there, so let's walk through it. First up, we have a generic definition, <T extends Token["type"]>. This is essentially saying that T must be one of the possible values of the Token.type field. Typescript is smart enough to know that means T must be one of "int" | "float" | "identifier" | "typed-identifier" | "bracket.

The next interesting piece of code is the return type predicate item is Extract<Token, { type: T }>. This predicate tells TypeScript that if the return value of isTokenType is true, then item must be the Token whose type matches the string passed as the type parameter.

In practice that means that if we were to pass an unknown Token to isTokenType, typescript will be able to correctly narrow the value to a more specific token, like IntToken.

Now that we have our custom type guard defined, we can define the actual token parsers. The first three are simple; they essentially just return a copy or slightly modified copy of the token:

The final parser is the parseTypedIdentifier. Remember that a typed identifier takes the form identifier:type. Parsing it is as simple as splitting the string by the colon. The first value of the returned array is the identifier, the second is the type. Here's the definition:

Here’s the finished file

That's all the code required for a working parser. Before we move on, let's update the main src/index.mts file to view the output of the parser:

Build and run project:

If all goes well, the output should look like this.

With that, the parser is finished. We can now convert the stream of tokens from the lexer into an AST. In the next post, we can get into the juicy bits: generating and running machine-readable code.

Start Routing Notifications Today!

Courier is a notification service that centralizes all of your templates and messaging channels in one place which increases visibility and reduces engineering time.


More from Engineering


Simplifying notifications with the Courier iOS SDK

Push notifications are a valuable tool for keeping users informed and increasing their engagement with your app. You can use push notifications to alert users about promotions, new content, or any other important updates. While push notifications are a powerful tool, setting up push notifications in iOS can be a daunting task that requires a significant amount of effort and time. Fortunately, the Courier iOS Mobile Notifications Software Development Kit (SDK) simplifies this process.

Mike Miller

Mike Miller

March 23, 2023

Courier Android SDK thumbnail

Building Android push notifications with Firebase and Courier’s SDK

Push notifications have become an essential part of modern mobile apps, allowing you to keep your users engaged and informed. However, implementing push for different platforms can be a complex and time-consuming task, requiring developers to set up and handle token management, testing, and other logistical details.

Mike Miller

Mike Miller

March 21, 2023

Build your first notification in minutes

Send up to 10,000 notifications every month, for free.

Get started for free

Email & push notification

Build your first notification in minutes

Send up to 10,000 notifications every month, for free.

Get started for free

Email & push notification











API Status


© 2023 Courier. All rights reserved.