Lexical Analyzer Project

Introduction and Learning Goals

Building a lexical analyzer from scratch is your first hands-on encounter with how compilers actually process source code. Think of the lexer as a word recognizer — just as a human reader groups letters into words, the lexer groups characters into meaningful units called tokens. This project will teach you to handle real-world complications: multi-character operators (is = an assignment or the start of ==?), string literals with escape sequences, nested comments, and error recovery when encountering unexpected characters.

By completing this project, you will understand why lexical analysis exists as a separate phase, how regular expressions translate into efficient finite automata, and how tools like Flex automate this process. You will build a lexer for a C-like language that produces a stream of classified tokens suitable for feeding into a parser.

Project Specification

Input: Source code written in a C-like language Output: A sequence of tokens, each with its type, lexeme (actual text), and source location (line number)

Our lexer must recognize these token categories:

Keywords: if, else, while, for, int, float, char, void, return, struct Identifiers: Variable and function names following the pattern [a-zA-Z_][a-zA-Z0-9_]* Integer literals: Sequences of digits, optionally with hex prefix 0x Float literals: Digits with decimal point, optional scientific notation String literals: Characters between double quotes, supporting escape sequences Operators: Arithmetic (+, -, *, /, %), relational (<, >, <=, >=, ==, !=), logical (&&, ||, !), assignment (=, +=, -=) Delimiters: {, }, (, ), [, ], ;, , Comments: Single-line (//) and multi-line (/* ... */) — skipped, not tokenized

Implementation with Flex

Here is the complete Flex specification:

Test Input Program

Create a file called test_input.c:

Expected Output

Handling Tricky Cases

Longest match for operators: When the input contains <=, the lexer must recognize it as a single <= token, not as < followed by =. Flex handles this automatically via the longest-match rule.

Keywords vs identifiers: The word integer should be an identifier, not keyword int followed by identifier eger. Again, longest match handles this — the identifier pattern matches all 7 characters.

Unterminated strings: If a string literal is never closed, the basic pattern fails. Add error handling:

Nested comments: Standard C comments do not nest, but if your language requires it, use a counter with start conditions.

Building and Running

Extension Ideas

Once your basic lexer works, try adding these features to deepen your understanding:

• Symbol table population: Store each identifier in a hash table during lexing, tracking first occurrence line
• Token statistics: Count tokens by category, most frequent identifiers
• Preprocessor directives: Recognize #include, #define as special tokens
• Unicode identifiers: Allow non-ASCII characters in identifiers
• Error recovery: After an error, skip to the next whitespace and continue tokenizing

Key Takeaways

This project demonstrates that lexical analysis is fundamentally about pattern matching. Each token type corresponds to a regular expression, and the lexer applies the longest-match-first-rule-priority strategy to unambiguously classify every character in the source code. The separation of lexing from parsing simplifies both tasks — the parser never needs to worry about whitespace, comments, or multi-character operator recognition because the lexer has already handled these concerns.