From Tokens to Syntax
Parsing is the process of recognizing syntactic structure in a token stream. The lexer handled lexical structure: it decided where identifiers, literals, operators, and punctuation began and ended. The parser now determines how those pieces fit together.
Consider a block:
{
answer := 42
print(answer)
}When the parser sees {, the language grammar says that a block has begun. The
parser repeatedly parses statements until it reaches the matching }. If the
file ends first, the source is syntactically incomplete and the parser can
report that a closing brace was expected.
Different languages express the same structure differently. C-like languages
often delimit blocks with braces. Lua uses keywords such as then, do, and
end. Python uses indentation. None of these spellings is inherently a block;
the grammar gives the spelling its role.
Grammar
The grammar describes which token sequences form valid language constructs. A few direct rules are enough to make the first parser concrete:
file -> statement* EOF
block -> "{" statement* "}"
declaration -> IDENTIFIER ":=" expression
return_stmt -> "ret" expression?
statement -> block | return_stmt | declaration | expressionThe arrow can be read as "consists of." statement* means zero or more
statements, and expression? means that the expression is optional.
For example:
block -> "{" statement* "}"says that a block begins with a left brace, contains any number of statements, and ends with a right brace.
These rules are both documentation and implementation guidance. A recursive descent parser often has functions that correspond almost directly to the grammar:
Ast *parse_file(Parser *parser);
Ast *parse_statement(Parser *parser);
Ast *parse_block(Parser *parser);
Ast *parse_expression(Parser *parser);If two different rules can consume the same token sequence in incompatible ways, the language is ambiguous unless you add another rule that resolves the choice.
Validation
The parser validates syntax. It can determine that:
- a block that begins with
{eventually closes with}; - a call that begins with
(contains a valid argument list and closes with); - a binary operator has an expression on both sides;
- an
ifstatement contains the punctuation and clauses required by the grammar; and - every consumed sequence corresponds to some recognized construct.
If the parser's only job is to build the AST, then it usually should not decide whether an identifier refers to an existing variable, whether a constant can be assigned to, whether a function receives the correct number of arguments, or whether two runtime values can be added.
As the language designer, however, you're allowed to combine stages, and some language rules require earlier feedback. The practical rule is to avoid making the parser understand facts that are easier to establish once a complete syntactic structure exists.
A compiler can guarantee that a source file satisfies the language rules it checks.
It cannot generally guarantee that the program will behave as its author intended, terminate, or remain correct for every possible input.
"Syntactically valid" and "correct program" are very different claims.
Connecting the Lexer and Parser
A parser needs access to the current token and usually a small amount of lookahead. A minimal parser might contain:
typedef struct Parser {
Lexer lexer;
Token previous;
Token current;
Token next;
Arena *arena;
bool failed;
} Parser;elf uses exactly this kind of three-token window. Consuming a token shifts the window and asks the lexer for one more:
Token consume_token(Parser *parser) {
Token result = parser->current;
parser->previous = parser->current;
parser->current = parser->next;
parser->next = lex_token(&parser->lexer);
return result;
}Three tiny operations cover most parser control flow:
bool peek(Parser *parser, Token_Kind kind); // Is this the current token?
bool pick(Parser *parser, Token_Kind kind); // If so, consume it.
Token take(Parser *parser, Token_Kind kind); // Require it or report an error.That lets grammar code remain direct:
Ast *parse_block(Parser *parser) {
Token open = take(parser, TOKEN_LEFT_BRACE);
Ast_List statements = {0};
while (!peek(parser, TOKEN_RIGHT_BRACE) &&
!peek(parser, TOKEN_EOF)) {
list_push(&statements, parse_statement(parser));
}
take(parser, TOKEN_RIGHT_BRACE);
return make_block(parser, open.site, statements);
}You do not need an elaborate parser framework to begin. A token cursor, a few helpers, and functions that mirror the grammar are enough.
Building the AST
The parser's output is usually an AST. Every node represents one meaningful syntactic construct and points to the nodes contained by that construct.
A small C representation can use a kind plus a union:
typedef enum Ast_Kind {
AST_IDENTIFIER,
AST_INTEGER,
AST_BINARY,
AST_CALL,
AST_DECLARATION,
AST_BLOCK,
AST_IF,
AST_RETURN,
} Ast_Kind;
typedef enum Binary_Operator {
BINARY_ADD,
BINARY_MULTIPLY,
// ...
} Binary_Operator;
typedef struct Ast Ast;
struct Ast {
Ast_Kind kind;
Source_Site site;
union {
Atom *atom;
i64 integer;
struct {
Binary_Operator operator;
Ast *left;
Ast *right;
} binary;
struct {
Ast **items;
usize count;
} block;
};
};The kind determines which union member is valid. A binary node uses left and
right; an integer node uses integer; and a block stores a sequence of statement
nodes.
The tree is abstract because it does not preserve every token. Parentheses, commas, and braces often disappear once they have done their job of determining structure. Source locations remain because diagnostics and tools still need to connect a node to the program that produced it.
In a simple implementation, each parsed construct becomes a fresh node and the result is an ordinary ownership tree. More advanced compilers may share nodes or attach links that make the full structure graph-like, but that complication is unnecessary here.
elf allocates AST nodes from an arena. All nodes for one compilation have nearly the same lifetime, so individual allocation and destruction provide little value. The parser creates nodes as it advances, later stages consume the tree, and the entire arena can be released together.
Statements and Expressions
The distinction between statements and expressions varies by language, but it is still useful.
An expression can be evaluated to produce a value:
42
left + right
make_value()
table.nameA statement primarily performs an action or controls execution:
value := 42
value = value + 1
ret value
while running ? {}Language design determines the boundary. C treats assignment as an expression, which is why this works:
x = y = 42;y = 42 assigns to y and also yields the assigned value, allowing that value
to become the right operand of x = ....
Our small language can deliberately make assignment a statement. Then
x = y = 42 is not legal syntax, and the parser only recognizes assignment at
the statement level. elf currently follows this general structure: it parses an
expression-like destination first, then recognizes declaration or assignment
operators while parsing the surrounding statement.
Conditionals present the same design choice. A conventional if statement
selects which action to perform. An if expression produces one of two values.
Instead of copying C's condition ? true_value : false_value, a language could
eventually let its ordinary if form yield a value. That is a language-design
decision, not something forced by parsing theory.
Assignment Targets, lvalues, and rvalues
The terms lvalue and rvalue came historically from the left and right sides of assignment, but their precise meaning—especially in C and C++—is more specific than "returns a value."
For this parser, simpler terminology is enough:
- a value expression can be evaluated to obtain a value;
- an assignment target identifies somewhere a value can be stored.
An identifier can do both jobs:
copy := value // read value
value = 42 // write valueA field expression can also appear in either context:
copy := table.name
table.name = "new name"The parser can construct the same field-access shape in both cases. A later stage sees the surrounding assignment and validates whether that shape is a legal destination, then emits the appropriate read or write operation.
Keeping that semantic decision out of the parser is useful. The parser records what the programmer wrote; lowering determines what operation the structure requires.
Parse Primary, Prefix, and Postfix Expressions
Expression parsing becomes easier when split into layers.
Primary expressions are the indivisible starting points:
identifier
integer literal
string literal
parenthesized expression
function literal
table literalPrefix operators appear before their operand:
-value
~maskPostfix operations extend an already-parsed expression:
value.field
value[index]
value(argument)
value.field(argument)[index]A useful implementation first parses one primary or prefix expression, then loops while the next token can extend it:
Ast *parse_postfix(Parser *parser) {
Ast *value = parse_primary_or_prefix(parser);
for (;;) {
if (pick(parser, TOKEN_DOT)) {
value = parse_field(parser, value);
} else if (pick(parser, TOKEN_LEFT_BRACKET)) {
value = parse_index(parser, value);
} else if (peek(parser, TOKEN_LEFT_PAREN)) {
value = parse_call(parser, value);
} else {
break;
}
}
return value;
}This naturally makes value.field(argument)[index] left-associated: begin with
value, attach .field, attach the call, then attach the index.
Binary Expressions Need Precedence
A flat sequence such as:
1 + 2 * 3has more than one possible tree:
Multiply Add
|- Add |- Integer(1)
| |- Integer(1) `- Multiply
| `- Integer(2) |- Integer(2)
`- Integer(3) `- Integer(3)Normal arithmetic rules choose the second tree because multiplication has higher precedence than addition. The parser must encode that rule.
You can use a Pratt parser, recursive functions for every precedence level, or precedence climbing. elf uses precedence climbing. In simplified form:
Ast *parse_subexpression(Parser *parser, int minimum) {
Ast *left = parse_postfix(parser);
for (;;) {
Binary_Operator op = binary_operator(parser->current.kind);
int precedence = operator_precedence(op);
if (precedence <= minimum) {
break;
}
Token operator_token = consume_token(parser);
Ast *right = parse_subexpression(parser, precedence);
left = make_binary(parser, operator_token.site, op, left, right);
}
return left;
}The exact comparison changes depending on associativity conventions, but the idea is stable. Parse a left expression, inspect the following operator, and only absorb operators that bind tightly enough in the current recursive call.
The result for 1 + 2 * 3 becomes:
Add
|- Integer(1)
`- Multiply
|- Integer(2)
`- Integer(3)Print and verify this tree before moving on. A precedence bug can produce a completely valid AST that represents the wrong program.
Statement Parsing
Statement parsing is usually direct dispatch. The current token identifies special statement forms; everything else begins an expression or assignment:
Ast *parse_statement(Parser *parser) {
switch (parser->current.kind) {
case TOKEN_LEFT_BRACE: return parse_block(parser);
case TOKEN_IF: return parse_if(parser);
case TOKEN_WHILE: return parse_while(parser);
case TOKEN_FOR: return parse_for(parser);
case TOKEN_RET: return parse_return(parser);
default: return parse_expression_statement(parser);
}
}An if parser then follows its grammar in order. For elf's current syntax:
if condition ? {
ret 1
} else {
ret 0
}the implementation roughly does this:
consume "if"
parse the condition expression
require "?"
parse the true statement or block
if "elif" appears, parse another conditional
otherwise, if "else" appears, parse the false statement or block
construct AST_IFThe source syntax could have used parentheses, colons, then, or something
else. Once you choose the grammar, the parser is mostly the mechanical act of
recognizing that choice.
This is why parsing is fun: language design becomes executable here.
Fail Clearly and Always Make Progress
At minimum, distinguish between checking for a token and requiring one. If the
grammar requires ) and the current token is }, report the expected token and
the actual token at the current source location.
expected ')', got '}'A parser also needs to avoid getting stuck. A loop that repeatedly calls
parse_statement without consuming anything will never terminate. elf guards
against this by remembering the token before parsing a statement and reporting
an internal parse failure if the parser returns without advancing.
Early versions can stop at the first error. Later, error recovery can skip to a likely synchronization point such as a newline, semicolon, closing brace, or statement keyword and continue collecting diagnostics. Recovery is useful, but it is not required to prove the basic parser architecture.
Keep error nodes or a clear failure sentinel so malformed input cannot be mistaken for an absent optional construct. "There was no else clause" and "the else clause failed to parse" are different states.
Test Tree Shapes, Not Just Success
The parser accepting a program is not enough. It may accept the correct tokens and build the wrong tree.
For this source:
x := 1 + 2 * 3a focused test should verify:
FILE
`- BLOCK
`- DECLARATION
|- IDENTIFIER("x")
`- ADD
|- INTEGER(1)
`- MULTIPLY
|- INTEGER(2)
`- INTEGER(3)Useful parser tests cover:
- operator precedence and associativity;
- nested blocks and matching delimiters;
- calls, fields, and indexes chained together;
- declarations versus assignments;
- optional clauses such as
elseand optional return values; - malformed expressions and missing delimiters;
- source locations attached to the resulting nodes; and
- newline rules if the language uses them to terminate expressions.
elf's parser tests inspect the kinds and children of AST nodes directly. They verify, for example, that multiplication nests inside addition, function parameters remain ordered, range bounds are preserved, and multiline comments interact correctly with statement boundaries.
An AST printer is still worth building. Tests catch known cases; a readable tree lets you inspect new syntax while designing it.
Keep Meaning Out Until You Have the Structure
The parser's job is not to solve the whole language. It transforms:
flat token stream -> grammatical treeKeep the implementation close to the grammar. Use small token helpers. Build fresh, source-located AST nodes. Parse primary and postfix expressions before handling binary precedence. Dispatch statements from their leading token. Make every parser loop prove that it advanced.
Most importantly, let the parser record what was written before asking later stages what it means. Name resolution, lexical scopes, assignment validation, closure capture, and control-flow lowering become much easier once they can operate on a complete tree instead of a moving token stream.
The lexer categorized the text. The parser recovered its structure. In the next stage, we can finally begin resolving that structure into explicit operations.