The compiler story
From a model token to a question about the parser stack.
The long version fills an article. This is the short version: each token induces bounded lexer/parser behaviour; GLRMask compiles the shared structure of those behaviours into weighted automata that can be evaluated over the current parse state.
Model tokens are not grammar terminals.
A single BPE token can contain bytes that cross several lexer boundaries. So legality is not “is this terminal valid?” It is “can these token bytes be lexed into any terminal sequence that leaves some valid continuation?”
Vocabulary bytes → lexer paths → terminal sequences
" + foo"→bytes→WS · PLUS · IDENT
The Terminal DWA shares lexer work.
For a fixed lexer state, model tokens can produce different terminal sequences. The Terminal DWA stores the shared sequence structure once and carries token/lexer-state information in its weights.
One weighted graph instead of one automaton per token
Terminals become stack effects.
An LR parser reacts to terminals with shifts, reductions, and gotos. From outside, those actions can be summarized by the parser-stack symbols they require and the stack symbols they produce.
Terminal → bounded reads/writes on the LR stack
Compose them into the Parser DWA.
Substitute the stack effects for Terminal-DWA edges, cancel stack writes against later reads, project away the parts that only describe the future, then determinize. The resulting machine reads the existing parser stack from the top down.
Current stack prefix → weighted set of legal model tokens
Run it over all live parse stacks at once.
A GLR parser can have many live stacks with shared tails. GLRMask stores them as a weighted graph-structured stack. Running the Parser DWA over that compressed structure unions the legal-token sets from all valid parser alternatives.
Weighted GSS + Parser DWA → next-token mask
Full derivation
The weighted-automata article.
The complete version works through the construction, longest-match lexer semantics, the weighted GSS, code, equations, and benchmark context.
Read the long versionData structure
Weighted GSS on its own.
The persistent stack map used by GLRMask is also released separately, with an article on its representation and operations.
Read about weighted-gss