PizzaScript Parser with RxGo — The Pyramid of Doom

<expr> ::= <operand> (("+" | "-" | "*" | "/") <operand>)*
<operand> ::= <num> | ("+" | "-") <operand>
<num> ::= <digit>+
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
➜ pizzascript ✗ go run main.go
Hello, alex! This is the PizzaScript programming language!
Feel free to type in commands
>> +1-2/2
0
>> +++2
2
>> ---2
-2

The Algorithm

// <expr> ::= <operand> (("+" | "-" | "*" | "/") <operand>)*
fun expr {
// in pizzascript parenthesis can be omitted in most cases
operand
while operator
operand
}
fun operator {
// take next token from input
next == "+" || next == "-" || next == "*" || next == "/"
}
fun next {
input[i + 1]
}
// rbp - right binding power
fun expr(rbp = 0) {
// null denotation
var left = nud(next())

while bp(peek()) > rbp
// left denotation
left = led(left, next())
left
}
fun nud(operator) {
node(operator)
}
fun led(left, operator) {
node(left, operator, expr(bp(operator))
}
  +
/ \
1 *
/ \
2 3
// and not *
/ \
+ 3
/ \
1 2
fun bp(operator) {
precendence[operator]
}
Operator precedence levels while parsing

Implementation Details & Problems

Node Type

The main parse expression

RxGo — Scan Operator

The Pyramid of Doom

pyramid of pizza
RxGo Reduce

Next Steps

--

--

--

Software engineer, instructor, mentor, and author of technical materials #JavaScript

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

How to Add a File Input Button and Display a Preview Image With React

I Made My First Open Source Contribution to Material-UI

LeetCode #994: Rotting Oranges Problem

Guide to Using Hooks in React Router

Build a Real-time Chat App with Vue 3, Socket.io and Nodejs

Tree Traversal with JavaScript

React Native 101: Build your first mobile app — React Native School

How to Set Up a Headless CMS in Under 5 Minutes

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Alex Korzhikov

Alex Korzhikov

Software engineer, instructor, mentor, and author of technical materials #JavaScript

More from Medium

How Golang DB migration tool work?

Binary Search in Go

Solving Leetcode Problems with Golang

Complete guide on Golang Control Structure