Scanners

Overview

Scanners, or lexical analyzers, are the underlying system that supports Compilers. Their task is to transform a stream of characters into a stream of words in the input language. Interestingly, the scanner is the only phase in the entire compilation process to touch every single character in the input. The nuance of scanners is incredible, relying on fascinating techniques like Regular Expressions, Finite Automata, Deterministic Finite Automata, Nondeterministic Finite Automata, and other cool, yet esoteric, concepts.

From the Ground Up

As mentioned above, the overarching goal of a scanner is to produce a stream of words from an input stream of characters. Of course, this is an insanely in-depth process given the complexity of programming languages. Just a few things to start thinking about are:

1. How do we determine validity of a given stream of characters?
2. How can we accurately detect words?
3. How can it enforce grammatical structure?

There are many more questions to be asked and answered, but lets dive into the basics. The root of scanner construction is based on formal language theory, being modeled as recognizers that simulate deterministic finite automata. The compiler writer, then, must specify the structure of the language using a robust set of regular expressions. The most atomic part of a scanner is known as a lexeme, or the actual text for a word recognized by the scanner. The lexeme is paired with its corresponding syntactic categoryWhich is essentially the scanner equivalent to the "part of speech" in English. Together, <lexeme, category> represents a token.

Now that we have some general definitions down, lets answer our first big question: how can we determine what a "word" is? The first step here is microsyntax, which specifies how to turn groups of characters into words. This, of coure, is not a compiler-specific term. Languages like english have simple microsyntax, like adjacent characters forming a word that is then terminated by a space. However, what is specific to compilers is the reservation of keywords, or words reserved for a specific purpose that cannot be used as a regular word.

The Implementation

All of this sounds pretty straightforward so far. However, the real depth comes when we try to go about creating an intelligent system that can do this autonomously. Funnily enough, this brings us to the domain known as automata. The premise behind automata, at least in the context of what we're talking about here, is to create a state-machine that either accepts or rejects input. Naively, we can map every single word in our language's dictionary to a collection of states that either into $s_{i}$ or $s_{e}$, where $s_{i}$ is the $ith$ state that is either accepting or not the end-state, and $s_{e}$ is the error state.

More formally, we introduce the idea of finite automata, a mathematical formalism recognizers that consists of a finite amount of states $S$, an alphabet $\sum$, a transition function $\delta(s,c)$, a start state $s_0$, and a set of accepting states $S_A$. Within this branch, we see the emergence of two unique subsets: Nondeterministic Finite Automata and Deterministic Finite Automata