Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 36 ยท Projects and Practice

Project: A Tokenizer and Calculator in Nim

Build an expression calculator in Nim with a tokenizer using variant objects and a recursive descent parser, plus a runnable C version of the same design.

A calculator that understands 2 + 3 * (4 - 1) is a classic project because it touches everything: reading characters, grouping them into tokens, respecting operator precedence, and handling errors. You will use a variant object for tokens and a small recursive descent parser.

The Nim program is read-only on this site (type it in and run nim r calc.nim yourself). The C version below runs here and uses the identical design.

Grammar

Precedence is built into the grammar: each rule calls the next stronger one.

Text
expr   = term   { ("+" | "-") term }
term   = factor { ("*" | "/") factor }
factor = number | "(" expr ")" | "-" factor
flowchart TD
  E["expr: + and -"] --> T["term: * and /"]
  T --> F["factor: number, parentheses, unary minus"]
  F -->|"( ... )"| E

Each level handles one precedence class; parentheses loop back to the top.

Tokens in Nim

NIM
type
  TokenKind = enum
    tkNum, tkOp, tkLParen, tkRParen, tkEnd

  Token = object
    case kind: TokenKind
    of tkNum: value: float
    of tkOp: op: char
    else: discard

proc tokenize(src: string): seq[Token] =
  var i = 0
  while i < src.len:
    let c = src[i]
    case c
    of ' ': inc i
    of '0'..'9', '.':
      var j = i
      while j < src.len and src[j] in {'0'..'9', '.'}: inc j
      result.add Token(kind: tkNum, value: parseFloat(src[i ..< j]))
      i = j
    of '+', '-', '*', '/':
      result.add Token(kind: tkOp, op: c); inc i
    of '(': result.add Token(kind: tkLParen); inc i
    of ')': result.add Token(kind: tkRParen); inc i
    else:
      raise newException(ValueError, "unexpected '" & c & "' at " & $i)
  result.add Token(kind: tkEnd)

The parser in Nim

NIM
type Parser = object
  toks: seq[Token]
  pos: int

proc peek(p: Parser): Token = p.toks[p.pos]
proc next(p: var Parser): Token =
  result = p.toks[p.pos]
  inc p.pos

proc expr(p: var Parser): float

proc factor(p: var Parser): float =
  let t = p.next()
  case t.kind
  of tkNum: t.value
  of tkLParen:
    result = expr(p)
    if p.next().kind != tkRParen: raise newException(ValueError, "expected )")
  of tkOp:
    if t.op == '-': -factor(p)
    else: raise newException(ValueError, "unexpected operator")
  else: raise newException(ValueError, "unexpected end")

proc term(p: var Parser): float =
  result = factor(p)
  while p.peek.kind == tkOp and p.peek.op in {'*', '/'}:
    let op = p.next().op
    let rhs = factor(p)
    result = if op == '*': result * rhs else: result / rhs

proc expr(p: var Parser): float =
  result = term(p)
  while p.peek.kind == tkOp and p.peek.op in {'+', '-'}:
    let op = p.next().op
    let rhs = term(p)
    result = if op == '+': result + rhs else: result - rhs

echo expr(Parser(toks: tokenize("2 + 3 * (4 - 1)")))   # 11.0

The forward declaration proc expr(p: var Parser): float lets factor call expr before it is defined. var Parser shares the cursor across calls (see Value, Reference and Pointer Semantics).

The same design in C

This version evaluates directly from the character stream, one function per grammar rule, which is the same recursion without the separate token list.

C C stand-in: recursive descent 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 scanf or fgets), it gets the next line from this box.

Precedence works without any table: 3 * (4 - 1) is finished inside term before expr adds it to 2.

Extensions

  1. Add ^ for powers (right associative: its rule calls itself on the right).
  2. Support variables with a Table[string, float] and an assignment statement.
  3. Return an Option[float] or a result variant instead of raising exceptions.
  4. Turn the evaluator into a tree builder, then print or optimize the tree (the same shape as in Macros and the AST).
  5. Add tests in tests/ using std/unittest.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How does the grammar enforce that * binds tighter than +?

    Each precedence level is a function that calls the next stronger one.
  2. 2. Why does Nim need proc expr(p: var Parser): float before factor?

    A forward declaration allows mutual recursion.
  3. 3. What type is best for a token with different data per kind?

    A case object carries only the fields each kind needs.
  4. 4. What should happen on input like 2 + * 3?

    Parsers should reject malformed input with an error.

Summary

  • Tokenize first, parse second, or parse the characters directly.
  • One function per grammar rule gives correct precedence for free.
  • Variant objects model tokens; forward declarations allow mutual recursion.
  • Always report malformed input.

Next: Project: A Ring Buffer