How a Machine Learned to Read: Tokens, Grammar, and the Parser

Planted 02026-08-01

How can a line of text contain a tree?

How can a machine learn to read a program?

Not execute it.

Not translate it.

Read it well enough to recognize what its parts are and how they belong together.

A person looking at this Jack statement sees structure:

let total = (price * quantity) + tax;

total is the destination.

The material after the equals sign is an expression.

The parentheses group a multiplication. The result of that multiplication participates in an addition. The semicolon ends the statement.

None of those relationships is physically present in the text file.

The file contains characters in sequence:

l e t   t o t a l   =   ( p r i c e   *   q u a n t i t y )   +   t a x ;

There are no branches showing that price and quantity belong inside the multiplication. There is no box surrounding the complete expression. The hierarchy exists only through conventions a reader has learned.

Before a compiler can produce stack commands, it must recover that invisible organization.

It must turn a line into a tree.

1. The reader who already knows too much

Reading source code feels immediate because a person brings knowledge to it.

Consider:

do square.moveRight();

A programmer can see:

do                  a statement that invokes behavior
square              the object receiving the request
.                   a connection between an object and a method
moveRight           the method being requested
( )                 an empty argument list
;                   the end of the statement

The eyes receive marks.

The mind supplies categories and relationships.

A compiler begins without that silent assistance. If it reads one character at a time, its first observations are painfully small:

d
o
space
s
q
u
a
r
e
.
...

The letter d is not a statement. The letter o is not a command. Only together, in the right location, can do play a grammatical role.

The first problem is therefore not understanding a program.

It is discovering its pieces.

2. Why spaces cannot find the words

An obvious solution is to divide the file wherever a space appears.

That works for a carefully chosen line:

let total = price;

It fails almost immediately.

Programmers are allowed to write punctuation beside names:

let total=(price*quantity)+tax;

The lack of spaces does not change the program’s structure.

Spaces can also appear inside a single value:

let message = "order complete";

The space between order and complete belongs to the string. It must not divide the string into two pieces.

Comments create another exception:

let total = total + price; // preserve the running total

The words after // are useful to a person and irrelevant to the Jack program. A reader must know when to stop treating characters as source instructions.

The boundary between pieces is not represented by one universal separator.

It depends on the kind of piece currently being read.

3. The tokenizer gives characters roles

A tokenizer groups characters into tokens and classifies them.

For Jack, the main categories are:

keyword
symbol
identifier
integer constant
string constant

The statement:

let total = (price * quantity) + tax;

becomes a stream such as:

keyword             let
identifier          total
symbol              =
symbol              (
identifier          price
symbol              *
identifier          quantity
symbol              )
symbol              +
identifier          tax
symbol              ;

Whitespace has disappeared.

Comments have disappeared.

The characters in each name have become one unit.

The tokenizer can recognize let as a keyword because Jack reserves that exact word. It can recognize 749 as an integer constant because the characters follow the permitted pattern for a number. It can recognize the characters between quotation marks as a string constant.

For an unfamiliar name such as quantity, it can make a more modest claim:

This has the shape of an identifier.

It does not yet know what the identifier identifies.

That depends on where the name appears.

4. The pieces still do not make a program

Tokenization is a genuine transformation.

The machine no longer sees isolated characters. It sees classified units.

But a token stream remains flat:

let total = ( price * quantity ) + tax ;

The sequence does not explicitly say that the tokens inside the parentheses form a smaller expression nested inside a larger one.

It does not say that total is the destination of the assignment while tax is one of the expression’s terms.

It does not say whether an identifier followed by a parenthesis begins a function call or whether an identifier followed by a bracket begins an array access.

Classifying a word is not the same as understanding its grammatical role.

Human languages face the same broad difficulty. A dictionary can say that flies may be a noun or a verb. It cannot, by that fact alone, determine the structure of every sentence containing the word.

A programming language narrows the problem by refusing most possible arrangements.

It needs rules describing which arrangements remain.

5. The international language no one computer owned

By the late 1950s, programming languages were multiplying alongside the machines they served.

FORTRAN was strongly associated with IBM computers. Other systems developed their own notations, translators, and conventions. A program written for one environment could be difficult to discuss—and impossible to run—somewhere else.

American and European researchers began working toward an international language for describing algorithms.

The effort eventually produced ALGOL, the algorithmic language.

Its ambitions created an unusual problem.

ALGOL was not supposed to belong to one manufacturer’s hardware. Its definition had to travel among countries, institutions, and compiler teams. People who had not attended the design meetings would have to read the report and build compatible implementations.

A language manual written only in ordinary prose left room for different interpretations.

A language defined only by one existing compiler would quietly make that compiler the authority—and would make its accidents part of the language.

The committee needed something stronger:

A description independent of one machine
                +
Precise enough for different people to implement
                +
Compact enough for people to inspect and debate

The problem was not yet how to parse a program.

It was how to describe, without ambiguity, what counted as a program at all.

6. The astronomer preparing for Paris

Peter Naur entered computing through astronomy.

Trained to work with observations, calculations, and precise descriptions, he became involved with the Danish computing organization Regnecentralen and with the European discussions surrounding ALGOL.

He also edited the ALGOL Bulletin, which circulated proposals, disagreements, and corrections among people trying to shape the language.

The earlier ALGOL work had exposed a basic difficulty: people could read the same informal language description and carry away different ideas about what it permitted.

John Backus had presented a notation for describing the syntax of the proposed international language. Instead of explaining every valid form in paragraphs of prose, the notation described language structures using named categories and rules for combining them.

Naur recognized what the notation made possible.

Before the final ALGOL 60 conference in Paris in January 1960, he prepared a new draft report. He adapted Backus’s notation and used it to give the proposed language a systematic structure.

Thirteen representatives from seven countries debated the language. Naur’s draft became the basis for their work. The resulting report listed its contributors, but Naur’s preparation and editing gave their agreements a coherent form.

The notation later became known as Backus–Naur Form, or BNF.

It did not remove disagreement.

It made disagreement visible at the level where it could be resolved.

7. A language for describing languages

Consider a simplified rule:

letStatement → 'let' variableName '=' expression ';'

The rule says that a letStatement consists of:

the keyword let
then a variable name
then an equals sign
then an expression
then a semicolon

The quoted pieces must appear literally.

The named pieces are categories defined by other rules.

Jack permits an optional array index, so a fuller rule resembles:

letStatement →
    'let' variableName ('[' expression ']')? '=' expression ';'

The question mark means that the bracketed portion may appear once or not at all.

This one rule therefore accepts both:

let total = price;

and:

let values[index] = price;

The grammar is not a program written in Jack.

It is a metalanguage: a language used to describe another language.

That step upward matters.

Instead of arguing over thousands of examples, language designers can argue over the rule that generates them.

8. Finite rules describe unbounded structure

A program may contain an expression inside parentheses:

(price + tax)

That expression may contain another parenthesized expression:

(price + (tax * rate))

And another:

(price + (tax * (rate + adjustment)))

No language manual can list every possible depth.

Grammar handles the problem by allowing a category to lead back to itself.

A simplified description of a Jack term includes:

term → integerConstant
     | stringConstant
     | variableName
     | '(' expression ')'
     | subroutineCall

An expression contains terms.

A term may contain a parenthesized expression.

That inner expression contains more terms, one of which may contain another expression.

The rule is finite.

The structures it permits are not limited to one fixed depth.

This is recursion appearing not in a running program, but in the definition of a language.

9. Precision does not guarantee one answer

Writing a grammar formally does not automatically make the language unambiguous.

A set of precise rules may still allow the same tokens to acquire two different structures.

Consider a language that permits an if inside another if without requiring braces:

if A then if B then X else Y

Does else Y belong to the inner condition or the outer one?

Both readings can be described precisely. The problem is that the language has permitted both.

This is known as the dangling else problem.

Jack avoids that particular ambiguity by requiring braces around the statements controlled by if and else:

if (a) {
    if (b) {
        do x();
    }
} else {
    do y();
}

The braces make the ownership visible.

Jack makes another simplifying choice for expressions: it defines no general priority among binary operators. Parentheses must make required grouping explicit.

These restrictions are not merely inconveniences imposed on the programmer.

They are part of the language’s bargain:

Accept these explicit forms,
and the parser can recover one intended structure with less uncertainty.

10. The parser follows the rules

A grammar describes permitted structures.

A parser tries to recognize one of those structures in a token stream.

For Jack, a parser can be organized around operations that mirror the grammar:

compileClass
compileSubroutine
compileStatements
compileLet
compileIf
compileWhile
compileExpression
compileTerm

Suppose compileLet begins with the current token at let.

Its work follows the rule:

Expect the keyword let.
Expect an identifier.
If the next token is [, parse an index expression and expect ].
Expect =.
Parse an expression.
Expect ;.

The parser advances as each expectation is fulfilled.

When it reaches a component governed by another rule, it delegates:

compileLet calls compileExpression.
compileExpression calls compileTerm.
compileTerm may call compileExpression again.

The algorithm acquires the shape of the language it reads.

This style is called recursive descent.

The parser descends from larger grammatical forms into their smaller parts, using recursive calls when the grammar permits nesting.

11. The call stack learns to read

Consider the expression:

(price * (quantity + bonus)) + tax

The parser begins reading the outer expression.

It encounters ( and enters a parenthesized expression.

Inside, it reads price * and then encounters another (.

The first expression is not finished.

The second expression is not finished.

The parser must remember both suspended acts of reading while it handles:

quantity + bonus

The call stack from our earlier machine returns in a new role.

Each parser call preserves:

Which grammatical rule is active
How far through that rule the parser has progressed
Where reading should resume
What nested structure is being produced

When the innermost expression reaches ), its call returns.

The surrounding multiplication resumes.

When the next ) arrives, that call returns.

The outer addition resumes and accepts tax.

The stack no longer preserves only unfinished arithmetic or function behavior.

It preserves unfinished interpretation.

Recursion in the grammar is recognized by recursion in the parser, supported by recursion in the machine’s runtime.

12. The tree hidden inside the line

The original statement appeared flat:

let total = (price * quantity) + tax;

After parsing, its relationships can be shown as a tree:

let statement
├── destination: total
└── expression
    ├── grouped expression
    │   ├── price
    │   ├── *
    │   └── quantity
    ├── +
    └── tax

Nothing new has been added to the requested calculation.

What was implicit has become explicit.

The tree records containment:

The multiplication belongs inside the grouped expression.
The grouped expression belongs inside the larger expression.
The larger expression belongs inside the let statement.
The let statement belongs inside a sequence of statements.
That sequence belongs inside a subroutine body.

This hierarchy is what later compiler stages need.

They cannot translate a multiplication correctly until they know which two terms belong to it. They cannot translate a return until they know which expression, if any, supplies the returned value. They cannot determine the scope of a local declaration until they know which subroutine contains it.

Structure prepares meaning for action.

13. The compiler that deliberately produces no program

The syntax-analysis project in Nand to Tetris stops at an unusual point.

Its tokenizer writes classified tokens.

Its parser writes XML that displays the grammatical hierarchy.

A fragment resembles:

<letStatement>
  <keyword> let </keyword>
  <identifier> total </identifier>
  <symbol> = </symbol>
  <expression>
    ...
  </expression>
  <symbol> ; </symbol>
</letStatement>

The XML does not run.

It does not push a value, call a method, or alter a pixel.

That apparent uselessness is the point.

The project separates two questions that a complete compiler usually answers together:

Did we recover the program’s structure correctly?
                        ↓
What executable behavior should that structure produce?

By pausing between them, the learner can inspect the answer to the first question directly.

A missing node, misplaced term, or incorrectly nested statement becomes visible before code generation can conceal the mistake inside wrong behavior.

The XML is a record of reading.

14. Correct grammar can carry nonsense

The parser is concerned with form.

It does not know whether the program expresses a sensible idea.

This statement has the shape of a Jack assignment:

let total = true + square;

There is a let keyword, a destination, an equals sign, an expression, and a semicolon. The expression contains terms separated by an allowed operator.

The grammar can accept the structure even though adding truth to a square does not describe a sensible order total.

The Nand to Tetris project uses this separation deliberately. One test program replaces meaningful expressions with single identifiers. The result may be nonsensical as a computation while remaining grammatically valid.

This exposes a boundary:

Syntax asks:
Does this sequence have a permitted structure?

Semantics asks:
What does that structure mean?

A parser can prove that tokens fit the grammar without understanding what the program is for.

The machine has learned to read only in a narrow sense.

That narrowness is what makes the task mechanical.

15. The moment a promise breaks

Now remove the semicolon:

let total = price

The parser enters a letStatement.

It accepts let.

It accepts the identifier total.

It accepts the equals sign.

It parses price as an expression.

Then the grammar requires ;.

If the file ends or another incompatible token appears, the current structure cannot be completed.

This is a syntax error.

The parser has not discovered that the programmer’s goal is mistaken. It has discovered that the token stream cannot fulfill the grammatical promise currently in progress.

Useful error reporting requires more work. The parser should preserve where the failure occurred, what it had recognized, and what token it expected. A technically correct message can still be unhelpful if the true mistake occurred several tokens earlier.

Failure reveals the parser’s limits.

It knows the shapes it can continue.

It does not know what the author meant to write instead.

16. From private intuition to public structure

Return to the ALGOL committee.

Its members needed a language that could cross machines, organizations, and national borders. A compiler writer in another country could not depend on having shared the designers’ conversations.

The formal grammar moved part of that private understanding into a public artifact.

Designer’s intuition
        ↓
Written grammar
        ↓
Parser implementation
        ↓
Recovered program structure

Each step can be inspected.

The grammar does not contain every fact about a language. The ALGOL report still needed prose to explain meaning. A Jack grammar can say that a method call is permitted without explaining how an object reference will be passed at runtime.

But syntax no longer has to live only in examples or in the habits of one compiler.

It can become an agreement of its own.

That agreement allows different parsers to recognize the same structures even when they are written in different implementation languages and run on different computers.

17. What a parser really is

A parser is often defined as a program that analyzes source code according to a grammar.

That is correct.

But the transformation is easier to see when we compare its input and output.

The input is sequence:

token after token after token

The output is relationship:

This belongs inside that.
This begins a statement.
This completes an expression.
These arguments belong to this call.
These statements belong to this block.

A tokenizer teaches the compiler where the pieces are.

A grammar describes the permitted ways those pieces may be arranged.

A parser attempts to reconstruct one permitted arrangement from the pieces it receives.

It does not read as a person reads.

It does not imagine the moving square, question the order total, or recognize an elegant algorithm.

Its promise is smaller:

Give me tokens that follow this grammar.
I will reveal the structure they imply.

That promise was made possible by people who learned to describe languages with enough precision that their structure could be recovered mechanically.

The source file is no longer merely text.

It has become a tree.

But the tree still does nothing.

The parser knows that price * quantity is a multiplication inside an expression inside a let statement. It knows that square.moveRight() is a qualified subroutine call inside a do statement. Determining that square names an object—and that the call must therefore receive the object’s address—belongs to the work still ahead.

It has not yet produced the stack commands that multiply the values, preserve the result, locate the object, or perform the call.

The next question is no longer how the compiler can recognize a program.

It is how recognized structure becomes executable behavior.

How can meaning become motion?