Skip to content

MathParser: Parsers as a Thinking Tool

A look back at a parser demo of my own from 2010 shows why a handwritten expression parser teaches more about layers, structure and the boundary between syntax and semantics in a few lines than many a large project.

≈ 12 min readSoftwareArchitecture

MathParser: Parsers as a Thinking Tool

About 200 lines of C#. That’s all a complete parser for arithmetic expressions needs – tokenizer, recursive descent, evaluation, parentheses, operator precedence, useful error messages with positions. An average controller in a business system reaches the same length and teaches almost nothing about software design along the way. The 200 parser lines, on the other hand, contain three cleanly separated layers, a grammar as an explicit structural model and a boundary between form and meaning that you’ll pinch your fingers on at least once while writing. Measured in insight per line, I know little that is denser – and it fits into an afternoon.

A four-year-old demo project, reread#

The occasion for this text is a repository of my own: MathParser, a C# demo project from 2010. A Visual Studio solution containing a parser project, a second variant called ClassicMathParser and a test project. Not a product, not a library for others – a demo, written to have worked through the subject myself once.

Four years later I opened it again, really just to clean up. What caught me was something else: the code asks questions I didn’t see at all in 2010. Why are there two variants side by side? Why does the parser evaluate right away instead of building a structure first? Why does the handling of the minus sign sit exactly where it sits? Old projects of your own are uncomfortably honest in this respect: you’re arguing with a former self who can no longer talk their way out.

That’s exactly why the look back is worth an article. Not because the repository is special – but because the topic ages better as a thinking tool than most frameworks of that time.

Why a regular expression isn’t enough here#

The first reflex for “parse an arithmetic expression” is the same again and again in code reviews: a regular expression, maybe two, plus a Split on operators. For 2+3*4 this even looks good for a moment. For (1+2)*(3-(4/2)) it collapses, and not because of sloppy craftsmanship but fundamentally: regular expressions can’t count. Nested parentheses require a memory of the nesting depth, and that’s exactly what a regular expression can’t provide by its very model. You can justify this theoretically – regular versus context-free languages – but in practice a look at the parentheses is enough: if you read (((, you have to remember that ))) still has to follow three times.

In 2010 I noticed for the first time that the choice of tool is a statement about the structure of the problem. A regular expression claims: “This input is flat.” A parser with recursion claims: “This input is a tree.” Arithmetic expressions are trees – 1+2*3 has an inner structure you can’t see in the string. If you claim the wrong thing, you pay for it later with special cases.

Three layers, three contracts#

An expression parser falls apart into three layers almost by itself, and each one has a clear contract:

  • The tokenizer turns a string into a stream of symbols: numbers, operators, parentheses. It knows characters, but no structure.
  • The parser checks whether the symbol sequence matches the grammar and builds the structure from it. It knows structure, but no meaning.
  • Evaluation gives the structure a meaning: it computes. Only here do concepts like “result” or “division by zero” exist.
flowchart LR
  A["Input<br/>(1+2)*3"] --> B["Tokenizer<br/>characters to symbols"]
  B --> C["Token stream<br/>( 1 + 2 ) * 3"]
  C --> D["Parser<br/>recursive descent"]
  D --> E["Structure<br/>tree or direct value"]
  E --> F["Evaluation<br/>meaning, result"]

That sounds like a textbook, but it has a very practical point: you can test, replace and explain each layer on its own. That’s exactly why the solution has its own test project, and the tests for the tokenizer know nothing about grammar – they only check that "12.5+" becomes the symbols 12.5 and +. This kind of separation is preached constantly in large systems; in the parser it isn’t a resolution but the only convenient way to build it. That’s the first reason I call the topic a thinking tool: it lets you experience an architectural principle instead of just claiming it.

The grammar forces you to think about structure#

Before the actual parser comes the grammar – back then, for me, as an EBNF sketch on a piece of paper, in this form:

Expression := Term   { ("+" | "-") Term }
Term       := Factor { ("*" | "/") Factor }
Factor     := Number | "(" Expression ")" | "-" Factor

Three lines, and the most interesting property isn’t stated explicitly anywhere: operator precedence. Multiplication before addition isn’t a rule checked with an if somewhere – it lives in the layering of the grammar. Expression consists of Term building blocks, Term of Factor building blocks. Because * and / are bound one level deeper than + and -, they automatically bind more tightly. The parenthesis, in turn, jumps from the very bottom back to the very top: a Factor may contain a complete Expression. That’s the recursion the regular expression failed at earlier, here in a single line.

Rereading it in 2014, I still find this remarkable: precedence as structure instead of as a condition. Terence Parr covers exactly this way of thinking in depth in “Language Implementation Patterns” from 2010, and Douglas Crockford shows an alternative path in his essay “Top Down Operator Precedence” from 2007, where precedence is attached as binding power to the operators themselves. Both paths get you there; if you’ve rebuilt both once, you understand better afterward what “expressing structure” even means.

Recursive descent in C##

The grammar translates into code almost mechanically – one method per rule. First the tokenizer, deliberately kept simple here:

public enum TokenType { Number, Plus, Minus, Star, Slash, LeftParen, RightParen, End }

public sealed class Tokenizer
{
    private readonly string _input;
    private int _position;

    public Tokenizer(string input) { _input = input; }

    public Token Next()
    {
        while (_position < _input.Length && char.IsWhiteSpace(_input[_position]))
            _position++;

        if (_position >= _input.Length)
            return new Token(TokenType.End, 0, _position);

        char current = _input[_position];

        if (char.IsDigit(current))
        {
            int start = _position;
            while (_position < _input.Length &&
                   (char.IsDigit(_input[_position]) || _input[_position] == '.'))
                _position++;

            double value = double.Parse(
                _input.Substring(start, _position - start),
                CultureInfo.InvariantCulture);

            return new Token(TokenType.Number, value, start);
        }

        _position++;
        switch (current)
        {
            case '+': return new Token(TokenType.Plus, 0, _position - 1);
            case '-': return new Token(TokenType.Minus, 0, _position - 1);
            case '*': return new Token(TokenType.Star, 0, _position - 1);
            case '/': return new Token(TokenType.Slash, 0, _position - 1);
            case '(': return new Token(TokenType.LeftParen, 0, _position - 1);
            case ')': return new Token(TokenType.RightParen, 0, _position - 1);
        }

        throw new FormatException(
            string.Format("Unexpected character '{0}' at position {1}.", current, _position - 1));
    }
}

Two small things with a big effect: CultureInfo.InvariantCulture, because otherwise double.Parse expects a comma on a German machine and silently turns 1.5 into 15 – a bug I haven’t hunted in the parser demo, but more than once in real systems. And the position in the token, because without it no later layer can produce an error message that shows the user where the problem is.

The parser itself follows the grammar line by line:

public sealed class Parser
{
    private readonly Tokenizer _tokenizer;
    private Token _current;

    public Parser(string input)
    {
        _tokenizer = new Tokenizer(input);
        _current = _tokenizer.Next();
    }

    public double Parse()
    {
        double result = ParseExpression();
        Expect(TokenType.End);
        return result;
    }

    // Expression := Term { ("+" | "-") Term }
    private double ParseExpression()
    {
        double left = ParseTerm();
        while (_current.Type == TokenType.Plus || _current.Type == TokenType.Minus)
        {
            TokenType op = _current.Type;
            Advance();
            double right = ParseTerm();
            left = op == TokenType.Plus ? left + right : left - right;
        }
        return left;
    }

    // Term := Factor { ("*" | "/") Factor }
    private double ParseTerm()
    {
        double left = ParseFactor();
        while (_current.Type == TokenType.Star || _current.Type == TokenType.Slash)
        {
            TokenType op = _current.Type;
            Advance();
            double right = ParseFactor();
            left = op == TokenType.Star ? left * right : left / right;
        }
        return left;
    }

    // Factor := Number | "(" Expression ")" | "-" Factor
    private double ParseFactor()
    {
        if (_current.Type == TokenType.Number)
        {
            double value = _current.Value;
            Advance();
            return value;
        }

        if (_current.Type == TokenType.LeftParen)
        {
            Advance();
            double inner = ParseExpression();
            Expect(TokenType.RightParen);
            return inner;
        }

        if (_current.Type == TokenType.Minus)
        {
            Advance();
            return -ParseFactor();
        }

        throw new FormatException(
            string.Format("Unexpected token at position {0}.", _current.Position));
    }

    private void Advance() { _current = _tokenizer.Next(); }

    private void Expect(TokenType type)
    {
        if (_current.Type != type)
            throw new FormatException(
                string.Format("Expected {0} at position {1}.", type, _current.Position));
        Advance();
    }
}

This is recursive descent in its purest form: ParseExpression calls ParseTerm, ParseTerm calls ParseFactor, and ParseFactor calls ParseExpression again on a parenthesis. The runtime’s call stack takes over the parenthesis counting that the regular expression lacked. You can have tools like ANTLR generate such methods from a grammar – for serious languages, I would do that too. For understanding, nothing replaces doing it by hand.

AST or direct evaluation – the question I skipped in 2010#

The parser shown computes right away: ParseTerm returns a double, not a node. That’s the shortest variant, and perfectly fine for a demo. Rereading it, though, I notice what this shortcut costs: parser and evaluation, a moment ago two layers with their own contracts, are fused into one here. If you want to compute the same expression twice with different variable values, you have to parse twice. If you want to print the expression nicely formatted, simplify it or translate it into another language, you can’t – the structure was never captured, it only existed fleetingly in the call stack.

The alternative is an abstract syntax tree: ParseTerm then returns a Node, say BinaryNode(Star, NumberNode(2), NumberNode(3)), and a separate Evaluate method walks the tree. More code, more allocations – but the structure becomes a value of its own that you can keep working with. In my solution, two project variants still sit side by side to this day, and I strongly suspect the difference revolved around exactly this question; after four years I can no longer say for sure, and that in itself is a lesson about demo projects without notes.

The general form of the question has come up constantly since then: do I evaluate right away, or do I build a model first? An import that writes line by line directly into the database is direct evaluation. An import that first builds a validated intermediate model and then applies it is the tree. Both are legitimate – but it should be a decision, not an accident.

The same in ES5, as a test#

To check whether the structure holds or is just a C# idiom, I redid the core in JavaScript – same pattern, same names:

// Expression := Term { ("+" | "-") Term }
function parseExpression(state) {
  var left = parseTerm(state);
  while (state.current.type === 'Plus' || state.current.type === 'Minus') {
    var op = state.current.type;
    advance(state);
    var right = parseTerm(state);
    left = op === 'Plus' ? left + right : left - right;
  }
  return left;
}

No type system, no classes, and yet it’s recognizably the same parser. That’s no accident: the grammar is the design document, the code merely its translation. Crockford’s essay takes this even further in JavaScript and uses it to build a parser for JavaScript itself – if you want to know what JSON.parse or an expression field in a form does inside, you’ll find the answer there in surprisingly little code.

The boundary between syntax and semantics becomes physical#

The moment that stuck with me most from that afternoon in 2010 hinges on the minus sign. 3-2 and -2 contain the same character, but two different things: once a binary operator, once a sign. The tokenizer can’t know the difference – it only sees a character. The decision is made in the parser, based on context: a minus at a position where a Factor is expected is a sign; a minus after a completed Term is a subtraction. The meaning “negate” comes even later, in evaluation.

The same goes for errors. 2+*3 fails in the parser – a syntax error, the input is already invalid as a form. 2/0, on the other hand, passes the parser without complaint and only fails in evaluation – a semantic error, the form was correct, the meaning isn’t. If you handle both errors in the same layer, you’ve blurred the boundary; if you separate them, you get two precise error messages almost for free. I’ve carried this distinction – what is well-formed, what is valid, what makes sense – through every interface discussion since, from validating an XML document to the question of whether a web service should return a 400 or a 422.

What I take away from it#

All in all, rereading the old demo made three things clear to me. First: small, self-contained problems make the better teaching pieces, because you can understand them completely – in a parser there’s no place where you’d have to point to magic. Second: the three layers and the grammar layering aren’t specialist parser knowledge but architecture in miniature; the questions “who may know what” and “where does the structure live” are exactly the same as in any larger system. Third: reading your own old projects with four years of distance is an underrated exercise – the open questions of back then are visible today, and today’s answers wouldn’t exist without that afternoon back then.

If you’ve never written a parser: one afternoon, an empty project, the three EBNF lines from above. No generator, no library, no peeking at other people’s code. The 200 lines that come out of it are probably the densest piece of software design you can learn in that time.

Further reading#

Revised and translated from German with the help of AI.