Lexical Analysis — The Scanner

Lexical analysis (scanning) is the first phase of compilation. It reads the raw source code character by character and groups characters into TOKENS — the smallest meaningful units of the language.

What is a token?
A token is a pair (type, value):
- Keywords: INT, IF, WHILE, RETURN — reserved words of the language
- Identifiers: variable names, function names — matched by regex [a-zA-Z_][a-zA-Z0-9_]*
- Literals: numbers (42, 3.14), strings ("hello"), booleans (true, false)
- Operators: +, -, *, /, ==, !=, <=, >=, &&, ||
- Punctuation: (, ), {, }, [, ], ;, ,, .
- Whitespace and comments: usually DISCARDED (not passed to parser)

The scanner ignores whitespace and comments — they carry no semantic meaning (usually). This is why you can format code however you like.

How it works — Finite Automata:
Each token type is described by a regular expression. The scanner builds a DFA from all these regexes combined. As it reads characters, it follows DFA transitions. When it reaches an accepting state and the next character doesn't extend the current token, it emits the token and resets.

Maximal munch rule: always consume the longest possible token. "==" is one EQUALS_EQUALS token, not two EQUALS tokens. "integer" is one IDENTIFIER, not keyword INT + identifier "eger".

Lexer vs Scanner: used interchangeably. The tool that builds scanners from regex specs is called lex (Unix) or flex (faster lex). Python's tokenize module does exactly this.

Symbol Table: identifiers found during lexing are entered into the symbol table — a data structure that maps names to their properties (type, scope, memory location). Built during lexing, enriched during semantic analysis.

Lexical errors: if no token pattern matches the current input → lexical error. "int x = @5;" → '@' is not part of any valid token → error: invalid character '@'.

Token attributes: some tokens carry values needed later. NUM token carries the numeric value. ID token carries the string name. The parser needs these to build the AST correctly.

1import re
2from enum import Enum, auto
3from dataclasses import dataclass
4
5# ── Token types ────────────────────────────────────────
6class TT(Enum):
7    # Literals
8    NUMBER   = auto()
9    FLOAT    = auto()
10    STRING   = auto()
11    # Keywords
12    IF       = auto()
13    ELSE     = auto()
14    WHILE    = auto()
15    RETURN   = auto()
16    INT      = auto()
17    FLOAT_KW = auto()
18    # Identifiers
19    ID       = auto()
20    # Operators
21    PLUS     = auto()
22    MINUS    = auto()
23    STAR     = auto()
24    SLASH    = auto()
25    ASSIGN   = auto()
26    EQ       = auto()
27    NEQ      = auto()
28    LT       = auto()
29    GT       = auto()
30    LEQ      = auto()
31    GEQ      = auto()
32    AND      = auto()
33    OR       = auto()
34    NOT      = auto()
35    # Punctuation
36    LPAREN   = auto()
37    RPAREN   = auto()
38    LBRACE   = auto()
39    RBRACE   = auto()
40    SEMI     = auto()
41    COMMA    = auto()
42    # Special
43    EOF      = auto()
44
45@dataclass
46class Token:
47    type: TT
48    value: object
49    line: int
50    col: int
51    def __repr__(self):
52        return f"Token({self.type.name}, {self.value!r}, line={self.line})"
53
54# ── Lexer ──────────────────────────────────────────────
55class Lexer:
56    KEYWORDS = {
57        "if": TT.IF, "else": TT.ELSE, "while": TT.WHILE,
58        "return": TT.RETURN, "int": TT.INT, "float": TT.FLOAT_KW,
59    }
60
61    # Order matters: longer patterns first, keywords before identifiers
62    TOKEN_PATTERNS = [
63        (r'd+.d+',          TT.FLOAT),
64        (r'd+',               TT.NUMBER),
65        (r'"[^"]*"',           TT.STRING),
66        (r'==',                TT.EQ),
67        (r'!=',                TT.NEQ),
68        (r'<=',                TT.LEQ),
69        (r'>=',                TT.GEQ),
70        (r'&&',                TT.AND),
71        (r'||',              TT.OR),
72        (r'=',                 TT.ASSIGN),
73        (r'+',                TT.PLUS),
74        (r'-',                 TT.MINUS),
75        (r'*',                TT.STAR),
76        (r'/',                 TT.SLASH),
77        (r'<',                 TT.LT),
78        (r'>',                 TT.GT),
79        (r'!',                 TT.NOT),
80        (r'(',                TT.LPAREN),
81        (r')',                TT.RPAREN),
82        (r'{',                TT.LBRACE),
83        (r'}',                TT.RBRACE),
84        (r';',                 TT.SEMI),
85        (r',',                 TT.COMMA),
86        (r'[a-zA-Z_]w*',      TT.ID),     # identifiers (and keywords)
87        (r'[ 	
]+',          None),       # whitespace — discard
88        (r'
89',                None),       # newline — discard (track line)
90        (r'//[^
91]*',          None),       # line comment — discard
92    ]
93
94    def __init__(self, source: str):
95        self.source  = source
96        self.pos     = 0
97        self.line    = 1
98        self.col     = 1
99        self.pattern = re.compile(
100            '|'.join(f'(?P<p{i}>{p})' for i, (p, _) in enumerate(self.TOKEN_PATTERNS))
101        )
102
103    def tokenize(self):
104        tokens = []
105        for match in self.pattern.finditer(self.source):
106            idx  = next(i for i in range(len(self.TOKEN_PATTERNS)) if match.group(f'p{i}') is not None)
107            pat, tt = self.TOKEN_PATTERNS[idx]
108            val = match.group()
109
110            if val == '
111':
112                self.line += 1
113                self.col = 1
114                continue
115            if tt is None:
116                continue    # discard whitespace/comments
117
118            # Check if identifier is actually a keyword
119            if tt == TT.ID and val in self.KEYWORDS:
120                tt = self.KEYWORDS[val]
121
122            # Convert value types
123            if tt == TT.NUMBER: val = int(val)
124            elif tt == TT.FLOAT: val = float(val)
125            elif tt == TT.STRING: val = val[1:-1]  # strip quotes
126
127            tokens.append(Token(tt, val, self.line, match.start() - self.source.rfind('
128', 0, match.start())))
129
130        tokens.append(Token(TT.EOF, None, self.line, self.col))
131        return tokens
132
133# ── Test the lexer ─────────────────────────────────────
134source = """
135int factorial(int n) {
136    if (n <= 1) {
137        return 1;
138    }
139    return n * factorial(n - 1);
140}
141"""
142
143lexer  = Lexer(source)
144tokens = lexer.tokenize()
145
146print("Source code:")
147print(source)
148print("Tokens:")
149for tok in tokens:
150    print(f"  {tok}")
151
152# ── Python's own tokenizer ─────────────────────────────
153import tokenize, io
154print("
155Python's tokenize module on 'x = 1 + 2 * 3':")
156src = "x = 1 + 2 * 3
157"
158for tok in tokenize.generate_tokens(io.StringIO(src).readline):
159    if tok.type != tokenize.NEWLINE and tok.type != tokenize.ENDMARKER:
160        print(f"  {tokenize.tok_name[tok.type]:10} {tok.string!r}")