A scanner must handle block comments that nest to any depth; what does a pure finite-state pass lack for that job?

seniorshould knowfreq 33%

answer

finitely many states, finite memory
unbounded depth needs counting
a fixed cap is still regular
counter for comments, stack for modes
end of input at depth above zero

basics

~20 s

It lacks a counter. A finite-state pass has a fixed number of states, so it cannot track how many openings are still unclosed when the depth is unbounded. Scanners add a depth counter, and a stack of modes for constructs that nest.

solid answer

~40 s

Finitely many states means finitely much memory. Nesting to an unbounded depth needs to remember a number that has no ceiling, so no finite-state recogniser accepts it - this is the same limitation that keeps a pattern from matching balanced brackets. Note the qualifier: if a language caps nesting at some fixed depth, that is finite-state, one state per level. Real scanners therefore stay finite-state for token shapes and bolt on a small amount of extra state: an integer depth for nested comments, and a stack of modes for a string containing an embedded expression that may itself contain another string. The scanner is then a finite-state machine plus a counter, which is deliberate engineering rather than a violation of the theory.

Finitely many states means finitely much memory. Nesting to an unbounded depth needs to remember a number that has no ceiling, so no finite-state recogniser accepts it - this is the same limitation that keeps a pattern from matching balanced brackets. Note the qualifier: if a language caps nesting at some fixed depth, that *is* finite-state, one state per level. Real scanners therefore stay finite-state for token shapes and bolt on a small amount of extra state: an integer depth for nested comments, and a **stack of modes** for a string containing an embedded expression that may itself contain another string. The scanner is then a finite-state machine plus a counter, which is deliberate engineering rather than a violation of the theory.

code

pseudocode · 19 lines

pseudocode

skip_nested_comment(input, pos):
    depth = 1
    open_at = pos
    pos = pos + 2                       # consume the opening marker

    while depth > 0:
        if pos >= length(input):
            report "unterminated comment" at open_at
            return pos
        if matches(input, pos, "/*"):
            depth = depth + 1
            pos = pos + 2
        else if matches(input, pos, "*/"):
            depth = depth - 1
            pos = pos + 2
        else:
            pos = pos + 1

    return pos

go deeper

for a junior

Remember that a scanner with a fixed set of states cannot count, and that counting is exactly what is needed to know when a nested comment has closed.

for a middle

Explain why unbounded nesting is not regular while a fixed depth cap is, and describe the depth-counter loop including what happens at end of input.

for a senior

Describe the mode stack and why an embedded-expression string needs one rather than a flag, and say where the unterminated-construct diagnostic should point and why.

for a principal

Weigh the syntax choice itself: non-nesting comments and delimiter-fixed strings keep the scanner declarative and its generator simple, at a cost in expressiveness that the language has to justify.

What a finite-state pass can remember

A finite-state recogniser has a fixed set of states and moves between them one character at a time. Its entire memory is which state it is in, so it can remember only a bounded amount. Counting to an arbitrary number is exactly what it cannot do, because each distinct count would need its own state and there is no bound on the count.

Nesting is counting. To know whether a nested block comment has closed, you must know how many openings are still outstanding, and that number is unbounded if the language allows arbitrary depth. So a language of arbitrarily nested comments is not regular, and no scanner built as a pure state machine can recognise it.

The qualifier that matters

It is the unbounded part that bites. If a language caps nesting at, say, three levels, the resulting set of strings is still regular: a machine with three extra states does it. The same goes for a comment syntax that does not nest at all - a non-nesting block comment is trivially finite-state, because the first closing marker always ends it, and that is why so many languages chose that design.

Construct	Extra state needed	Still finite-state?
Non-nesting block comment	none	yes
Nesting capped at a fixed depth	a bounded set of states	yes
Nesting to any depth	an unbounded counter	no
String with embedded expressions containing strings	a stack of modes	no

What scanners actually add

Production scanners do not abandon the state machine; they extend it in two named ways.

A depth counter. On the opening marker, increment; on the closing marker, decrement; the comment ends when the count returns to zero. One integer covers unbounded depth.
A mode stack. A mode is a rule set: which patterns are active right now. Ordinary code is one mode, the inside of a string is another, the inside of an embedded expression is a third. Entering a construct pushes a mode, leaving it pops.

The mode stack is what handles a string with an embedded expression hole. Inside the hole the language is code again - which may contain another string, which may contain another hole. The nesting is unbounded, so a flag is not enough; the scanner must push and pop. A single boolean in a string or not out of a string is the classic bug: the first quote inside the hole closes the outer string and the rest of the file is scanned in the wrong mode.

The error path is part of the design

The counter makes a new failure possible: end of input with the depth still above zero, meaning an unterminated comment. A scanner has to detect that explicitly rather than looping, and the diagnostic should point at the outermost opening marker, because that is the one the author most likely forgot to close. The same holds for the mode stack: a non-empty stack at end of input is an unterminated string or hole, and the stack itself tells you what was open.

What this costs and why it is accepted

The extra state is small and the pass stays linear - one character step plus, at most, one counter update or one stack push. What it does cost is composability: the scanner is no longer a pure pattern set that can be described declaratively, so a generator has to expose mode transitions and counter actions as explicit hooks. Languages that want their scanner to stay purely declarative pay for it in syntax design: non-nesting comments, no embedded expressions in strings, or a string syntax that fixes its own delimiter so it cannot be confused with the inner one.

How to argue it in an interview

The strong answer separates the theory from the practice. The theory: unbounded nesting is not regular, so this is not a limitation of an implementation but of the machine class. The practice: nobody responds by moving comments into the parser; they add a counter and a mode stack and keep the linear pass. Naming the interpolated-string case as the reason a stack is needed rather than just a counter is what distinguishes a candidate who has implemented one from a candidate who has read about one.

## What a finite-state pass can remember A finite-state recogniser has a fixed set of states and moves between them one character at a time. Its entire memory is *which state it is in*, so it can remember only a bounded amount. Counting to an arbitrary number is exactly what it cannot do, because each distinct count would need its own state and there is no bound on the count. Nesting is counting. To know whether a nested block comment has closed, you must know how many openings are still outstanding, and that number is unbounded if the language allows arbitrary depth. So a language of arbitrarily nested comments is **not regular**, and no scanner built as a pure state machine can recognise it. ## The qualifier that matters It is the *unbounded* part that bites. If a language caps nesting at, say, three levels, the resulting set of strings is still regular: a machine with three extra states does it. The same goes for a comment syntax that does not nest at all - a non-nesting block comment is trivially finite-state, because the first closing marker always ends it, and that is why so many languages chose that design. | Construct | Extra state needed | Still finite-state? | |---|---|---| | Non-nesting block comment | none | yes | | Nesting capped at a fixed depth | a bounded set of states | yes | | Nesting to any depth | an unbounded counter | no | | String with embedded expressions containing strings | a stack of modes | no | ## What scanners actually add Production scanners do not abandon the state machine; they extend it in two named ways. 1. **A depth counter.** On the opening marker, increment; on the closing marker, decrement; the comment ends when the count returns to zero. One integer covers unbounded depth. 2. **A mode stack.** A *mode* is a rule set: which patterns are active right now. Ordinary code is one mode, the inside of a string is another, the inside of an embedded expression is a third. Entering a construct pushes a mode, leaving it pops. The mode stack is what handles a string with an embedded expression hole. Inside the hole the language is code again - which may contain another string, which may contain another hole. The nesting is unbounded, so a flag is not enough; the scanner must push and pop. A single boolean in a string or not out of a string is the classic bug: the first quote inside the hole closes the outer string and the rest of the file is scanned in the wrong mode. ## The error path is part of the design The counter makes a new failure possible: end of input with the depth still above zero, meaning an unterminated comment. A scanner has to detect that explicitly rather than looping, and the diagnostic should point at the **outermost** opening marker, because that is the one the author most likely forgot to close. The same holds for the mode stack: a non-empty stack at end of input is an unterminated string or hole, and the stack itself tells you what was open. ## What this costs and why it is accepted The extra state is small and the pass stays linear - one character step plus, at most, one counter update or one stack push. What it does cost is **composability**: the scanner is no longer a pure pattern set that can be described declaratively, so a generator has to expose mode transitions and counter actions as explicit hooks. Languages that want their scanner to stay purely declarative pay for it in syntax design: non-nesting comments, no embedded expressions in strings, or a string syntax that fixes its own delimiter so it cannot be confused with the inner one. ## How to argue it in an interview The strong answer separates the theory from the practice. The theory: unbounded nesting is not regular, so this is not a limitation of an implementation but of the machine class. The practice: nobody responds by moving comments into the parser; they add a counter and a mode stack and keep the linear pass. Naming the interpolated-string case as the reason a *stack* is needed rather than just a counter is what distinguishes a candidate who has implemented one from a candidate who has read about one.

Why is a boolean not enough for a string that can contain an embedded expression?
Because the expression inside the hole may contain another string, which may contain another hole, with no bound on the depth. A boolean records only in a string or not, so the first quote inside the hole is read as closing the outer string and everything after it is scanned in the wrong mode. A stack of modes records what to return to.
Does adding a counter mean the scanner is no longer finite-state in any sense?
The token patterns themselves remain finite-state; the counter is extra state layered on top for one construct. The useful way to say it is that the scanner is a finite-state machine plus a bounded number of counters and a mode stack. That is strictly more powerful than a pure state machine and still runs in one linear pass.
Where should the diagnostic for an unterminated nested comment point?
At the outermost opening marker, which is the one that was never closed and the position the author needs to see. Pointing at end of input tells the reader nothing, and pointing at the innermost opening is usually wrong, since inner markers are typically balanced. The counter loop must therefore record the outer opening position before it starts.

A guard who can only remember inside or outside cannot tell when the last person has left a building that people keep re-entering. A hand tally counter can, and that counter is precisely what a state machine does not have.

saying these in an interview costs you the question

Says no scanner can handle nested comments at all
Claims nesting capped at a fixed depth still needs a counter
Uses one boolean flag for whether the scan is inside a string
Thinks a mode is a token class rather than a rule set
Omits the end-of-input check and lets the depth loop run off the buffer

A scanner must handle block comments that nest to any depth; what does a pure finite-state pass lack for that job?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

What a finite-state pass can remember

The qualifier that matters

What scanners actually add

The error path is part of the design

What this costs and why it is accepted

How to argue it in an interview

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

What a finite-state pass can remember

The qualifier that matters

What scanners actually add

The error path is part of the design

What this costs and why it is accepted

How to argue it in an interview

answer

go deeper