Lexical errors and recovery; how a lexer generator (Lex/Flex) is structured

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• State the two rules a lexer uses to choose among overlapping patterns. from Lesson 1.2.2
• How many tokens are in printf("%d", x);? from Lesson 1.1.2
• In the regular expression a | bc*, which operator binds tightest? from Lesson 0.2.2

1 · The Story

📖

When no card fits

One speech arrives with smudged text: “Aaje dud#h no bhaav”. Mira reaches “#” and no card fits anything starting with “#”. She has two choices.

Skip ahead: throw away characters until she reaches something that some card fits, report one complaint to the Complaints Desk, and carry on. Quick and safe, but a little text is lost.

Repair: try one small fix (delete the “#”, or swap two letters, or insert one) and see whether the word then fits a card. Careful, but it can guess wrong.

Meanwhile Mrs. Desai buys a Word Desk Builder: you feed it Mira’s cards, each with an instruction (“stamp NAME”, “skip”), and it builds the complete flowchart and a working desk clerk automatically, using the same two house rules.

2 · Predict First

🤔

A lexer meets @ in the middle of C code. Should the whole compilation stop at once? Write your guess down. The answer is in the vault.

3 · Core Concept

Lexical errors

A lexical error occurs when no pattern matches any prefix of the remaining input. Typical cases:

• an illegal character (@, a stray backtick);
• an unterminated string literal or comment;
• an identifier or number that exceeds a length limit;
• in some definitions, a malformed constant.

Many “errors” are not lexical: a misspelled keyword is a valid id; 12.34.5 splits by longest match into 12.34 and .5 or similar, and the trouble is reported by the parser.

Error recovery

• Panic mode: delete characters from the input until a well-formed token can begin. Simple and the most common.
• Local repairs: delete one character, insert one, replace one, or transpose two adjacent characters, then try again.
• Minimum-distance correction: find the fewest such edits that make the input valid. Rarely used: expensive, and the closest valid text is not always what the programmer meant.

Lex and Flex

Lex (and its modern version Flex) is a lexer generator: you describe tokens, it writes the lexer.

%{  C declarations, e.g. #include "tokens.h"  %}
digit   [0-9]
id      [a-z][a-z0-9]*
%%
if              { return IF; }
{id}            { yylval = install_id(); return ID; }
{digit}+        { yylval = atoi(yytext); return NUM; }
[ \t\n]+        { /* skip whitespace */ }
.               { error("illegal character"); }
%%
int install_id() { … }   /* auxiliary functions */

• Three sections separated by %%: declarations, translation rules (pattern + action), auxiliary functions.
• Lex turns all patterns into one NFA, then a DFA, then a C file lex.yy.c containing yylex().
• yytext is the matched lexeme, yyleng its length, yylval the attribute passed to the parser.
• Conflicts: longest match first, then the earliest rule. That is why if is listed before {id}, and why the catch-all . rule comes last.

The pipeline

From a specification to a working lexer.

Story → compiler term

4 · Visual

5 · Worked Examples

Example 1 Easy

Classify: (a) x = 5 $ 3; (b) s = "abc; (c) retrun 0;

Solution

(a) Lexical error at $ (in standard C; some compilers allow $ in names). (b) Lexical error: the string literal never closes. (c) Not lexical: retrun is an id; the parser reports it. Mira complains only when no card fits.

Example 2 Medium

A Lex specification has the rules, in order: if → print IF; [a-z]+ → print ID; [0-9]+ → print NUM; [ \t\n]+ → nothing; . → print ?. What is printed for if ifx 42 x9?

Solution

if: IF (ties with [a-z]+ at length 2; the earlier rule wins). ifx: ID (longest match). 42: NUM. x9: [a-z]+ takes only x → ID, then 9 → NUM. Output: IF ID NUM ID NUM, verified by simulating the rules.

Example 3 GATE

With the same specification, what is printed for x@1 if, and which rule recovers from the error?

Solution

x → ID; @ matches only the catch-all . → ?; 1 → NUM; if → IF. Output: ID ? NUM IF. The . rule is a built-in panic mode of length 1: it consumes the bad character and lets the lexer continue, like Mira skipping one smudge.

6 · Shortcuts

⚡

Lex conflict rules = lexer rules: longest match, then earliest rule. Simulate position by position. Valid when: any “what does this Lex program print” question.

⚡

Lexical error only if no pattern matches. If some pattern matches a prefix (even a strange one), the error, if any, belongs to a later phase. Valid when: error-classification questions.

7 · GATE Traps

⚠️

• A misspelled keyword is never a lexical error.
• Lex picks the longest match even if an earlier rule matches a shorter prefix.
• Put the catch-all . rule last, or it would beat specific single-character rules by priority.
• yytext is the lexeme; yylval is the attribute passed to the parser.
• Panic mode loses input; it trades precision for simplicity.

8 · Memory Hook

🧠

Lex = “Longest, Earliest, eXecute”: longest match, earliest rule, run its action.

9 · Connect the Dots

Phase 1 is complete: the lexer turns characters into tokens. Phase 2 opens the Sentence Desk: how to describe which token sequences form valid programs, using a tool more powerful than regular expressions.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markLexical error

Which is a lexical error in C?

• (A) a missing semicolon
• (B) an unterminated string literal
• (C) an undeclared variable
• (D) calling a function with too many arguments

Q2MCQ1 markRecovery

Panic-mode recovery in a lexer:

• (A) stops compilation
• (B) deletes input characters until a valid token can start
• (C) rewrites the whole program
• (D) asks the user

Q3MCQ2 marksLex simulation

Rules in order: if → IF; [a-z]+ → ID; [0-9]+ → NUM; blanks skipped; . → ?. Output for iff if9 7a?

• (A) ID IF NUM NUM ID
• (B) IF ID IF NUM NUM ID
• (C) ID ID NUM ID
• (D) IF ID IF NUM ID

Q4MSQ1 markLex

Which are true about Lex?

• (A) It generates C code for a lexical analyzer.
• (B) It resolves conflicts by longest match, then the earliest rule.
• (C) yytext holds the current lexeme.
• (D) It builds a parser for the whole language.

Q5MCQ1 markRepairs

Which is not one of the single-character local repairs?

• (A) delete one character
• (B) insert one character
• (C) transpose two adjacent characters
• (D) reverse the whole line

11 · Rule Card

• Lexical error: no pattern matches a prefix of the remaining input (illegal char, unterminated string/comment, over-long name).
• Recovery: panic mode (delete until a token can start); local repairs (delete, insert, replace, transpose); minimum-distance (rare).
• Lex file: declarations %% rules (pattern {action}) %% functions.
• lex.l → Lex → lex.yy.c → C compiler → lexer; yylex(), yytext, yyleng, yylval.
• Conflicts: longest match, then earliest rule; catch-all . last.

12 · Concept Ledger

lexical errorpanic-mode recoverylocal repairminimum-distance correctionLex / Flexlexer generatortranslation rule (pattern { action })lex.yy.cyylex()yytext / yyleng / yylval

13 · Answer Vault