CFG Parser

Overview

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

Before this project, I had mainly programmed in Java and Python. I chose Rust because I wanted to move closer to systems programming and understand concepts that higher-level languages had mostly handled for me: ownership, memory safety, and explicit control over how data moves through a program.

Rather than learn those ideas through isolated exercises, I spent about one month building a complete command-line expression parser. I designed the grammar myself, wrote the tokenizer and recursive-descent parser by hand, and evaluated each expression without relying on an existing calculator library or parser generator.

The result is an arithmetic language supporting precedence, nested parentheses, unary negation, implicit multiplication, exponentiation, n-th roots, and structured failures.

The arithmetic was not the main challenge. The valuable part was deciding exactly which inputs belong to the language, which layer should reject invalid input, and how Rust should represent the path from raw text to either a number or an error.

Goal

My goal was to make two unfamiliar subjects practical at the same time: Rust and context-free grammars.

I wanted the grammar to be more than documentation written after the code. It had to define the implementation itself. Each production would become a parser function, each precedence level would have an explicit boundary, and every accepted expression would follow the same path through the language.

I deliberately avoided a parser generator because that would have hidden the part I most wanted to understand. I also chose direct evaluation instead of building an abstract syntax tree. The program only needed to return one numeric result, so introducing a second intermediate representation would have added complexity without solving a current requirement.

The final = delimiter was another deliberate language decision. It gives the parser an explicit end to a complete formula, rather than accepting whatever valid prefix happens to appear before the input stops.

Technical Approach

The implementation is split into two main stages.

The tokenizer scans the input character by character and produces typed tokens for real numbers, operators, parentheses, and the final delimiter. Its responsibility is lexical: identify what each symbol is and reject malformed numbers or unknown characters before grammar evaluation begins.

The recursive-descent parser then consumes the token sequence. Its functions mirror the grammar layers:

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 minus, and parenthesized expressions.

This structure encodes precedence directly. Multiplication does not need to be “fixed” after addition, because additive parsing can only consume values that have already passed through the product layer.

Exponentiation and roots are right-associative through recursion. For example, 2^3^2 is interpreted as 2^(3^2), because the parser resolves the expression on the right before completing the current operation.

Architecture

The parser evaluates values while traversing the grammar, so the complete flow stays linear:

Input string
    -> Tokenizer
    -> Vec<Token>
    -> Recursive-descent parser/evaluator
    -> f64 result or CalcError

One important design decision was keeping implicit multiplication inside the parser rather than the tokenizer.

The tokenizer can see that 2 is a number and ( is a parenthesis, but it should not decide that the relationship between them means multiplication. That decision requires grammar context.

The product layer therefore accepts three constrained adjacency patterns:

• a number followed by (, as in 2(3 + 4);
• ) followed by (, as in (1 + 2)(3 + 4);
• ) followed by a number, as in (1 + 2)3.

Parentheses provide a clear boundary for implicit multiplication, allowing expressions such as 4(1.2 - 3.4) to be valid while rejecting 2 3.

This boundary keeps lexical recognition simple while allowing the parser to support familiar mathematical notation without turning the implementation into a collection of string-specific exceptions.

Main Challenge: Giving Each Failure the Right Owner

The most difficult part was assigning lexical, syntactic, and mathematical failures to the layer that had enough information to identify them correctly.

From a user's perspective, all of these inputs are simply “wrong,” but they fail for different reasons:

• 1..2 + 3 = contains a malformed number and should fail during tokenization.
• 2 + = contains valid tokens but violates the grammar because an operand is missing.
• 2 * (3 + 4 = reaches the parser with an unmatched parenthesis.
• 8 / 0 = is syntactically valid but mathematically undefined.
• a negative number with an even root is valid syntax but invalid over the real numbers.

Combining every failure into one generic message would have made the parser easier to write but harder to reason about. The implementation models and exposes those failures through:

• TokenError for malformed input and invalid expression structure;
• MathError for division by zero, invalid powers or roots, overflow, and underflow;
• CalcError as the unified result returned to the caller.

This forced me to answer a useful design question for every failure: which layer has enough information to identify the problem accurately?

That same question improved the rest of the architecture. The tokenizer recognizes symbols, the parser validates relationships between tokens, and the parser’s evaluation logic enforces numeric constraints.

What Shipped

The CLI supports a compact but intentionally defined expression language:

• real numbers and unary negation;
• +, -, *, and / with standard precedence;
• nested parenthesized expressions;
• constrained implicit multiplication;
• right-associative exponentiation with ^;
• n-th roots with $;
• mandatory formula termination with =;
• explicit token, syntax, and mathematical errors.

Representative expressions show the grammar working across features:

• 1 + 2 * 3 = returns 7.000 because the product layer resolves first.
• (1 + 2)(3 + 4) = returns 21.000 through implicit multiplication.
• 2^3^2 = follows right-associative exponentiation.
• 27 $ 3 = returns the cube root of 27.
• 5 5 = is rejected rather than silently guessed.
• 2 + = is rejected before evaluation because its right operand is missing.

The project can run directly with Cargo or inside Docker, with expressions supplied as command-line arguments or through the CFGPARSER_INPUT environment variable.

Engineering Proof

The repository documents the grammar, architecture, Docker workflow, supported operators, valid expressions, invalid expressions, and error categories.

The five grammar non-terminals are implemented through eight recursive-descent methods. That mapping makes the implementation inspectable: a reader can move from a production rule to the exact function responsible for it.

The project also exposes repeatable execution paths:

• cargo run for local development;
• cargo test for the current test target;
• Docker builds for an isolated runtime;
• CLI arguments and environment variables for custom expressions.

The strongest evidence is the explicit grammar, the documented valid and invalid cases, and the direct correspondence between language rules and parser functions.

Expanding those examples into a comprehensive regression suite is the most important step before extending the language.

What I Learned

This project was my first practical experience with Rust ownership.

In Java and Python, I could often pass data between functions without thinking deeply about who owned it or how long a reference remained valid. Rust made those decisions visible. The tokenizer borrows the input while scanning it, produces a vector of owned tokens, and transfers that token sequence into the parser. Lightweight token values can be copied, while larger values and errors move through explicit Result paths.

At first, these rules made development slower. That learning curve is one reason the project took about a month. Over time, however, ownership stopped feeling like a restriction and became a way to describe the program's data flow more precisely.

I also learned that parser correctness starts before implementation. When a grammar rule is vague, the code tends to accumulate special cases. When the rule is precise, the correct layer and function usually become much easier to identify.

The part I am most proud of is not one operator. It is designing my first grammar and implementing it in a language that was completely new to me, rather than falling back to Java where the work would have been more familiar.

Future Improvements

Before adding more syntax, I would strengthen the project's internal structure and verification.

The first improvement would be splitting the current implementation into focused modules for tokens, tokenization, parsing, errors, CLI input, and tests. That would make each responsibility easier to navigate and reduce the cost of changing one grammar layer.

The second improvement would be building a larger regression suite around:

• precedence and associativity;
• every supported implicit-multiplication transition;
• nested and unmatched parentheses;
• unary negation;
• malformed numbers and incomplete expressions;
• division by zero, invalid exponentiation, invalid roots, overflow, and underflow.

Only after that foundation is in place would I consider an AST, variables, assignments, or functions. Those features need reusable expression structure; the current direct-evaluation design is intentionally appropriate for the calculator-sized language that exists today.

Links

• GitHub repository
• Technical documentation
• Project README