llguidance HATES This One Weird Grammar (Maximal munch)

Here is a grammar that llguidance does not like:

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

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

The language contains both listed and listened:

list   | ed
listen | ed

Lark parses both. llguidance accepts listened. But the single model token listed is rejected:

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

To see why, walk the token byte by byte.

At list, the lexer is in an accepting state. list is a complete STEM.

But it is not forced to stop there. The same terminal also contains listen, so e keeps the current lexeme alive:

list      accepting
liste     live, not accepting
listen    accepting

For listened, that greediness is correct. For listed, the next d kills the longer attempt. Only then does it become clear that the correct boundary was the earlier one:

list | ed

The useful comparison is with an ordinary maximal-munch lexer.

Two very similar policies

A conventional lexer keeps scanning while a token can continue, but it also remembers the most recent accepting position:

candidate = None

for prefix in prefixes:
    if prefix.is_accepting():
        candidate = prefix

return candidate

The scan can wander beyond the eventual token boundary. That is fine. If the longer attempt dies, candidate still points at the last place the lexer could legally have stopped.

The relevant llguidance behaviour is closer to:

candidate = None

for prefix in prefixes:
    candidate = prefix

return candidate if candidate.is_accepting() else None

That is conceptual pseudocode, not the literal implementation. The real recognizer is incremental, parser-aware, handles multiple active terminals, and is driven by a walk over the model vocabulary trie. But this tiny distinction captures the failure.

The trie part matters because llguidance cannot just run a conventional lexer independently on every vocabulary token. That would throw away most of the sharing that makes mask generation fast. If 10,000 tokens begin with the same bytes, the recognizer should process that prefix once, then branch only where the vocabulary does.

So its natural interface is closer to advance(byte) than lex(remaining_string). While a byte can continue the current lexer state, the recognizer advances. When a byte finally cannot continue it, llguidance can emit the current lexeme if that current state is accepting, advance the parser, and try the same byte again as the beginning of the next lexeme.

That scheme works beautifully when the killing byte arrives immediately after the real boundary. For an identifier followed by (, for example, ( cannot continue the identifier. The recognizer discovers the boundary exactly when it needs to hand the byte to the next parser state.

listed breaks the assumption. The first byte after the real boundary, e, does not kill STEM. It takes the recognizer away from the accepting state and into a live non-match. The actual killing byte is the later d.

After reading the bytes before the killing d:

ordinary lexer:  current = liste   candidate = list
llguidance:       current = liste

Then d arrives. liste cannot continue and is not accepting. The ordinary lexer still has list. llguidance has nothing to emit.

You can phrase the difference another way:

ordinary maximal munch:
    last(accepting prefixes)

the failing policy:
    accept(last live prefix) if it happens to be accepting

Those expressions are almost identical on ordinary lexer paths. They diverge precisely when an accepting prefix is followed by a longer live, non-accepting prefix. list -> liste is the smallest useful example I have found.

That also explains why this does not amount to “llguidance cannot handle a token containing two lexemes.” It can. The problem is that the first lexeme had an unresolved greedy alternative, and the evidence that alternative was wrong arrived after the true boundary.

Fix the grammar

One repair is trivial:

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

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

Now stem is a parser rule. The lexer no longer has to hide the list versus listen decision inside one greedy terminal.

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

For an affected custom grammar, this is often all you need.

Why JSON mostly gets away with it

JSON rarely presents this exact boundary.

A string ends at a quote. Structural punctuation cannot continue the string. true, false, and null are similarly followed by bytes that kill those lexemes immediately. Numbers do have accepting prefixes followed by live non-accepting prefixes—1 versus 1e is the obvious example—but the next legal JSON lexeme does not normally begin with the same byte that continues the number.

So the problematic condition is narrower than “a terminal has prefixes that are also matches.” Plenty do. What matters is whether the lexer can move past a valid boundary without immediately learning that it crossed one.

That is also why changing the grammar works. Parser rules let llguidance represent the two alternatives as parser structure rather than asking one terminal to carry the unresolved greedy choice internally. We are not making the accepted language simpler; we are moving where the ambiguity lives.

Remembering the boundary

There is also an implementation-side repair. Keep the greedy path exactly as it is, but remember the latest accepting lexer position. If the attempted longer lexeme dies before reaching another accepting position, restore that boundary and replay the intervening bytes in the parser state after the saved lexeme.

I implemented that as an opt-in llguidance branch: redesign/greedy-lexeme-fallback-integrated-v3.

That implementation needs more machinery than the sentence above suggests because llguidance is speculatively walking a vocabulary trie, not scanning one finished input string. But the semantic difference remains tiny:

ordinary maximal munch:
    remember where you could have stopped

current llguidance behaviour:
    discover later that you should have stopped there

For listed, one remembered position is the difference between False and True.