Lexical Analysis: Tokens, Lexemes, Automata & Scanners

TAKEAWAYS:

• Lexical analysis converts source code into tokens (lexemes) using regular expressions and finite automata (DFA/NFA).
• A scanner (lexical analyzer) reads input, skips whitespace/comments, and groups characters into tokens (e.g., if, 42, +) via deterministic finite automata (DFA).
• Regular expressions define token patterns (e.g., \d+ for integers), while lexeme is the actual sequence matched (e.g., 123).
• NFA to DFA conversion ensures deterministic token recognition; subset construction is the standard method.
• Lexical errors (e.g., invalid characters) are caught here, while syntax errors are deferred to parsing.
• Tools like Lex/Flex automate scanner generation from regex rules.

---

1. Introduction to Lexical Analysis

Lexical analysis is the first phase of compilation, where the compiler:

• Reads source code (e.g., int x = 5 + y;).
• Groups characters into tokens (lexemes) like int, x, =, 5, +, y, ;.
• Removes whitespace/comments (irrelevant to meaning).
• Outputs a stream of tokens for syntax analysis.

Why is it important? Without lexical analysis, the parser would see raw text (e.g., intx=5+y;) and fail to recognize keywords, identifiers, or operators.

---

2. Tokens and Lexemes

Key Idea:

• A token is like a part-of-speech tag (e.g., noun, verb), while a lexeme is the word itself (e.g., "run").
• Example: The lexeme while belongs to the token WHILE.

---

3. Regular Expressions for Token Patterns

Regular expressions (regex) define how lexemes are matched. Common patterns:

• Identifiers: [a-zA-Z_][a-zA-Z0-9_]* (e.g., x, total_count).
• Integers: [0-9]+ (e.g., 42, 1000).
• Operators: [+\-*\/] (e.g., +, -).
• Whitespace: [ \t\n] (skipped by the scanner).

Example Regex for a Simple Language:

IDENTIFIER   = [a-zA-Z_][a-zA-Z0-9_]*   // e.g., x, var1
INTEGER      = [0-9]+                   // e.g., 42
PLUS         = \+                      // e.g., +
LPAREN       = \(                      // e.g., (
RPAREN       = \)                      // e.g., )

Note: Regex must be ambiguous-free (no overlap between tokens). For example, if should not match iff.

---

4. Finite Automata: NFA and DFA

Lexical analyzers use finite automata to recognize tokens.

4.1 Non-Deterministic Finite Automata (NFA)

• States: Represent progress in matching a lexeme.
• Transitions: Can be non-deterministic (multiple transitions on the same input).
• Epsilon (ε) transitions: Allow "guessing" paths (e.g., in a|b, the NFA may try both a and b).
• Accepting state: Marks successful matches.

Example: NFA for a*b* (even number of as followed by any bs)

4.2 Deterministic Finite Automata (DFA)

• No ε-transitions or ambiguity: Each state/input has exactly one transition.
• Efficient for scanners: DFAs are easier to implement in hardware/software.
• Constructed from NFA via subset construction (see Section 5).

Example: DFA for 01* (binary strings starting with 0)

---

5. NFA to DFA Conversion (Subset Construction)

Problem: NFAs are hard to implement directly. We convert them to DFAs.

Steps:

1. Start with the NFA’s initial state (including ε-closures).
2. For each input symbol, compute the next set of states reachable via ε-transitions.
3. Repeat until all states are processed.

Example: Convert NFA for a|b to DFA NFA:

DFA Construction:

Final DFA:

---

6. Lexical Analyzer (Scanner) Design

A scanner:

1. Reads input characters one by one.
2. Uses a DFA to classify tokens.
3. Skips whitespace/comments (e.g., //, /* */).
4. Reports errors (e.g., invalid characters like @).

Example: Scanner for int x = 5;

---

7. Handling Ambiguity and Precedence

Problem: Overlapping regex (e.g., 01 could be 0 followed by 1 or the number 1). Solutions:

1. Longest-match rule: Prefer longer tokens (e.g., 01 → INTEGER over 0 + 1).
2. Reserved words first: Check if before IDENTIFIER.
3. Lexical precedence: Define an order (e.g., == before =).

Example: Ambiguity in 01

---

8. Lexical Errors

Common errors caught by the scanner:

• Invalid characters: @, # (not in the language).
• Unterminated strings/comments: /* without */.
• Trigraphs: ??= (non-standard sequences).

Example Error Handling:

Input: `int x @ 5;`
Scanner output:
  - `int` → `INT`
  - `x` → `IDENTIFIER`
  - `@` → **Lexical Error: Invalid character**
  - `5` → `INTEGER`
  - `;` → `SEMICOLON`

---

In the Real World

Lexical analysis is everywhere in software and systems:

1. eSewa (Nepal’s Digital Payment System)

   • Regex Use: Validates transaction IDs (e.g., TXN12345) using \d{3}[A-Z]{2}\d{5}.
   • Scanner Role: Ensures only alphanumeric IDs are processed, rejecting malformed inputs like TXN@123.

2. Khalti (Mobile Payment App)

   • Token Classification: Separates amounts (\d+\.\d{2}), phone numbers (\d{10}), and commands (pay, transfer).
   • Error Handling: Flags invalid inputs like pay 100@ (rejects @ symbol).

3. Daraz (E-Commerce Platform)

   • Order Processing: Uses regex to parse product codes (e.g., DZ-PHONE-001) and quantities (\d+).
   • Queue Management: Lexical analysis ensures order IDs (e.g., ORD-2024-001) are correctly tokenized before routing to the order fulfillment DFA.

4. Ncell (Telecom Billing)

   • SMS Parsing: Extracts keywords (balance, recharge) and numbers (\d{10}) from user messages.
   • Example: Input balance 9812345678 → Tokens: BALANCE, PHONE_NUMBER.

5. Google’s Go Language Compiler

   • Lexical Scanner: Uses Lex/Flex to tokenize code like:

     package main
     import "fmt"
     func main() { fmt.Println("Hello") }
     

     → Tokens: PACKAGE, main, IMPORT, "fmt", FUNC, main, (, ), {, Println, "Hello", }.

---

Worked Example: Scanner for a Simple Arithmetic Expression

Input: 3 + 5 * ( 2 - 1 ) Regex Rules:

Scanner Trace:

Input: 3 + 5 * ( 2 - 1 )
Step 1: '3' → INTEGER (3)
Step 2: ' ' → skip
Step 3: '+' → PLUS
Step 4: ' ' → skip
Step 5: '5' → INTEGER (5)
Step 6: ' ' → skip
Step 7: '*' → MULTIPLY
Step 8: ' ' → skip
Step 9: '(' → LPAREN
Step 10: ' ' → skip
Step 11: '2' → INTEGER (2)
Step 12: ' ' → skip
Step 13: '-' → MINUS
Step 14: ' ' → skip
Step 15: '1' → INTEGER (1)
Step 16: ')' → RPAREN

Output Tokens: [INTEGER(3), PLUS, INTEGER(5), MULTIPLY, LPAREN, INTEGER(2), MINUS, INTEGER(1), RPAREN]

---

9. Tools for Lexical Analysis

Example Lex Specification (for INTEGER and PLUS):

%%
[0-9]+       { yylval = atoi(yytext); return INTEGER; }
"+"          { return PLUS; }
[ \t\n]      ;   // Skip whitespace
.            { printf("Lexical error: %s\n", yytext); }
%%

Compilation: lex scanner.l → scanner.c → Compile with gcc scanner.c -lfl -o scanner.

---

Exam Tip

What to Expect in TU/PU Exams:

1. Define and Differentiate:

   • "Explain the difference between a token and a lexeme with examples."
   • "What is the role of a DFA in lexical analysis?"

2. NFA to DFA Conversion:

   • Given an NFA, construct the DFA using subset construction.
   • Common pitfall: Forgetting ε-closures in intermediate steps.

3. Regex and Ambiguity:

   • "Write regex for identifiers and floating-point numbers."
   • "Resolve ambiguity between 01 as INTEGER vs. 0 + 1."

4. Scanner Design:

   • "Design a scanner for a language with keywords if, else, and identifiers starting with a letter."
   • Trace: Show how if(x>0) is tokenized.

5. Error Handling:

   • "How does a scanner detect invalid characters? Give an example."

Marks Distribution:

• Short answers (2-4 marks): Definitions, regex, token examples.
• Long answers (6-8 marks): NFA/DFA conversion, scanner traces.
• Programming (4-6 marks): Lex/Flex code snippets or pseudocode.

Pro Tip:

• Draw DFAs for regex like a*b* or 01*—examiners love visuals!
• Memorize the subset construction steps for NFA to DFA.
• Practice tokenizing real code snippets (e.g., C/Java/Python).