llguidance HATES This One Weird Grammar (Fallback repair)

I found a grammar that makes llguidance reject the English word listed:

%llguidance {"no_forcing": true}
start: STEM SUFFIX

STEM: "list" | "listen"
SUFFIX: "ed"

The intended parses are not subtle:

listed     = list   | ed
listened   = listen | ed

Lark accepts both. llguidance accepts listened. The model token listed is missing from the mask:

>>> b"listed" in next_token_mask
False
>>> validate_tokens([b"listed"])
0

I initially expected this to be another model-token-boundary problem. It is not. The interesting part is inside the lexer.

After reading list, the current terminal is accepting. But greediness says not to emit it yet, because listen would be a longer STEM if the next bytes were en.

So the recognizer keeps going:

list      accepting; could stop here
liste     live, non-accepting
listed    dead

The final d proves that trying to extend STEM was wrong. The correct split was list | ed. But by the time llguidance learns that, the earlier accepting position is no longer available as the lexeme boundary.

An ordinary lexer usually solves this by remembering the last accepting position while it pursues a longer match. That suggested a fairly direct repair: let llguidance stay greedy, but give it a memory.

Remember the place you could have stopped

Conceptually, the state you need is tiny:

class GreedyFallback:
    accepting_position = None

As bytes extend the current lexeme, record the newest point at which it was accepting. Do not fork the parser and do not immediately take the shorter match. Keep pursuing the primary greedy interpretation exactly as before.

For listed:

list      accepting -> remember boundary
liste     live       -> keep going
listed    dead       -> recover boundary

Recovery then means: return to the state after list, emit that STEM, and replay the bytes that came after the checkpoint. In the parser context following STEM, those bytes are ed, so they become SUFFIX.

In simplified form:

def recover():
    restore(latest_accepting_position)
    emit_saved_lexeme()
    replay(bytes_after_saved_position)

That is the central idea behind my opt-in branch, redesign/greedy-lexeme-fallback-integrated-v3.

There is an important semantic constraint: an earlier checkpoint must not compete forever with a later successful greedy match. If the lexer goes from list to listen, then listen becomes the new greedy result. The saved list interpretation should not remain as an alternative merely because it once matched. The fallback is for a longer attempt that fails, not a general mechanism for preserving every lexical segmentation.

For example, if a grammar can match either A = "a" or AB = "ab", reaching the complete ab match should still discard the earlier a boundary for maximal-munch purposes. The repair changes what happens when the longer path dies in a non-accepting state. It does not change which successful match wins.

Why the real implementation is less tiny

llguidance is not scanning one complete input string from left to right. During mask generation it walks a trie containing model vocabulary tokens and speculatively pushes and pops bytes as branches diverge.

That means a fallback cannot simply mutate the recognizer and forget what happened. If recovery occurs while exploring one vocabulary branch, backing out of that branch must restore the exact primary state so another token can still take the longer greedy interpretation.

In practice this means speculative recovery needs undo information. A trie branch can temporarily promote the fallback, replay some bytes, discover that this particular model token works, and then be popped while the traversal explores a sibling. The sibling must start from the same state it would have seen if recovery had never happened on the first branch.

There is another problem: the distance from an accepting boundary to the eventual failure can be arbitrarily long. Replaying a handful of bytes is cheap. Replaying ten thousand bytes after one unlucky token is not. My implementation therefore uses replay for short unresolved gaps and can materialize a synchronized fallback parser state when the gap becomes long.

Those details matter to the implementation, but not to the semantics. There is still only one preferred interpretation: the longest match. The earlier boundary is insurance. It becomes active only if the attempted longer lexeme dies before reaching a newer greedy match.

A pending checkpoint also makes some optimizations less obviously valid. If two recognizers have the same current lexer DFA state but different remembered accepting boundaries, they are no longer necessarily interchangeable. Cache keys and vocabulary-slice shortcuts that normally depend only on the current state need either more information or a conservative slow path while fallback state is live. My branch takes the conservative route in those cases rather than complicating the ordinary hot path.

You can also just fix the grammar

If you are writing an affected grammar rather than llguidance itself, there is a much easier solution:

%llguidance {"no_forcing": true}
start: stem SUFFIX

stem: "list" | "listen"
SUFFIX: "ed"

Putting the choice in a parser rule makes the boundary visible to the parser, and listed works again:

>>> b"listed" in next_token_mask
True
>>> consume_token(b"listed")
True

Most JSON grammars never need this workaround. Quotes and structural punctuation make their important lexeme boundaries explicit, and the bytes that continue a number or literal generally cannot also begin the next legal lexeme.

The counterexample matters less because listed itself is common than because it isolates the missing state so cleanly. There is one valid boundary, one tempting longer match, and one later byte that proves the lexer should have stopped earlier.

That was useful experimentally. A complicated grammar can make a recognizer bug look like parser ambiguity, terminal priority, tokenizer weirdness, or a model-token split. Here there is nowhere for the cause to hide. The debugger reaches list, walks one byte beyond the correct boundary, and then dies. Once that was visible, the repair was almost forced.

The eventual fix was therefore not a new parser or a different vocabulary traversal. It was simply to let the greedy lexer remember where it had already been right.