Skip to content
Tutorials Center
My learning

Topics

Lesson 121 of 134 ยท Projects

Project: Expression Calculator

Build a calculator in Ruby from scratch - a tokenizer, a recursive descent parser, an AST made of Data objects, a pattern-matching evaluator, variables, functions and good error messages.

What happens when you type 2 + 3 * 4 into a calculator and get 14, not 20? Somebody wrote a program that understands precedence: multiplication binds tighter than addition. In this project you will write that program yourself, in about 150 lines of modern Ruby. Along the way you will build the same three-stage pipeline that every programming language, template engine and query parser uses.

  1. Tokenizer (also called a lexer): turns the text "2 + 3 * 4" into a list of small pieces, the tokens: number, plus, number, times, number.
  2. Parser: reads the tokens and builds a tree that shows how they group. Here 3 * 4 becomes a branch of its own, and the addition sits above it.
  3. Evaluator: walks the tree from the leaves up and computes the value.

The tree is called an abstract syntax tree, or AST. We will build it from Data objects, take it apart with pattern matching, and report mistakes with custom exceptions. If any of those are unfamiliar, this is a good moment to skim them. Everything runs on this page, one stage at a time.

What the calculator will support

  • Numbers: 42, 3.14
  • Operators: + - * / % ^ (power), unary minus, and parentheses
  • Variables: x = 5, then x * 2
  • Functions: sqrt(16), max(1, 7, 3), round(3.14159, 2)
  • Clear errors with the position of the problem: unexpected "$" at position 4

The rules of the language, from loosest to tightest binding, are written as a grammar. Each line says "this is made of that":

TEXT
statement  := IDENT "=" expression | expression
expression := term (("+" | "-") term)*
term       := unary (("*" | "/" | "%") unary)*
unary      := "-" unary | power
power      := primary ("^" unary)?
primary    := NUMBER | IDENT | IDENT "(" arguments ")" | "(" expression ")"

Read it from the top. An expression is one or more terms joined by + or -. A term is one or more unary pieces joined by *, / or %. Because term sits inside expression, multiplication is grouped first: that single design decision is how precedence works. The * in the grammar means "repeat zero or more times", and each rule will become one Ruby method.

Step 1: the tokenizer

The tokenizer scans the string from left to right. At each position it tries a few regular expressions (Regular Expressions), takes the first that matches, records a token, and moves on. A token is just three facts: its type, its value, and where it started (so errors can point at it). A Data class is perfect for that.

Ruby Step 1: the tokenizer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Some details deserve attention. The regular expression for numbers, \d+(\.\d+)?, accepts 42 and 3.14 but not .5; adding that is one of the exercises at the end. The anchor \A means "at the very start of the string", so each attempt looks only at the current position. We append a special :eof (end of input) token, which saves the parser from constantly asking "are there tokens left?". And "4 + $" fails with an error that names the offending character and its position: good error messages are a feature you design in from the start.

Step 2: the tree, and an evaluator for it

Before writing the parser, let us look at what it will produce. The expression 2 + 3 * 4 becomes:

TEXT
Bin("+",
  Num(2),
  Bin("*", Num(3), Num(4)))

Each node is a small immutable value. The leaves are numbers and variables; the inner nodes are operations that hold their children. We define one Data class per kind of node, and an evaluator that uses a case/in to say what to do for each. Build one by hand, and watch the evaluator compute it. Because the tree encodes the grouping, the evaluator needs no idea of "precedence" at all: it just does what the tree says.

Ruby Step 2: a hand-built tree and its evaluator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Bin["+", left, right] is a pattern that matches a Bin node whose first field equals "+" and binds the other two to variables. Because Data defines deconstruct, positional patterns work; and because Data objects compare by value, two trees built separately are equal, which makes testing a parser easy: you can write the expected tree and compare it with ==. The recursion mirrors the tree: to evaluate a node, evaluate its children, then combine.

Step 3: the parser

Now the interesting part. A recursive descent parser has one method per grammar rule, and each method calls the rules below it. The parser keeps an index into the token list. Two helper methods do most of the bookkeeping: peek looks at the current token without consuming it, and advance consumes it.

Look at how expression is written. It parses a term, then loops while the next token is + or -, building a new Bin each time with the tree so far as its left side. That loop makes subtraction left-associative: 10 - 3 - 2 becomes (10 - 3) - 2, which is 5, not 10 - (3 - 2), which is 9. power is different: it calls itself on the right side, which makes 2 ^ 3 ^ 2 mean 2 ^ (3 ^ 2), matching mathematics.

Ruby Step 3: the parser builds trees

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Study the trees. 2 + 3 * 4 has + at the top and * below it, so the evaluator will compute the product first. -2 ^ 2 is neg(2 ^ 2), which is -4, the same answer a mathematician gives. In the error list, notice that each message says what the parser expected and what it found, with a position. The only extra ingredient is expect(")"), which fails loudly when a closing parenthesis is missing.

When a recursive descent parser gets stuck, draw the call stack on paper for the failing input. Each method that is "open" corresponds to a grammar rule you are in the middle of. This is almost always faster than adding puts everywhere.

Step 4: the complete calculator

Now we combine the stages and add the final features: variables stored in a hash, a table of functions, careful arithmetic, and a read-evaluate-print loop driven by standard input. Real arithmetic has several traps, so the evaluator guards them:

  • 7 / 2 should be 3.5, not Ruby's integer 3; but 8 / 2 should still be 4, not 4.0.
  • Division or modulo by zero must raise our own CalcError, not Ruby's ZeroDivisionError.
  • 2 ^ -1 gives a Rational in Ruby; we convert it to a float.
  • A huge exponent would hang the machine, so we refuse exponents above 10,000.
  • sqrt(-1) raises Math::DomainError, which we translate.

Every error the user can cause becomes a CalcError, so the loop can catch exactly that class and carry on, while real bugs (any other exception) still crash loudly, which is what you want.

Ruby Step 4: the complete calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Read the output from top to bottom and match each line with the rule that produced it. x / 4 prints 2.5 while x / 5 prints 2, thanks to the whole check. 0.1 + 0.2 prints 0.3 because format_number rounds away floating-point noise (the raw value is 0.30000000000000004, see Numbers for why). The wrong-arity cases are caught by rescuing ArgumentError around the lambda call: lambdas are strict about argument counts (Procs and Lambdas). The last line, ast 1 + 2 * 3, uses p to print the tree with its readable Data representation, which is a handy debugging tool.

Two design choices deserve a comment. First, the Calculator object owns the variables, so every line you type shares them, as in a REPL. Second, rescue ArgumentError inside call is deliberately narrow: it wraps only the lambda call, so an argument error from a genuine bug elsewhere in the evaluator would still surface.

What if you do not catch the error?

Errors that you turn into CalcError are polite. Errors you forgot to handle are not. Here is what a tiny evaluator without the guard does with 1 / 0. This example fails on purpose:

Ruby Dividing by zero without a guard (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The first line prints 2, because Ruby's integer division truncates (the bug that fdiv fixed above). The second raises ZeroDivisionError with the message divided by 0, and the program stops with a stack trace pointing into evaluate. For a calculator, that is the wrong experience: the user made an ordinary mistake. Translating it to a CalcError with a friendly message, and rescuing only CalcError in the loop, is the fix we used in Step 4.

Extending the project

Each of these is a good exercise, and each touches a different stage:

  1. Tokenizer: accept numbers like .5 and 1e3, and the constants pi and e (store them as default variables).
  2. Parser: add comparison operators and an if(condition, a, b) function; add ! for factorial as a postfix operator.
  3. Evaluator: use Rational arithmetic so 1/3 + 1/3 + 1/3 is exactly 1, and print results as fractions.
  4. Tree transforms: write simplify(node), a recursive method that folds constants (2 * 3 becomes Num(6)) and removes x * 1 and x + 0. Pattern matching makes this a joy.
  5. Tools: add a to_source(node) method that prints a tree back as text with minimal parentheses; compile the tree to Ruby code or a stack machine's instructions.
  6. Quality: write Minitest tests that compare Parser.new("1+2*3").parse with the expected Bin tree, and test every error message.

When you finish, the next project, a bank account simulation, puts classes, modules and custom exceptions to work in a different style, and A JSON Parser applies the same recursive descent idea to a real data format.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does 2 + 3 * 4 evaluate to 14 in our parser?

    Precedence is encoded in the grammar. The expression method calls term for each operand, so the product is grouped into its own node and evaluated first.
  2. 2. How does the loop in expression make 10 - 3 - 2 equal 5?

    Each iteration wraps the tree built so far as the left child of a new node, which makes the operator left-associative: (10 - 3) - 2.
  3. 3. Why does power call unary on its right-hand side?

    Parsing the exponent with unary (which leads back to power) lets the exponent carry a minus sign and makes 2 ^ 3 ^ 2 group as 2 ^ (3 ^ 2).
  4. 4. Why does the REPL loop rescue CalcError instead of StandardError?

    Rescuing only your own error class separates expected, user-caused failures from programming errors, which should not be hidden.
  5. 5. Which Ruby feature lets Bin["+", left, right] match a node and bind its children?

    Data defines deconstruct and deconstruct_keys, so case/in can destructure instances positionally or by keyword.

Summary

  • A calculator is a pipeline: tokenizer (text to tokens), parser (tokens to tree), evaluator (tree to value).
  • A grammar written rule by rule becomes a recursive descent parser with one method per rule; precedence comes from which rule calls which.
  • Data classes make clean immutable AST nodes that compare by value and work with case/in patterns.
  • Loops build left-associative operators; a self-call on the right side builds right-associative ones such as ^.
  • Translate every user-caused failure into your own exception class with a position and a clear message, and rescue only that class.
  • Watch numeric edge cases: integer vs. float division, division by zero, negative exponents, huge exponents and floating-point noise.

Next: Project: Command-Line To-Do Manager