Lexical Analysis Notes & Formulas

1. Role of Lexical Analyzer

• First phase of compilation. Reads characters and groups them into meaningful sequences called Lexemes.
• Outputs Tokens: <token_name, attribute_value>.
• Strips out comments and whitespace.

2. Terminology

• Token: Abstract category (e.g., ID, KEYWORD, NUM).
• Lexeme: Actual text sequence (e.g., "x", "int", "3.14").
• Pattern: Rules (Regular Expressions) describing a token.

3. Implementation (DFA)

Lexical analyzers are implemented using Finite Automata (DFA).

• If multiple patterns match, use:
  1. Longest Match Rule: Pick the longest lexeme (e.g., "intptr" is one ID, not "int" + "ptr").
  2. Rule Priority: Keywords have priority over identifiers (e.g., "if" is a keyword).

4. Input Buffering

• Two-Buffer Scheme: Using two pointers (lexemeBegin and forward).
• Sentinels: Special characters (EOF) to avoid checking buffer boundaries in every step.

5. GATE Formulas & Tricks

• Total Identifiers: Number of unique words that match the identifier RE.
• Symbol Table: Initialized with keywords. LA enters new identifiers into it.
• Lexical Errors: Caught when no pattern matches (e.g., illegal characters like @ in some languages).