CFG Parser

Overview

Stack: Rust · Recursive-descent parsing · CLI · Docker

Before this project, most of my programming experience was in Java and Python. I wanted to try systems programming and understand ownership, borrowing, and explicit error handling in a program large enough for those ideas to matter.

I spent about a month building CFG Parser, a command-line calculator that tokenizes, parses, and evaluates arithmetic expressions. I wrote the grammar, tokenizer, and parser by hand rather than using a parser generator or calculator library.

The resulting language supports real numbers, nested parentheses, unary negation, implicit multiplication, exponentiation, n-th roots, and separate syntax and mathematical errors.

Calculating the answer was familiar. What interested me was encoding why one operation must happen before another—and making invalid input fail at the layer that could explain it.

From Grammar to Code

The implementation has two stages. The tokenizer scans the input and creates a Vec<Token> containing numbers, operators, parentheses, and the final = delimiter. The parser then consumes those tokens through five grammar levels:

1. F validates a complete formula ending in =.
2. E handles addition and subtraction.
3. P handles multiplication, division, and implicit multiplication.
4. U handles exponentiation and n-th roots.
5. B handles numbers, unary negation, and parenthesized expressions.

Each level calls the one below it before applying its own operators. Addition therefore receives values only after multiplication and powers have been resolved; precedence follows from the call structure instead of a table of special cases.

Powers and roots recurse on their right-hand side, making them right-associative. For example:

2^3^2 =

is evaluated as 2^(3^2), producing 512, rather than (2^3)^2.

The parser evaluates while it walks the grammar. Every successful method returns an f64 to the level above, so this version does not build an abstract syntax tree. An AST would add useful structure for variables, functions, or transformations, but it was unnecessary for a calculator whose only output is one number.

A Small Language Decision

I made = a required formula terminator rather than accepting the end of the input implicitly. A complete expression must reach it, and any trailing token is rejected. That gives the top-level grammar rule a clear boundary.

Implicit multiplication required a different kind of boundary. In an expression such as 2(3 + 4), the tokenizer can identify a number followed by a parenthesis, but it should not invent their meaning. The product layer decides whether that adjacency represents multiplication.

The grammar documents three intended forms:

number (
) (
) number

They cover 2(3 + 4), (1 + 2)(3 + 4), and (1 + 2)3. Keeping this decision in the parser separates symbol recognition from expression meaning.

The current implementation uses a broader adjacency predicate than the documented grammar and can also accept adjacent numbers. I would align the predicate with the grammar before extending the language. Finding that mismatch was a useful reminder that documentation and implementation only stay equivalent when tests enforce the contract between them.

Errors Belong Somewhere

The hardest implementation questions appeared around invalid input. These expressions are all wrong, but not for the same reason:

• 1..2 + 3 = contains a malformed number and fails during tokenization.
• 2 + = contains valid tokens but no right operand.
• 2 * (3 + 4 = is missing a closing parenthesis.
• 8 / 0 = is syntactically complete but mathematically invalid.
• an even-index root of a negative number falls outside the real numbers supported by the evaluator.

The project represents malformed input and expression structure with TokenError, numerical failures with MathError, and exposes both through CalcError. Rust's Result type carries those possibilities through each parsing method.

This made error handling part of the design rather than a message added after evaluation. The tokenizer knows whether characters form a valid token; the parser understands relationships between tokens; the mathematical operations know whether a valid expression has a result in the supported number system.

What the CLI Supports

The finished command accepts expressions through a CLI argument or the CFGPARSER_INPUT environment variable and can run with Cargo or Docker.

1 + 2 * 3 =          -> 7.000
(1 + 2)(3 + 4) =     -> 21.000
2^3^2 =              -> 512.000
27 $ 3 =              -> 3.000 (cube root of 27)

The repository includes the formal grammar, architecture notes, Docker instructions, and examples of valid and invalid expressions. Its parser methods map directly to the grammar: evaluate, evaluate_e, evaluate_p, evaluate_u, and evaluate_b, together with the recursive continuation methods for each operator level.

What I Took From It

Rust initially slowed me down. I had to decide whether values should be moved, borrowed, or copied instead of passing data around as casually as I would in Java or Python. In this program, the tokenizer borrows the input, produces owned tokens, and passes them into the parser; failures travel through explicit return values rather than exceptions.

After a while, those decisions became a way to describe the program's data flow rather than requirements I was satisfying only for the compiler.

The parser changed another assumption. I had always known that multiplication comes before addition, but implementing the grammar showed me how precedence can emerge from program structure. Choosing Rust made the work slower, and that was useful: I started the project to encounter decisions I could have avoided in a familiar language.

Next Steps

The priority is a regression suite for precedence, associativity, parentheses, unary negation, malformed input, numerical failures, and every accepted or rejected form of implicit multiplication. The current test target is too small for the number of language rules the repository documents.

I would then split the single-file implementation into modules for tokens, tokenization, parsing, errors, CLI input, and tests. If the language later gained variables, assignments, or functions, that would be the point to introduce an AST rather than stretching direct evaluation beyond its original purpose.

Links

• GitHub repository
• Technical documentation
• Project README