Lexical Analysis Interview Questions

Fundamental Concepts

Q1: What is lexical analysis and why is it the first phase of compilation?

Lexical analysis (scanning) is the phase that reads raw source code characters and groups them into meaningful units called tokens. It is the first phase because it simplifies everything that follows. The parser does not need to worry about whitespace, comments, or whether <= is one symbol or two — the lexer handles all of this, presenting clean tokens to the parser. Additionally, lexical analysis removes comments and whitespace, reducing the volume of data subsequent phases must process. This separation of concerns makes both the lexer and parser simpler and more maintainable.

Q2: Explain the difference between a token, a lexeme, and a pattern.

A token is a category of lexical unit — like IDENTIFIER, INTEGER, KEYWORD, or OPERATOR. A lexeme is the actual character sequence in the source code that matches a token pattern — for example, "count", "42", or "while". A pattern is the rule describing which lexemes belong to a token category — typically specified as a regular expression like [a-zA-Z_][a-zA-Z0-9_]* for identifiers. Think of it this way: the token is the label on a filing cabinet drawer, the pattern is the rule for what goes in that drawer, and the lexeme is an actual document in the drawer.

Q3: What are token attributes and why are they important?

Token attributes carry additional information beyond the token type. For an INTEGER token, the attribute might be its numeric value (42). For an IDENTIFIER token, the attribute is a pointer to its symbol table entry. For a STRING token, the attribute is the string value with escape sequences processed. Without attributes, the parser would know that something is a number but not which number — attributes preserve the semantic content that later phases need.

Q4: How does the lexer handle keywords versus identifiers?

Keywords like if, while, and return look syntactically identical to identifiers — they match the same [a-zA-Z]+ pattern. There are two approaches. The reserved word table approach: the lexer first matches any alphabetic sequence as an identifier, then checks a hash table of reserved words. If found, it returns the keyword token; otherwise, it returns IDENTIFIER. The explicit pattern approach (used in Flex): list keyword patterns before the general identifier pattern, relying on rule priority to match keywords first. Both approaches are correct; the table approach is more maintainable when the keyword list is large.

Regular Expressions and Pattern Matching

Q5: How do regular expressions drive lexical analysis?

Each token type is defined by a regular expression. The lexer constructs a combined DFA that simultaneously recognizes all patterns. As input characters are read, the DFA transitions between states. When it reaches an accepting state (corresponding to a complete token), it reports the match. If multiple patterns could match, the lexer uses two disambiguation rules: longest match (prefer longer lexemes) and rule priority (among equal-length matches, prefer the earlier rule).

Q6: Explain the NFA-to-DFA conversion in the context of lexers.

The lexer generator (like Flex) first converts each regular expression pattern into an NFA (using Thompson's construction). It then combines all NFAs into one large NFA with epsilon transitions from a new start state. Finally, it applies the subset construction algorithm to convert this NFA into a DFA where each state is a set of NFA states. The DFA guarantees O(1) time per input character since there is exactly one transition for each (state, character) pair.

Q7: What is the longest match principle and why does it matter?

The longest match principle says: when multiple patterns could match starting at the current position, choose the one that consumes the most input characters. For example, given input "integer" and patterns for keyword "int" and identifier [a-z]+, the identifier pattern wins because it matches all 7 characters while "int" only matches 3. Without this rule, the lexer might incorrectly split "integer" into keyword int plus identifier eger.

Q8: What happens when no pattern matches the current input?

This is a lexical error. The lexer should report the error with the source location (line and column number), then employ an error recovery strategy to continue scanning. Common strategies include: skip the offending character and try again (panic mode), or skip characters until a known token delimiter (like whitespace or semicolon) is found. Good lexers report errors without stopping, allowing all lexical errors in a file to be found in a single pass.

Implementation Details

Q9: What is input buffering and why is it needed?

Reading one character at a time from disk is extremely slow due to system call overhead. Input buffering reads large chunks (typically 4096 bytes) into memory at once. The lexer then scans through the buffer, only refilling when it reaches the end. A double-buffer scheme uses two buffers: while the lexer scans one, the OS can asynchronously fill the other, ensuring the lexer never waits for I/O.

Q10: How does lookahead work in lexical analysis?

Lookahead allows the lexer to examine characters beyond the current position without consuming them. This is essential for distinguishing tokens that share a prefix: < vs <=, + vs ++, = vs ==. When the lexer sees <, it peeks at the next character. If it is =, it consumes both and returns <=. If not, it returns < without consuming the peeked character. In Flex, the trailing context operator / provides lookahead: abc/def matches "abc" only if followed by "def", but "def" is not consumed.

Q11: How would you implement string literals with escape sequences?

The pattern must handle both regular characters and escaped characters within quotes: \"([^"\\]|\\.)*\". This reads as: a quote, followed by zero or more characters that are either (not a quote or backslash) OR (a backslash followed by any character), followed by a closing quote. In the action code, you process escapes: \\n becomes a newline byte, \\t becomes tab, \\\\ becomes a literal backslash.

Q12: How do you handle multi-line comments without consuming excessive memory?

For /* ... */ comments that may span hundreds of lines, avoid storing the entire comment content. Use Flex start conditions: when /* is encountered, switch to a COMMENT state. In that state, match and discard all characters until */ is found, then switch back to the INITIAL state. Track line numbers within the comment for accurate error reporting:

Advanced Topics

Q13: What is the role of the lexer in tracking source locations?

The lexer is the only phase that sees raw characters, so it is responsible for tracking line numbers and column positions. Every token emitted includes its source location. This information propagates through all subsequent phases so that error messages (from the parser, type checker, or code generator) can point back to the exact source location. Without lexer-maintained positions, error messages would be useless.

Q14: Can lexical analysis be context-sensitive? Give an example.

Yes, some tokens depend on context. In C, (x) might be a cast expression or a parenthesized expression — the lexer cannot tell, so it leaves this to the parser. However, in Fortran, DO 10 I = 1, 100 vs DO 10 I = 1.100 (the first is a DO loop, the second is assignment to variable DO10I because Fortran ignores spaces) requires context-sensitive lexing. Modern solutions use scanner states or feedback from the parser to resolve such ambiguities.

Q15: How can a lexer be optimized for performance?

Key optimizations include: (1) minimize DFA states through state minimization algorithms, reducing table size and improving cache behavior; (2) use table compression (row displacement or bitmap) to shrink the transition table; (3) avoid backtracking by constructing the DFA carefully; (4) use efficient I/O buffering with OS-aligned reads; (5) avoid unnecessary string copies — point into the input buffer rather than copying lexemes.

Practical Scenarios

Q16: You encounter a token that looks like it could be two different things. How do you resolve it?

Apply longest match first. If both patterns match the same length, rule priority decides (the earlier rule wins). If the ambiguity truly cannot be resolved lexically, pass a generic token to the parser and let syntactic context disambiguate. For example, - might be unary minus or binary minus — the lexer returns MINUS in both cases and lets the parser determine the meaning from context.

Q17: How would you add support for nested comments?

Standard regex cannot count nesting depth, so this requires a counter variable combined with start conditions. On seeing /*, increment depth and enter COMMENT state. On seeing another /* within COMMENT state, increment depth. On seeing */, decrement depth; if depth reaches zero, return to INITIAL state. This exceeds regular language power but is easily implemented with Flex's action code.

Q18: Why is lexical analysis separated from parsing instead of combining them?

Separation provides three benefits. First, simplicity: regular expressions handle the character-level details, keeping the grammar cleaner. Second, efficiency: the DFA-based lexer is faster than embedding character matching in the parser. Third, portability: the same parser can work with different lexers (for different character encodings or input sources). The only cost is the interface between them, which is trivial — a single getNextToken() call.