Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 61 ยท Getting Started

Meet Our Toy Language

Meet Tiny, the small language you will compile throughout this track: its tokens, grammar, sample programs and a runnable reference interpreter.

To learn how compilers work you need something to compile. Real languages such as C or Java are too large: their specifications run to hundreds of pages. So this track uses a small language of our own, called Tiny. It is just big enough to be interesting (arithmetic, variables, decisions, loops and functions) and just small enough that you can hold the whole thing in your head.

Every chapter ahead applies to Tiny. You will write its lexer, give it a grammar, parse it, check it, translate it to intermediate code and finally run it on a virtual machine. This lesson defines the language, shows what programs look like, and gives you a reference interpreter to experiment with before you build the real pieces yourself. If you have not yet seen how the parts fit together, read the phases of a compiler first.

Design goals

A good teaching language follows a few rules:

  • Small. Few features, each easy to explain, so the compiler pieces stay short.
  • Familiar. It looks like a blend of C, JavaScript and Rust, so you can focus on the compiler, not on strange syntax.
  • Complete enough to be useful. Tiny can compute factorials, test primes and define recursive functions. A language that cannot loop or call functions would hide the most interesting compiler problems.
  • Easy to parse. Statements end in semicolons, blocks use braces, and conditions are always in parentheses. No clever layout rules.
  • Honest. What Tiny does not have (arrays, classes, floats, modules) is not hidden. A language this small is not "missing" things; it simply leaves them out.

Lexical structure

The lexer sees these kinds of tokens:

Token kind Examples Notes
Number 0, 42, 1000 non-negative whole numbers; -5 is the operator - applied to 5
String "hello" double quotes, no escape sequences in version 0
Identifier x, total_2, _tmp letter or underscore, then letters, digits or underscores
Keyword let print if else while fun return true false and or not reserved; cannot be identifiers
Operator + - * / % < <= > >= == != = = is assignment, == is comparison
Punctuation ( ) { } ; ,
Comment // until end of line ignored

Whitespace separates tokens but has no other meaning, so indentation is only for people.

Values and types

Tiny has three kinds of values:

  • integers such as 7 and -3. Arithmetic is on whole numbers; / is floor division, so 7 / 2 is 3.
  • booleans: true and false, produced by comparisons and logical operators.
  • strings, which can be printed and compared but not combined.

Variables have no declared types. Later, in type checking, you will add a checker that works out the types and rejects nonsense such as 1 + true before the program runs.

Statements

TEXT
let x = 10;                    // declare a variable
x = x + 1;                     // assign to an existing variable
print x * 2;                   // write a value on its own line

if (x > 5) { print "big"; } else { print "small"; }

while (x > 0) { x = x - 3; }

fun add(a, b) { return a + b; }
print add(2, 3);

A few rules worth stating once:

  • Every let creates a variable in the current block. Each { ... } opens a new scope, and an inner let can shadow an outer one with the same name. Symbol tables and scopes explores this.
  • Assignment changes the nearest visible variable of that name. Assigning to a name that was never declared is an error.
  • else is optional. The braces are mandatory, which also removes the famous "dangling else" ambiguity you will study in ambiguity and precedence.
  • Functions are declared with fun, take zero or more parameters, and give a value back with return. A function that finishes without return produces no useful value.
  • Functions may call themselves, so recursion works.

Expressions and precedence

From the loosest binding to the tightest:

Level Operators Associativity
1 or left
2 and left
3 == != left
4 < <= > >= left
5 + - left
6 * / % left
7 unary - and not prefix
8 function call f(x) postfix

Parentheses override everything. The table says that 1 + 2 * 3 is 7, and that 10 - 4 - 3 is 3 (left to right), not 9. Everything in this table becomes a grammar rule in the next chapters.

The grammar sketch

Here is the whole syntax in EBNF notation (* means "zero or more", ? means "optional", | means "or"). A formal introduction comes in context-free grammars; for now read it as a compact summary.

TEXT
program     = statement* ;
statement   = "let" ID "=" expr ";"
            | ID "=" expr ";"
            | "print" expr ";"
            | "if" "(" expr ")" block ( "else" block )?
            | "while" "(" expr ")" block
            | "fun" ID "(" params? ")" block
            | "return" expr ";"
            | expr ";" ;
block       = "{" statement* "}" ;
params      = ID ( "," ID )* ;

expr        = or_expr ;
or_expr     = and_expr ( "or" and_expr )* ;
and_expr    = equality ( "and" equality )* ;
equality    = comparison ( ( "==" | "!=" ) comparison )* ;
comparison  = term ( ( "<" | "<=" | ">" | ">=" ) term )* ;
term        = factor ( ( "+" | "-" ) factor )* ;
factor      = unary ( ( "*" | "/" | "%" ) unary )* ;
unary       = ( "-" | "not" ) unary | call ;
call        = primary ( "(" args? ")" )* ;
primary     = NUMBER | STRING | "true" | "false" | ID | "(" expr ")" ;
args        = expr ( "," expr )* ;

Notice how the expression rules stack one on top of another, one rule per precedence level. That layering is the standard way to encode precedence in a grammar, and it is exactly what you will study and use later.

What the lexer sees

Before parsing anything, the compiler turns a program into tokens. Here is a Tiny program that computes a greatest common divisor, with a quick census of its tokens. The scanner is deliberately short; Writing a Complete Lexer builds a proper one.

Python Counting the tokens of a Tiny program

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 input()), it gets the next line from this box.

The comment and the whitespace are recognized but never reach the parser, which sees 43 tokens. Change gcd(48, 18) to something else, or add a second function, and watch the counts change.

A reference interpreter

Finally, here is a complete working interpreter for Tiny, about a hundred lines. It is a tree-walking interpreter: it tokenizes, parses into a tree of tuples, and evaluates the tree directly. We call it the reference implementation, because later in the track you will build a real compiler and virtual machine and check that they agree with it on every program.

You do not need to understand every line yet. Treat it like a black box and run the programs at the bottom: factorial, a prime counter, and a scoping puzzle where an inner let x shadows the outer one. Then edit the programs or write your own.

Python Run Tiny programs

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 input()), it gets the next line from this box.

The factorial program prints 1, 2, 6, 24 and 120. The prime counter finds 10 primes below 30. In the shadowing program the block prints its own x (99), but afterwards show_x() still sees the outer x (10), because the inner let only existed inside the braces. The last two programs fail on purpose: the first with a NameError because y was never declared, the second with a SyntaxError because an expression is missing.

Notice how those two errors differ. The first is caught only when the program runs, because this interpreter has no checking phase. A compiler could report it before running anything, and that is the job of semantic analysis.

The road ahead

Here is how the track turns this reference interpreter into a real compiler:

flowchart LR
    A["Lexer<br/>(chapter 2)"] --> B["Grammar and parser<br/>(chapters 3 and 4)"]
    B --> C["Checker<br/>(chapter 5)"]
    C --> D["IR and optimizer<br/>(chapter 6)"]
    D --> E["Code generator and VM<br/>(chapter 7)"]
    E --> F["Projects<br/>(chapter 8)"]

Each chapter replaces one blackbox in the reference interpreter with a part you wrote and understand.

The first step is the lexer. You have already seen a tiny version above; the next chapter starts from the basics with tokens, lexemes and patterns.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does Tiny require braces around the body of every if and while?

    Mandatory braces mean every else clearly belongs to one if, and the parser never has to guess where a body ends.
  2. 2. What does 10 - 4 - 3 evaluate to in Tiny?

    Subtraction is left associative, so the expression means (10 - 4) - 3, which is 3. Right associativity would give 10 - (4 - 3) = 9.
  3. 3. In the shadowing example, why does show_x() print 10 after the block printed 99?

    Each block opens a new scope. The inner let x = 99 creates a separate variable that disappears when the block ends, leaving the outer x unchanged.
  4. 4. Which tokens does the lexer discard before the parser sees the program?

    Whitespace and comments carry no meaning for the parser, so the lexer recognizes them and throws them away.

Summary

  • Tiny is a small C-like language with integers, booleans, strings, variables, if/else, while, functions and recursion.
  • Its lexical structure has numbers, strings, identifiers, twelve keywords, operators, punctuation and // comments.
  • Expressions have eight precedence levels; binary operators are left associative and parentheses override them.
  • The grammar is one rule per statement kind plus one rule per precedence level, a pattern you will reuse in every parser.
  • A reference tree-walking interpreter defines what Tiny programs mean; your compiler must agree with it.
  • You can run and edit Tiny programs right on this page.

Next: Tokens, Lexemes and Patterns