DEV Community: LarmkaartDev

The parser (Part 1: Equations)

LarmkaartDev — Tue, 11 Jul 2023 16:33:56 +0000

The parser is a pretty complex component of the compiler. It will be responsible for converting the tokens into a format the Semantic analyzer can read and execute.

The parser will 'parse' all of the tokens the lexer generated. Parsing means that the parser will process the tokens and generate an Abstract Syntax Tree (AST) with them like described previously.

Let's see how the parser does this.

1. Equations

NOTE: In the following paragraph I'll be simplifying all tokens to just their Value properties, so if i write 1 + 2 i actually mean {"Value":"1","Type":"number"},{"Value":"+","Type":"operator"},{"Value":"2","Type":"number"}
This is just to make the entire example easier to follow.

Equations are pretty difficult to parse because you have to take order of operations in account. Instead of normal mathicmatical notation, the parser will make use of a clever notation called Postfix notation (click for more details). Postfix notation is a type of notation that gets rid of our order of operation problem. Instead of putting the operator between the terms, postfix will put it behind them.

For example the postfix notation will write

1 + 2 as 1 2 +

1 + 2 * 3 as 1 2 3 * +

(1 + 2) * 3 as 1 2 + 3 *

This notation might seem very confusing, but it will allow computers to calculate mathematical equations way quicker and easier.

To convert our standard notation into the postfix notation I will make use of the 'Shunting yard algorithm'. I won't go into details of implementation, but if you want to know more details and how to implement the algorithm, you should check out the Wikipedia page.

Now that we have the equation in postfix notation, we need to convert it into an AST so the Semantic analyzer will be able process and solve equation. for this I'll be using the following piece of code:

local queue = generatePostfix(tokens)

local function parsePostfix()
    local currentPostfixIndex = 1 -- current location in queue
    local operator = findNextOperator() -- find next operator

    while operator ~= nil do -- while there still exists an operator
        currentPostfixIndex -= 1 -- Look at the previous token
        local rhs = peekQueue(currentPostfixIndex) -- right hand side
        removeQueue(currentPostfixIndex) -- remove the processed token
        v -= 1 -- look at the previous token
        local lhs = peekQueue(currentPostfixIndex) -- left hand side
        removeQueue(currentPostfixIndex) -- remove the processed token

        local equation = {Type = "equation", Operator = operator.Value, Left = lhs, Right = rhs}

        if rhs.Type == "number" and lhs.Type == "number" then -- the equation only has numbers as terms?
            insertQueue(currentPostfixIndex, solveEquation(equation)) -- Insert the solved equation in the queue
        else
            insertQueue(currentPostfixIndex, equation) -- Insert the unsolved equationn in the queue
        end
        -- This is a quick optimisation so the Semantic analyzer doesn't have to calculate as much equations

        operator = findNextOperator() -- find the next operator
    end

    return queue
end

The code might seem a bit overwhelming at first so let's go through the code step by step parsing the equation
(1 + 2) * (3 + 4)
the equation in postfix notation will be
1 2 + 3 4 + *

Look for the next operator, in our case this will be + at index 3.
Put the previous token 2 in the right side of the equation
Put the previous token 1in the left side of the equation
Check if the equation is already solvabe, if so, put the result of the equation into the queue. Otherwise put the unsolved equation in the queue. The queue should now look like 3 3 4 + *.
repeat steps 1-4 untill no more operators are left. The entire equation should now be solved and the value in the queue should be 21
all that is left is to return the queue so the equation AST can be processed further.

Lets look a bit closer at step 5. in the first iteration the queue should be
3 3 4 + *
Now we iterate through step 1-4 again
3 7 *
one more time
21

Now we have succesfully solved the equation using the postfix notation!

The lexer

LarmkaartDev — Tue, 11 Jul 2023 16:32:34 +0000

The lexer is a surprisingly simple component of a compiler. It mainly consists of a bunch of if-statments. The lexer will break up the code in seperate lines and analyze them one by one.

1. Tokens

But before looking at the lexer, let's take a better look at tokens. A token is a very simple array that consists of a Type and a Value:
{ Type = TYPE_NAME, Value = TOKEN_VALUE }

The Type property describes the type of token like:

a statement
a number
a variable

The Value property can have different meanings depending on the type:

the statement type
the number value
the variable name

a token can have even more properties depending on the type.

2. The lexer

Let's see how the lexer will break down this example line into tokens:
var y = x + 2
I will use the string variable in the code examples to represent the part we are currently looking at.

the first part is var. We will insert a variable declaration token:

if string == "var" then
    pushTokens({Type = "statement", Value = "var"}) -- puts the token at the end of the tokens list
end

Now we have created our first token using the lexer!

Next up is y. This is a variable, but the lexer doesn't know this. Luckily, it is able to look at the previous token and see that it's a declaration, so it will add the y variable to the variable list.

if prevToken.Type == "statement" and prevToken.Value == "var" then -- the previous token declares a variable
    pushTokens({Type = "variable", Value = string}) -- put new token in the token list
    table.insert(localVariables, string) -- put new variable in the variable list
end

Next we have =. This is a simple case of adding a new token with Type assigner and value =:

pushTokens({Type = "assigner", Value = "="})

now the variable x. We will say we defined x earlier in the code somewhere, so the lexer already knows it's a variable. If it wasn't defined and the previous token is not a variable declaration token then the lexer should throw an error.

if table.find(localVariables, string) then -- A variable exist with name x?
    pushTokens({Type == "variable", Value = string}) -- Let's add it!
elseif prevToken.Type == "statement" and prevToken.Value == "var" then
    pushTokens({Type = "variable", Value = string})
    table.insert(localVariables, string)
else
    error("Unknown variable " .. string)
end

all thats's left are + and 2 these will be converted into these simple tokens:

{Type = "operator", Value = "+"}
{Type = "number", Value = "2"}

Now we have fully generated all of our tokens:

[Type = "statement", Value = "var"},
{Type = "variable", Value = "y"},
{Type = "assigner", Value = "="},
{Type = "variable", Value = "x"},
{Type = "operator", Value = "+"},
{Type = "number", Value = "2"}

This is a basic overview of the lexer. The more additions you add to your language, the complexer the lexer will become, so be sure to keep your code nice and tidy!

Creating a basic compiler - introduction

LarmkaartDev — Tue, 11 Jul 2023 15:10:49 +0000

For the past week I've been working on a game with a little compiler in Roblox Studio, I want to create a tool for beginners to help them get into coding. The compiler will make use of a high-level, Lua-like language. The goal of the game is to steer a little robot and make it do various tasks like navigating through a maze.

I've chosen Roblox Studio because of it's user-friendly nature. It will be easy for beginners to just start up the game and start coding! Roblox also handles most of the User interface by itself, so I will be able to focus more on coding the acutal logic. Another reason is that i already have a bunch of experience with Roblox Studio.

In this blog I want to focus on the journey of me creating my first ever compiler and explain my thought process. But before we start I want to make a few things clear:

Most of the code shown in this blog will be a simplification from the real code to make it easier to understand
Most of the code shown will be taken out of context
All code will be shown in either Luau, Roblox's main coding language, or my own language. additional comments will be provided whenever necessary
This compiler is made by me, it might differ from official methods
This series is still WIP. I am writing this while still working on the compiler, some things are bound to change. Feedback is greatly appreciated!

Now that that's out of the way, lets start!

Chapter 1: Main overview

You can make a compiler in a few different ways. For example a computer will convert Assembly language into Machine language and then execute it like its part of the code. In my approach I will be making use of an Abstract Syntax Tree (AST for short) I will explain more about this in a later chapter.

Now let's see a quick overview of my compiler!

1. The Lexer

The lexer, also known as a tokeniser, will convert the raw code input into tokens. Just like a sentence has words, each with a different function, each word in a line of code will have their own function.

Let's take the following line as example:
var y = x + 2

lets look at the functions of each part:
var is used to create a variable named y.
= is used to assign a value to y.
+ is used to add two values together.
x and y are variables and 2 is a number.

The lexer will go through all of the code like this and generate tokens which define the function of all parts of the code. The parser will be able to process these tokens further.

2. The Parser

The parser will take the previously described tokens and create an Abstract Syntax Tree (AST). An AST is an abstract repesentation of code. An AST repesentation of the previous example might look like this:

Using Semantic analysis the computer will be able to run the AST.

3. The Semantic analyzer

** WIP **

Chapter 2: Before starting

Before you start actually writing a compiler, there are a few things you should take care of.

1. Create a language description

Creating a description of the grammar of the language in a text file is an important thing to do before writing the compiler. This will provide a structure to your language and make coding it easier. The description should consist of a name, description and token repesentation. I will provide you with a part of my own description:

--------------------------] Types
number - any type of number                     { Type = number, Value = NUMBER_VALUE }
string - a string of text                       { Type = string, Value = STRING_VALUE }
variable -  an object with any type of value    { Type = variable, Value = VARIABLE_NAME }
equation - an equation                          { Type = equation, Operator = OPERATOR, Left = LHS, Right = RHS }

2. Create a comfortable work environment

Before creating the compiler you should make yourself a comfortable work environment. Create a basic code-editor and console, this will make debugging and working with the compiler much easier.

Now you should be ready to start working!