Make your own minicompiler (aka parser) on the Web in Plain English (Calculator with C++)

Welcome to Dragon World! — if you get it, you’re my hero :).

You’re going to learn to make your own compiler on the Web, indeed C++ and WebAssembly are the bread and butter of your needs, and unsurprisingly JavaScript, HTML, and CSS too.

Your chiefly goal is a calculator that evaluates ordinary expressions you type in ’cause you want to go into shape and acquaintance. An outward step career is writing a simple calculator; it shed light on programming techniques, compilers, and the theory of computation. By the way, my muse is Programming — Principles and Practice Using C++ by Stroustrup. So, let’s do it.

Demo

GitHub

Please checkout dependencies on GitHub.

Use cases

Since user experience is first and given users want a buttonless calculator, your calculator gotta receive infix expressions and return the result, but which expressions are your concern? Operators your calculator admitted are $+,-,*,/,\%,**$ on usual operator precedence.

If you enter 2+3.1*4 the program should respond 14.4

If you enter 2+4/2 the program should respond 4

If you enter 2+3%3 the program should respond 2

A complex expression. (2%5)*(-10/00000001.100000000)+4!*e

Local server and production hosting service

I’ve chosen Firebase hosting since I’m able to set up wasm files (WebAssembly compiled files) easier than other services such as Vercel or Netlfy, but you can deploy the project to them. We don’t really do more than it.

Whatever hosting service you choose, you should set up wasm file headers such that the server responds them as application/wasm, it must be not plain text format or another one.

"headers": [ 
     {
    	 "source": "**/*.@(wasm)",
    	 "headers": [ 
         {
      		"key": "Content-Type",
      		"value": "application/wasm"
    		 } 
	     ]
  	 } 
]

Example’s code

In your localhost, use make start it starts a Firebase local server with previous settings.

Download nanolib and compile your calculator.cpp

Your project needs [nanolib](<https://github.com/PetterS/clang-wasm>) since Clang is enough for you. Compile the simplest file to work. Checkout this empty commit.

#include "nanolibc/libc.h"
#include "nanolibc/libc_extra.h"
#define WASM_EXPORT __attribute__((visibility("default"))) extern "C"
WASM_EXPORT char* allocateMemoryForString(int size) {
	return new char[size];
}
WASM_EXPORT void freeMemoryForString(char* str) {
	delete[] str;
}
WASM_EXPORT double calculate(const char* expression) {
	return 0;
}

Compile your project with make

make

Since Makefile is not chiefly concern you must be ignored it.

Start localhost

make start

User interface and scripts

I won’t talk deeply about Tailwind. If you would do a simple form, you’re OK.

<form>
   <input id="calculator">
</form>
<span id="result" ></span>

But you must link form and your calculator; it should call your C++ code when the users changes their input.

<script type="module">
		document.getElementById("calculator").addEventListener('input', function (evt) {
		     // This call your C++ code.
		});
</script>

And, of course, you want to instantiate your wasm file.

const calculator = await (async (url) => {
			const { instance } = await WebAssembly.instantiateStreaming(fetch(url), importObject);
			return instance;
})("calculator.wasm");

Bad news! The C++ WASM module has its own memory and it only accepts numbers, but you need to share the memory with JavaScript and pass an expression to your function. The good news is that JavaScript’s standard, built-in objects included an encoder, your expression is allocated in a heap using a pointer that is passed to your function, and you free memory afterward such that you won’t fill up memory. For us, it is enough explanation but if you want to know more, I would recommend you to understand memory management.

// It encodes your input.
const expression = encoder.encode(evt.target.value + "\\x00");
// It allocates enough space in the heap, and also it returns a pointer to heap.
const pointer = calculator.exports.allocateMemoryForString(expression.length + 1);
// It sets the encoding expression in the heap.
const memory = new Uint8Array(calculator.exports.memory.buffer);
memory.subarray(pointer).set(expression);
// It evaluates your expression where the pointer refers to it.
calculator.exports.calculate(pointer);
// It frees memory
calculator.exports.freeMemoryForString(pointer);

Example’s code

Our deal arises about building a fulfill calculator

At least 70 years before, people invented compilers in order to take symbolic input from a keyboard because these problems are tricky when you don’t have the theory, but don’t worry I promise you it is not a lot. Remember, if someone ignores good standard answers with no piece of evidence, she/he is a moron.

The answer to your problem is “free context grammar”; it solves significant challenges in formal languages. Your calculator project doesn’t need a full theory, so you may ignore some details. Grammar describes a language in a compact way.

For example, a simple English sentence

You fly : Subject Verb

So, its grammar is

Sentence := Subject Verb

This representation way is called the Backus-Naur form.

Our arithmetic expressions with precedence rules are

2+2*2 : Number+Number*Number : Number + Rule1 : Rule0: Expression
1-2-3 : Number-Number-Number : Number-Rule0 : Rule0 : Expression
(2+2)/2= : (Expression)/Number : (Number+Number)/Number : Expression

their grammar is

Expression := OperatorPrecedenceLevel0
OperatorPrecedenceLevel0 :=
	OperatorPrecedenceLevel1|
  OperatorPrecedenceLevel0 "+" OperatorPrecedenceLevel1|
  OperatorPrecedenceLevel0 "-" OperatorPrecedenceLevel1|
OperatorPrecedenceLevel1 :=
  OperatorPrecedenceLevel1|
  OperatorPrecedenceLevel1 "*" OperatorPrecedenceLevel2|
  OperatorPrecedenceLevel1 "/" OperatorPrecedenceLevel2|
  OperatorPrecedenceLevel1 "%" OperatorPrecedenceLevel2|
OperatorPrecedenceLevel2 :=
  Number|
  "(" Expression ")"
Number := Integer|Integer"."|Integer"."Integer
Integer := <Digit><Integer>|Digit
Digit := "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"

Your grammar increases operator precedence (it is grouped before) at new levels.

If you want to test grammar, you would like https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/

👉🏼 Warning. Stroustrup’s book doesn’t teach the number rule. He parses tokens with cin and cin.putback(). But you don’t have them, since nanolibc doesn’t. You’re programming a free interface calculator.

Turning grammar into code. A program called parser.

You turn grammar into code using the simplest way: writing each grammar rule in a function that evaluates tokens, starting with the first rule, and parsing quote symbols as tokens (sometimes they are called terminal symbols).

A full-fledged evaluator shed light on you:

https://github.com/sanchezcarlosjr/my-first-compiler-aka-calculator/blob/main/src/evaluator.cpp

Testing

If you like unit testing, you would like the Google Test framework for C++ code.

We’re going to make a test suite as follows:

https://github.com/sanchezcarlosjr/my-first-compiler-aka-calculator/blob/main/calculator_test.cc

Execute your tests with

make live_test

When you change calculator_test.cc or evaluator.cpp files “make” compiles them and shows results.

Exercises

It’s expected you don’t import any mathematics library.

1. Implement bitwise operations.
2. Implement max and min functions.
3. Implement the Fibonacci function.
4. Implement exponential function a**x. Hint: Newton-Rapshon method. You could implement sqrt, but it is a special case.
5. Implement trigonometric functions. Hint: Taylor theorem.
6. Implement a sort function.
7. Turn factorial to Gamma function.