Lexical Analysis: Scanners, Regular Languages, DFAs, NFAs & Tokenization

TAKEAWAYS:

• Lexical analysis scans source code to identify tokens (keywords, identifiers, operators) using regular expressions and finite automata.
• Input buffering (e.g., buffer-pair scheme) improves efficiency by minimizing disk I/O and handling lookahead.
• DFAs and NFAs model lexical patterns: DFAs are deterministic and efficient, while NFAs allow nondeterminism and are easier to construct from regex.
• Token recognition involves matching input streams to predefined patterns (e.g., if, while, +) and rejecting invalid sequences.
• Real-world compilers (e.g., GCC, javac) use lexical analyzers to preprocess source code before parsing.
• Lexical errors (e.g., misspelled keywords, invalid characters) are caught early to improve debugging.

1. Role of the Lexical Analyzer in Compiler Design

The lexical analyzer (or scanner) is the first phase of a compiler. Its primary tasks are:

• Tokenization: Breaking source code into meaningful units called tokens (e.g., keywords, identifiers, literals, operators).
• Lexical error detection: Identifying invalid characters or sequences (e.g., @ in a variable name).
• Removing whitespace/comments: Ignoring irrelevant characters (spaces, tabs, // comments).
• Efficiency: Minimizing I/O operations by buffering input.

Why is Lexical Analysis Important?

• Preprocessing: Simplifies parsing by converting raw text into structured tokens.
• Error handling: Catches syntax errors early (e.g., x@y is invalid in most languages).
• Optimization: Reduces the workload for later phases (e.g., syntax analysis).

2. Input Buffering: How Lexical Analyzers Read Input Efficiently

Lexical analyzers read source code character by character, but disk I/O is slow. To optimize, they use buffering techniques:

Buffer-Pair Scheme with Sentinels

A common method is the two-buffer scheme:

1. Buffer A holds the current chunk of input (e.g., 100 characters).
2. Buffer B is loaded in advance while Buffer A is being processed.
3. A sentinel (e.g., EOF or a special character) marks the end of valid data.
4. When Buffer A is exhausted, the analyzer swaps buffers and continues.

Why is this efficient?

• Reduces disk reads: Only two buffers are in memory at once.
• Overlapping I/O and processing: While one buffer is being read, the other is being scanned.
• Handles large files: Avoids loading the entire file into memory.

flowchart LR
    A["Source File"] --> B["Buffer A (Current)"]
    A --> C["Buffer B (Next)"]
    B --> D["Scanner Processes Buffer A"]
    C --> E["Loader Fills Buffer B"]
    D --> F["Buffer A Empty?\nIf Yes, Swap A & B"]
    F -->|"No"| D
    F -->|"Yes"| G["Buffer B becomes A,\nNew Buffer B loaded"]
    G --> D

3. Regular Expressions and Finite Automata

Lexical analyzers recognize tokens using regular expressions (regex) and finite automata (DFA/NFA).

Regular Expressions (Regex)

A regex defines a pattern for tokens. Example:

• if → Matches the keyword if.
• [a-zA-Z][a-zA-Z0-9]* → Matches identifiers (e.g., x, totalPrice).
• [0-9]+ → Matches integers (e.g., 123).

Finite Automata

• DFA (Deterministic Finite Automaton): Each input symbol leads to one next state. Efficient but harder to construct.
• NFA (Nondeterministic Finite Automaton): Each input symbol can lead to multiple next states. Easier to build from regex but requires conversion to DFA for execution.

Example: Regex to DFA Conversion Convert the regex a(a+b)(b+c)*a# to a DFA.

stateDiagram-v2
    [*] --> q0
    q0 --> q1 : a
    q1 --> q2 : a
    q1 --> q3 : b
    q2 --> q4 : b
    q2 --> q5 : c
    q3 --> q4 : b
    q3 --> q5 : c
    q4 --> q4 : b
    q4 --> q5 : c
    q5 --> q5 : b
    q5 --> q5 : c
    q5 --> q6 : a
    q6 --> [*] : #

Steps to Build the DFA:

1. Construct NFA from the regex using Thompson’s construction.
2. Convert NFA to DFA using the subset construction method.
3. Minimize the DFA (optional but improves efficiency).

4. How Lexical Analyzers Recognize Tokens

Lexical analyzers use finite automata to match input against token patterns. Here’s how it works:

Example: Token Recognition for if and while

Suppose the input is:

if (x > 5) while (y < 10)

The lexical analyzer processes it as:

1. if → Matches the keyword if (token: IF).
2. ( → Matches the operator ( (token: LPAREN).
3. x → Matches the identifier x (token: ID(x)).
4. > → Matches the operator > (token: GT).
5. 5 → Matches the integer 5 (token: INT(5)).
6. ) → Matches the operator ) (token: RPAREN).
7. while → Matches the keyword while (token: WHILE).
8. And so on...

flowchart LR
    A["Source Code:\nif (x > 5)"] --> B["Lexical Analyzer"]
    B --> C["Token 1: IF"]
    B --> D["Token 2: LPAREN"]
    B --> E["Token 3: ID(x)"]
    B --> F["Token 4: GT"]
    B --> G["Token 5: INT(5)"]
    B --> H["Token 6: RPAREN"]

5. NFA vs. DFA: A Comparison

6. Worked Example: Converting NFA to DFA

Given NFA:

stateDiagram-v2
    [*] --> q0
    q0 --> q1 : a
    q1 --> q2 : b
    q1 --> q3 : b
    q2 --> q4 : a
    q3 --> q4 : a
    q4 --> [*] : #

Steps to Convert to DFA:

1. Initial State: {q0} (start with the NFA’s initial state).
2. Process Input a:
   • From q0, a leads to q1 → New DFA state: {q1}.
3. Process Input b:
   • From q1, b leads to {q2, q3} → New DFA state: {q2, q3}.
4. Process Input a:
   • From q2, a leads to q4.
   • From q3, a leads to q4.
   • New DFA state: {q4}.
5. Accepting State: {q4} (since q4 has a transition to EOF).

Final DFA:

stateDiagram-v2
    [*] --> S0
    S0 --> S1 : a
    S1 --> S2 : b
    S2 --> S3 : a
    S3 --> [*] : #

7. Real-World Applications of Lexical Analysis

Lexical analyzers are used in every compiler and interpreter, including:

1. eSewa (Nepal) – Token Validation in API Requests

• How it uses lexical analysis:
  • When you submit a payment request, eSewa’s backend validates the input token-by-token.
  • Example: The request pay?amount=1000&user=abc123 is split into tokens:
    • pay (keyword),
    • amount=1000 (identifier + integer),
    • user=abc123 (identifier + string).
  • The lexical analyzer checks for invalid characters (e.g., @ in user=abc@123) before processing.

2. GCC (GNU Compiler Collection) – C/C++ Lexical Scanning

• How it uses lexical analysis:
  • GCC’s cpp (C preprocessor) and gcc front-end use a lexical analyzer to:
    • Identify #include, ifdef, return, etc.
    • Remove comments (//, /* */).
    • Convert main() into tokens for parsing.
  • Example: The line int x = 5 + y; is tokenized as:
    • int, ID(x), =, INT(5), +, ID(y), ;.

3. WhatsApp (Global) – Message Tokenization for Spam Detection

• How it uses lexical analysis:
  • WhatsApp’s spam filter uses regex-based lexical analysis to:
    • Detect phishing keywords (e.g., click here, urgent).
    • Flag invalid phone numbers (e.g., +977-123@456).
  • Example: The message "Your account is locked! Click here to verify: http://fake.com" is scanned for:
    • account, locked, click, verify, http:// (tokens marked as suspicious).

8. Worked Example: Lexical Analysis in a Bank Loan Calculator

Scenario: A bank’s loan processing system reads input like:

loan_amount = 500000
interest_rate = 8.5%
term_years = 5

Lexical Analysis Steps:

1. Tokenize the input:
   • loan_amount, =, 500000, ;
   • interest_rate, =, 8.5%, ;
   • term_years, =, 5, ;
2. Validate tokens:
   • Check if loan_amount is a valid identifier.
   • Ensure 500000 is a valid integer.
   • Reject 8.5% if the system expects only numbers (unless % is allowed).
3. Pass tokens to the parser:
   • The parser then computes EMI using the formula: $$EMI=\frac{P\times r\times (1+r{)}^n}{(1+r{)}^n-1}$$ where $P=500000$, $r=\frac{8.5}{100}/12$, $n=5\times 12$.

Output:

Processing loan request...
Valid tokens detected.
Calculating EMI...
Monthly EMI: Rs. 9,980.55

9. Common Lexical Errors and How to Detect Them

10. Exam Tip: How to Score Full Marks

1. For DFA/NFA questions:

   • Always show all states and transitions.
   • Label start and accept states clearly.
   • If converting regex to DFA, explain each step (e.g., "From state X, input Y leads to state Z").

2. For buffer-pair scheme:

   • Draw a diagram showing two buffers swapping.
   • Mention sentinels and why they are used.

3. For token recognition:

   • Give a real code example (e.g., int x = 5; → tokens).
   • Explain how keywords vs. identifiers are distinguished.

4. For regex to automata:

   • If asked to convert (a+b)*a, first draw the NFA, then convert to DFA.
   • Minimize the DFA if possible (show steps).

5. Real-world applications:

   • Link to eSewa, GCC, or WhatsApp in your answer.
   • Example: "Like eSewa validates API tokens, a lexical analyzer checks for invalid characters in user input."

11. Summary Table: Key Concepts

12. Practice Questions (Exam-Style)

1. Design a DFA for the regex a*b*.
2. Explain how WhatsApp uses lexical analysis to detect spam messages.
3. Convert the following NFA to DFA:

   stateDiagram-v2
       [*] --> q0
       q0 --> q1 : a
       q1 --> q2 : b
       q1 --> q3 : b
       q2 --> q4 : a
       q3 --> q4 : a
       q4 --> [*] : #

4. What is the role of sentinels in the buffer-pair scheme? Give an example.
5. Tokenize the following C code:

   for (int i = 0; i < 10; i++) printf("Hello");