Building a Lexer for Your Next Interview

You're in a whiteboarding interview, heart pounding, and the interviewer just asked you to parse a simple arithmetic expression. Not just evaluate it, mind you, but break it down into its fundamental pieces. This isn't some abstract algorithm; it's a foundational skill, and building a lexer is often the very first step. You don't need a PhD in compilers to nail this; you need to understand the mechanics, the trade-offs, and how to articulate your design choices. This skill comes up in weird places, not just compiler companies: think log parsing, configuration file readers, even advanced search query builders.

Why Even Talk About Lexers?

Look, most of us use off-the-shelf parsers like ANTLR or Bison for real-world projects. I get it. But an interview isn't about rote memorization of library APIs. It's about demonstrating your understanding of core computer science principles. Building a lexer (or tokenizer, they're often used interchangeably in interviews) shows you grasp state machines, string manipulation, error handling, and separation of concerns. It's a fantastic problem to probe your analytical thinking. You'll often see this problem framed as "write a tokenizer for JSON," or "build a simple calculator," where the lexer is the first component. They want to see how you structure code, how you think about edge cases, and whether you can explain why you chose a switch statement over a giant if/else if chain for token identification.

Consider a string like "123 + "hello" * 4.5". Our goal is to turn this into a sequence of meaningful tokens: INT(123), PLUS, STRING("hello"), STAR, FLOAT(4.5). This process needs to be robust. It needs to handle whitespace, differentiate between + and ++, and know when a number ends and an identifier begins.

The Core Components of Your Lexer

At its heart, a lexer is a loop that consumes characters from an input stream and groups them into tokens. You'll need a few things to make this work:

1. Token Definition: Start here. What are the types of tokens your language will have? For an arithmetic expression, you might have NUMBER, PLUS, MINUS, MULTIPLY, DIVIDE, LPAREN, RPAREN, IDENTIFIER, STRING, EOF (End of File/Input). Define these clearly, perhaps as an enum or a set of constants. Each token generally carries a type and a value (lexeme). The value for NUMBER(123) is "123", for PLUS it's "+".

2. Input Stream Management: You need a way to read characters one by one, and sometimes "peek" at the next character without consuming it. A simple char[] or string with an index, or an InputStream reader, works fine. Make sure you handle reaching the end of the input gracefully. Don't forget to track line and column numbers if you want to give useful error messages later.

3. getNextToken() Function: This is the core loop. It will repeatedly:

   • Skip Whitespace: Ignore spaces, tabs, newlines until you hit something meaningful. This is a common early mistake: not explicitly handling ignorable characters.
   • Identify Token Type: This is the tricky part. Is it a number? An identifier? An operator? You'll often use if/else if or a switch statement based on the current character.
   • Consume Lexeme: Once you know the type, read all characters that belong to that token. For a number, read all digits. For an identifier, read letters, numbers, and underscores. For a string, read until the closing quote.
   • Create and Return Token: Package the type and lexeme into a Token object and return it.

Let's quickly sketch out some pseudocode for the getNextToken function. Imagine currentChar holds the character at currentIndex.

function getNextToken():
  skipWhitespace()

  if currentChar == EOF:
    return new Token(EOF_TYPE, "")

  if isDigit(currentChar):
    return readNumber()
  if isLetter(currentChar):
    return readIdentifierOrKeyword()
  if currentChar == '"':
    return readString()
  if currentChar == '+':
    advance()
    return new Token(PLUS_TYPE, "+")
  // ... more operators ...
  else:
    // This is where error handling comes in!
    error("Unexpected character: " + currentChar)

The readNumber(), readIdentifierOrKeyword(), and readString() functions would then handle the specific logic for consuming those particular lexemes until a non-matching character is found. This modularity is key.

Common Pitfalls and How to Avoid Them

You're not just writing code; you're demonstrating thought. Point out these potential issues and your solutions.

• Ambiguity: Is > a GREATER_THAN or the start of >> (right shift)? You need to "peek" at the next character. If currentChar is > and peekChar is also >, then it's >>. Otherwise, it's just >. This lookahead is critical.
• Keywords vs. Identifiers: Is if an IF_KEYWORD or an IDENTIFIER named "if"? When you read an identifier, check if its lexeme matches any predefined keywords. A HashMap or Dictionary mapping string lexemes to TokenType enums is perfect for this.
• Error Handling: What happens if you hit an unrecognized character? Don't just crash. Report an error with line/column information. What if a string literal doesn't close? Report an unclosed string error. Good error reporting is a sign of a mature design.
• Performance: For an interview, don't over-optimize prematurely. A simple character-by-character scan is fine. Mention that for very large files, you might consider buffering input or using regular expressions (though often, regex lexers can be slower or harder to debug for complex grammars).

What About Regular Expressions?

You might be thinking, "Can't I just use regular expressions?" Yes, you can, especially for simpler lexers. Many tools, like Python's re module or JavaScript's RegExp, let you define patterns for tokens.

For example, \d+ for numbers, [a-zA-Z_]\w* for identifiers. You'd typically compile these patterns, then iterate, trying to match the longest possible token at the current position.

However, be prepared to discuss the downsides:

• Order Matters: If you have if (keyword) and identifier ([a-zA-Z_]\w*), and you try to match identifier first, "if" will be tokenized as an IDENTIFIER by mistake. You need to order your regexes carefully, from most specific to most general, or use a "longest match wins" strategy.
• Lookahead/Context: Some tokenizing rules are hard to express with pure regex (e.g., distinguishing > from >> without careful ordering or lookahead assertions).
• Debugging: When a regex doesn't quite work, it can be a nightmare to debug why it's matching too much or too little.
• Performance: Repeatedly applying many complex regexes can be slower than a hand-rolled state machine, especially in languages where regex engines aren't highly optimized for this specific use case.

For an interview, a hand-rolled, character-by-character lexer demonstrates a deeper understanding of state machines and parsing logic. If you do propose regex, be ready to explain the ordering problem and how to solve it.

Your Design Choices and Trade-offs

This is where you shine. The interviewer isn't just looking for a correct solution; they want to see how you think.

• Language Choice: Use a language you're comfortable with. Java, Python, C++, C# – all are fine. The concepts are universal.
• Data Structures: An enum for TokenType is clean. A class Token with type and lexeme fields is standard. A StringBuilder for accumulating lexemes is efficient in Java/C#.
• Error Reporting: Will you throw exceptions? Collect errors in a list and continue? The latter is often better for user experience (show all errors, not just the first one).
• State Machine vs. Recursive Descent: For a lexer, a simple iterative state machine (your getNextToken loop) is usually sufficient and easier to reason about than a recursive solution. Save recursive descent for the parser.

Sometimes, an interviewer will ask about the "lexer generator" tools. ANTLR, Flex, JLex – these tools generate the lexer code from a grammar definition. You can mention them as advanced solutions, but make sure you can still explain the underlying principles they abstract away. This isn't about using the biggest hammer; it's about understanding the mechanics of a small, precise one.

Mastering this problem means you understand fundamental compiler design, string processing, and defensive programming. It shows you can break down a complex problem into manageable pieces. Practice it a few times in your language of choice. You'll be surprised how often this seemingly niche skill becomes a key differentiator in an interview.

Ready to Ace Your Next Interview?

Practice with AI-powered mock interviews tailored to your target role and company. Start Practicing for Free | Explore Interview Prep