llguidance HATES This One Weird Grammar (Well-behaved grammars)

Consider this grammar:

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

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

There are two obvious strings in the language:

list   | ed   = listed
listen | ed   = listened

Lark accepts both. llguidance accepts listened too. But give llguidance listed as one model token and it says no:

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

Which is weird. The split is sitting right there: list | ed.

The trouble starts after list. At that point STEM has matched, but the lexer can also keep going toward the longer listen match. The next byte in listed is e, so the lexer does keep going:

list      accepting
liste     live, non-accepting

Then it gets d, and listed is dead as a STEM. The correct boundary was two bytes ago, after list.

An ordinary longest-match scanner can remember the last accepting position and return to it when the longer attempt fails. llguidance’s incremental recognizer does not retain that boundary in the same way while it walks the model vocabulary trie. Once it has reached liste, the useful accepting state at list has been lost.

Here is the same thing in a little debugger. Step through listed, then compare it with listened.

A rule for well-behaved grammars

There is a simple sufficient condition that rules this problem out:

Once the combined lexer is accepting, every continuation that keeps it alive must leave it accepting.

In DFA terms, every live successor of an accepting state must also be accepting.

Our grammar fails immediately:

list      accepting
liste     live, non-accepting
listen    accepting

That middle state is the dangerous bit. We have crossed a perfectly valid boundary after list, but the lexer is still alive and has stopped being accepting. If the longer attempt later dies, recovering the earlier boundary requires memory.

This rule is stronger than necessary. JSON numbers, for example, can go through 1 (accepting), 1e (live but non-accepting), and 1e2 (accepting) without causing this particular problem in normal JSON parser contexts. So I would not use the rule as a definition of correct lexing.

But as a grammar-author sanity check it is nice. If your combined lexer satisfies it, this whole class of lost-boundary behaviour simply cannot happen. And if it does not, the accepting → live/non-accepting edge tells you exactly where to look.

You can also just fix the grammar

For this example, I would probably do that.

Move the choice out of the greedy terminal and let the parser see it:

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

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

Lowercase stem is a parser rule. Now the lexer no longer has to hide the list versus listen choice inside one terminal, and listed works:

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

I would not respond by splitting every terminal into tiny parser rules. That can make the parser do a lot more work. The useful splits are the awkward boundaries: places where a terminal can already have matched, continue through a non-accepting state, and collide with what the grammar wants to read next.

For a custom grammar, fixing one of those boundaries is often much easier than caring about any of the recognizer machinery below.

Fixing it for good (my PR)

The grammar rewrite is a workaround. llguidance can support the original grammar too if its greedy lexer remembers where it could have stopped.

I implemented that in llguidance PR #373, Add lexer backtracking.

The primary greedy path stays unchanged. When it reaches an accepting position, the recognizer remembers it. It can then continue looking for a longer match. If that attempt later dies before finding a newer accepting position, the recognizer restores the saved boundary and replays the bytes after it in the new parser context.

For listed, that means remembering list, trying liste, failing on the d, then returning to list and reading ed as SUFFIX.

There is more implementation work because mask generation is speculative: llguidance is pushing and popping branches of a vocabulary trie, so fallback state has to roll back correctly too. Long unresolved gaps also need something better than blindly replaying an arbitrary number of bytes. The branch handles those details while leaving the ordinary fast path alone when no fallback is pending.

But the semantic fix is small. Greedy matching is allowed to try the longer lexeme. It just has to remember the last place where stopping was already valid.