You are browsing as a guest. Sign up (or log in) to start making projects!

mast

  • 8 Devlogs
  • 32 Total hours

Lexer + Parser for math.

Ship #1

I built a parser for mathematical expressions that turns math input into an abstract syntax tree. From there, you can do things like simplifying or differentiating the expression.

Learning about parsing methods was genuinely interesting — once I understood the theory behind lexing and parsing, implementation was fairly straightforward. After getting the basic parsing working, I wanted to build a simple web interface for it. Looking back, the interface ended up taking a lot more time than I expected.

During this project I learned a lot about compiler design and language theory as well as web development and application deployment. All in all I am quite happy with the result.

  • 8 devlogs
  • 32h
Try project → See source code →
Open comments for this post

9h 1m 44s logged

Finish Website

I added the following to the website

  1. Button for evaluation an expression
  2. Reload ast and LaTeX only if there is no input for 500ms
  3. Tutorial on the Home page to show all features
  4. Info page for additional information
  5. A footer with info about the build (commit, branch, time)
  6. Improve colors especially for light mode

I also noticed that my project can’t be cloned on windows because windows doesn’t allow * in filenames. I updated the filenames but old commits still can’t be checked out easily.

0
0
5
Open comments for this post

10h 13m 58s logged

New Website

Starting Over

I wasn’t happy with the website Claude generated for me, so instead of iterating on it further, I decided to build it myself from scratch.

Why SolidJS

I’m not a web dev. I’ve written JavaScript before, but never really worked with a framework on a personal project. For this one I picked SolidJS, for two reasons: I didn’t want to use React, and I’d heard Solid does similar things but better.

Building Everything From Scratch

One tradeoff with SolidJS became obvious fast: there’s no real ecosystem of UI libraries to lean on. Every component and every line of CSS in this project, I wrote myself.

Dev Setup

To make local development easier, I added a Dockerfile and a docker-compose setup.

What’s Left

The site isn’t finished yet. The main thing still missing is buttons for a few actions.

0
0
5
Open comments for this post

3h 2m 36s logged

Web demo

I wrote a small API for my project using FastAPI, then handed the code to Claude. After a few iterations, I had a fairly good looking web interface for interacting with my project.

I also experimented with making all tree nodes circular. It turns out circles grow very quickly as numbers get bigger, so keeping every circle the same size caused the text to overflow. Switching to ellipses solved this.

I also spent some time reducing the number of parentheses in the output to make it more readable.

0
0
4
Open comments for this post

2h 15m 16s logged

Differentiation

My math program can now symbolically compute the derivative of an expression.

Challenges

One tricky case was finding the derivative of x^x. Since x^x = e^(x*ln(x)), rewriting it in that form let the existing exponential and product rules handle it correctly.

Restrictions

Differentiation works well, but outputs aren’t always in the simplest form. Differentiating (x^2)/2, for instance, currently gives 0.5*2*x instead of the simplified x. Simplifying this is a lot harder than it looks at first because it is really hard to determine whether an action results in a simpler form or not.

Next up

I’ll pause the AST experiments here for now. There’s a lot more that could be done, but I want to make it demoable. Next step: a small web UI so people can try it out directly.

0
0
5
Open comments for this post

1h 53m 39s logged

Functions and Exponents

I’ve just added support for exponents and standard mathematical
functions, including sin, cos, tan, ln, log, and sqrt.

The implementation was fairly straightforward. The lexer simply
tokenizes the ^ character into a Power token. Extending the lexer
from there was just a matter of adding the token rule and implementing
the corresponding evaluation logic.

The Precedence Gotcha

I did run into one classic mathematical quirk with my parser rules.
Currently, -x^2 is parsed as (-x)^2 because the unary minus operator
mistakenly has higher precedence than the exponent. Standard
mathematical convention dictates it should be evaluated as -(x^2).
While I plan to fix this in the parser proper, the current workaround is
just to use explicit parentheses when writing negative exponents.

Next Up: Symbolic Differentiation

As a final step for this milestone, I want to implement symbolic
differentiation
utilizing the chain rule. This will allow the engine
to take simple expressions like x^2 or sin(2x) and automatically
differentiate them into 2*x and 2*cos(2x) respectively.

0
0
2
Open comments for this post

1h 8m 27s logged

Simplification

I added some trivial simplification rules to my math parser. It checks for simple rules like x+0 -> x or x+x -> 2x.

Of course, you could go way deeper on simplification. My current implementation can’t simplify 2*x + 3*x -> 5*x, since my rules only match syntactically identical terms, not terms that differ by a coefficient. To handle cases like this, you’d need some sort of term-collection method that groups like terms together before combining them.

You could also expand expressions first and then simplify, which would let the parser recognize things like (x+1)^2 - (x^2+2x+1) -> 0.

My simple rules won’t bring expressions into their absolute simplest form, and they certainly don’t produce a standardized form that lets you check two expressions for equality. But they do make the program’s output noticeably more readable.

0
0
2
Open comments for this post

59m 52s logged

Input evaluation

You can now evaluate inputs, e.g. (3+2)*6 outputs 30. This works by
recursively evaluating the AST nodes — operator precedence comes for free
from the tree structure.

All variables found in the input are collected, and the user is prompted
to assign a value to each one. This somewhat defeats the purpose of
variables for now, but it’s a stepping stone — variables become essential
once symbolic differentiation or a proper UI come into play.

0
0
2
Open comments for this post

3h 17m 4s logged

Lexing + Parising

For my math parser I implemented the lexer and the parser. The lexer splits the mathematical input into tokens. The recursive descent parser parses those tokens into an abstract syntax tree.

For me the most interesting part was learning about different parsing techniques which also tought me a lot about compilers.

Next up I will implement the evaluation of expressions to calculate inputs like 2 + 3 * 5. Due to the design of the tree it should already respect pemdas.

0
0
15

Delete project?

Are you sure you want to permanently delete this project? This action cannot be undone.

All devlogs, followers, and associated data will be removed.

Followers

Loading…