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

The content

React Native — Beautiful Horoscope App

Important Architecture Decisions for Your Angular Application

Introduction to JavaScript

How to host static website on Firebase hosting for free

Components in jQuery. Is it a dream?

Remove duplicate values from Javascript array — How to & Performance comparison

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

An OpenMP-inspired approach to parallelizing loops in Go

Golang Vs Python: Which Language Is Best for AI App Development

Golang Vs Python

Using assert in go tests