Series Overview
Building a Toy Language Processor (Part 2 of 2)
In the previous chapter, we covered the high-level architecture of a compiler, mapping out the standard phases from lexical analysis down to target code generation.
Before we write our lexer, let's clarify a quick design choice regarding our backend: we are building a source-to-source compiler (a transpiler).
Instead of generating raw machine instructions or bytecode in our final phase, our compiler will output Go source code.
STANDARD Source Code ──> [ Lexer ──> Parser ──> AST ] ──> Code Generator ──> Go Source Code
└──────── Frontend ────────┘ └─ Backend ─┘
Compiling high-level STANDARD code into Go lets us focus on building a real compiler frontend without needing to write a custom execution engine. And because lexical analysis and parsing are backend-agnostic, our lexer and parser remain 100% identical to those in a traditional compiler.
Now, let's build the first phase: Lexical Analysis.
Lexical analysis is the transformation of source code into tokens. This is done by a lexer (also called scanner or tokenizer).
The source code is just a string, and we need to represent it in other forms that are easier to work with. This is the essence of the lexer.
The lexer transforms the source code into tokens. Tokens are small data structures that model the structure of the source code. They are fed to the parser, which transforms them to an Abstract Syntax Tree (AST).
AST is a tree representation of the source code of a computer program that conveys the structure of the source code.
Building the Lexer
To start building the lexer, first, we need to define a token.
// ...token/token.go
type TokenType string
type Token struct {
Type TokenType
Literal string
}
I'll do a manual transformation of our source code to tokens, it'll be self-explanatory why we represent the Token this way.
Take a look at this source code:
LET name
The output tokens:
[
Token{Type: token.LET, Literal: "LET"},
Token{Type: token.IDENT, Literal: "name"}
]
The Token retains its type, and its literal. Next, we're going to be crafting our lexer. We'll need a data structure to hold the source code and other metadata for manipulating the source code.
type Lexer struct {
source string
}
We'll add Lexer.position and Lexer.readPos to the Lexer structure. The diagram below helps understand the usefulness of this structure.
The updated source code will be:
type Lexer struct {
source string
position int
readPos int
ch byte
}
The ch field stores the current position character of the source. This is useful for preview during tokenisation. The next step will be converting the source into tokens. But firstly, let's define some token type.
type TokenType string
const (
EOF = "EOF" //end-of-file
ILLEGAL = "ILLEGAL" // the token is unknown
// keywords
PRINT = "PRINT"
LET = "LET"
WHILE = "WHILE"
REPEAT = "REPEAT"
ENDWHILE = "ENDWHILE"
IDENT = "IDENTIFIER"
// operators
ASSIGN = "="
PLUS = "+"
MINUS = "-"
BANG = "!"
ASTERISK = "*"
SLASH = "/"
)
With all these in place, we'll create some functions for processing the next token in the source. The function consumes the next token within the source code, and advances the navigation state.
func (l *Lexer) readChar() {
if l.readPos >= len(l.source) {
l.ch = 0 // NUL
} else {
l.ch = l.source[l.readPos]
}
l.position = l.readPos
l.readPos += 1
}
func (l *Lexer) NextToken() token.Token {
var tok token.Token
switch lexer.ch {
case '=':
tok = newToken(token.ASSIGN, lexer.ch)
case '+':
tok = newToken(token.PLUS, lexer.ch)
case '-':
tok = newToken(token.MINUS, lexer.ch)
case '!':
tok = newToken(token.BANG, lexer.ch)
case '*':
tok = newToken(token.ASTERISK, lexer.ch)
case '/':
tok = newToken(token.SLASH, lexer.ch)
case 0:
tok = newToken(token.ILLEGAL, "")
}
}
I won't be showing code snippets as frequently as I've done earlier, I'd rather be giving an overview of what I did; Readers can find the code in my GitHub repo.
Our lexer can now consume operators. Next, we need to consume keywords and identifiers. We'll store a map of keywords to token type, after reading an identifier, if it's present in the map, we'll replace it with the paired token type.
//[switch]
default:
if isLetter(lexer.ch) {
tok.Literal = lexer.readIdentifier()
tok.Type = token.LookupIdent(tok.Literal)
return tok;
}
//...
LookupIdent is a helper function that checks if the identifier is an existing keyword. Here's the implementation of the readIdentifier method.
func (l *Lexer) readIdentifier() string {
pos := l.position
for isLetter(l.ch) {
l.readChar()
}
return l.source[pos:l.position]
}
The function keeps advancing the position pointer till it encounters a character that is not a valid letter. We compare the identifier with our keywords map, if there's no match, we'll assign token.IDENT.
Handling Indentations
Most programming languages use explicit characters like curly braces ({}) or keywords to mark where a block begins or ends. In STANDARD, we rely on significant tabs and line break just like Python.
This introduces a new challenge for our lexer: how do we tell our parser that a block of code has started or ended when there are no physical characters in the text?
Virtual Tokens and the Indentation Stack
The answer lies in virtual tokens. Tokens that don't directly correspond to a printed keyword or operator in the source code, but are synthesized by the lexer based on layout:
- INDENT: Synthesised when stepping deeper into a tabbed block.
- DEDENT: Synthesised when exiting one or more tabbed blocks.
- NEWLINE: Synthesised at the end of a non-empty statement line.
Because a single line change can drop out of multiple nested blocks at once (for example, moving from 3 tabs directly back to 0 tabs), our lexer might need to emit multiple DEDENT tokens from a single character inspection.
To manage this, we add three new fields to our Lexer struct:
type Lexer struct {
source string
position int
readPos int
ch byte
indentStack []int
tokenQueue []token.Token
atLineStart bool
}
When atLineStart is true, before parsing standard characters like numbers or identifiers, we invoke a function which does this:
- Count Tabs: We measure the number leading
\tbytes on new line. - Ignore Empty Lines: If the line contains only newlines or whitespce, we ignore it and avoid altering our indentation state.
- Compare Depth: We compare the count of leading tabs against the top of
indentStack:tabs > top: We pushtabsontoindentStackand push anINDENTtoken into thetokenQueue.tabs == top: The block depth has changed.tabs < top: We pop values off theindentStackuntil we matchtabs. For every value popped, we push a newDEDENTtoken into thetokenQueue.
Here is the implementation in Go:
func (l *Lexer) consumeIndentation() {
for l.ch == '\n' {
l.readChar()
}
tabs := 0
for l.ch == '\t' {
tabs++
l.readChar()
}
if l.ch == '\n' || l.ch == 0 {
return
}
currentIndent := l.indentStack[len(l.indentStack) - 1]
if tabs > currentIndent {
l.indentStack = append(l.indentStack, tabs)
l.tokenQueue = append(l.tokenQueue, token.Token{Type: token.INDENT, Literal: '\t'})
} else if tabs < currentIndent {
for len(l.indentStack) > 0 && l.indentStack[len(l.indentStack) - 1] > tabs {
l.indentStack = l.indentStack[:len(l.indentStack)-1]
l.tokenQueue = append(l.tokenQueue, token.Token{Type: token.DEDENT, Literal: ""})
}
}
if l.indentStack[len(l.indentStack) - 1] != tabs {
l.tokenQueue = append(l.tokenQueue, token.Token{Type: token.ILLEGAL, Literal: "Indentation Error"})
}
}
Integrating with NextToken()
Because consumeIndentation() can generate several DEDENT tokens at once into the token queue, NextToken() must check drain this queue before reading new characters from source:
func (l *Lexer) NextToken() token.Token {
if len(l.tokenQueue) > 0 {
tok := l.tokenQueue[0]
l.tokenQueue = l.tokenQueue[1:]
}
if l.atLineStart {
l.atLineStart = false
l.consumeIndentation()
if len(l.tokenQueue) > 0 {
tok := l.tokenQueue[0]
l.tokenQueue = l.tokenQueue[1:]
return tok
}
}
l.skipWhitespace()
var tok token.Token
switch l.ch {
case '\n':
tok = newToken(token.NEWLINE, l.ch)
l.atLineStart = true
l.readChar()
return tok
case 0:
// Flush remaining open blocks at EOF
for len(l.indentStack) > 1 {
l.indentStack = l.indentStack[:len(l.indentStack)-1]
l.tokenQueue = append(l.tokenQueue, token.Token{Type: token.DEDENT, Literal: ""})
}
if len(l.tokenQueue) > 0 {
tok = l.tokenQueue[0]
l.tokenQueue = l.tokenQueue[1:]
return tok
}
tok = token.Token{Type: token.EOF, Literal: ""}
// ... handle operators, identifiers, and numbers
}
l.readChar()
return tok;
}
To support multi-character operators like ==, !=, <=, and >=, we implement peekChar(). It inspects the character at readPos without advancing the lexer's position pointers.
//[switch...]
case '=':
{
if lexer.peekChar() == '=' {
ch := lexer.ch
lexer.readChar()
literal := string(ch) + string(lexer.ch)
tok = token.Token{Type: token.EQ, Literal: literal}
} else {
tok = newToken(token.ASSIGN, lexer.ch)
}
}
case '!':
{
if lexer.peekChar() == '=' {
ch := lexer.ch
lexer.readChar()
literal := string(ch) + string(lexer.ch)
tok = token.Token{Type: token.NOT_EQ, Literal: literal}
} else {
tok = newToken(token.BANG, lexer.ch)
}
}
What's Next?
With our lexer complete, we can transform raw STANDARD code into a clean stream of tokens.
Next, we will tackle the Parser, building an Abstract Syntax Tree (AST) to structure these tokens for code generation.
Find the full project source code here . Stay tuned for Part 3!