Correctness-Guaranteed Code Generation via Constrained Decoding
Authors: Lingxiao Li
salar rahili
Yiwei Zhao
Venue: COLM 2025 (2025)
Keywords: code generation
constrained decoding
correctness
llm
TL;DR: We present a constrained decoding algorithm that uses context-sensitive parsing with non-extensible regular expressions to generate semantically correct programs that can be extended to runtime guarantees

Abstract: Language Models (LMs) are increasingly being used for code generation, but ensuring the correctness of generated programs remains a significant challenge. Although imperfect code may be acceptable during software development with human oversight, domains such as video games and robotics require one-shot correctness for runtime-critical components. We present a constrained decoding algorithm for generating semantically correct programs that incorporates a context-sensitive parser, which, at each step, outputs a regular expression that satisfies a critical non-extensible property to guide the generation of the next token sequence that can continue to a correct program. To build such a context-sensitive parser, we propose a framework of a dynamic tree of parsers (ToP) during parsing, where each parser corresponds to a modular context-free grammar enriched with contextual information such as variable scopes and type constraints, with tree branches representing ambiguity in the future code segment. We demonstrate our approach through sLua, a strongly typed variant of Lua, showing that our method can generate semantically correct programs conforming to any prescribed scripting API. We further show that, with careful design, our semantic guarantees extend to runtime correctness, as validated in the application of generating game mechanics for a roguelike video game.

Published as a conference paper at COLM 2025
Corredhnes--Guranteed Code Generation via Constrained Decoding
Lingxiao Netflix
Salar Rahili Netflix
Yiwei Zhao Netflix
Los Gatos, CA, USA Lingxiaall@netflix.coom
Los Gatos, CA, USA srahilionetflix,
Los Gatos, CA, USA yiweizênet fl
Abstract
Language Models (LMs) are increasingly being used for code generation, but ensuring the correctness of generated programs remains a significant challenge. Although imperfect code may be acceptable during software development with human oversight, domains such as video games and robotics require one-shot correctness for runtime-critical components. We present a constrained decoding algorithm for generating semantically cor- rect programs that incorporates a context-sensitive parser, which, at each step, outputs regular expression that satisfies a critical non-extensible property to guide the generation of the next token sequence that can con- tinue to correct program. To build such context-sensitive parser, propose a framework of a dynamic tree of parsers (ToP) during parsing, where each parser corresponds to modular fontext-free grammar riched with contextual information such as variable scopes and type con- straints, with tree branches representing ambiguity in the future code seg- ment. We demonstrate our approach through sLua, a strongly typed vari- ant of Lua, showing that our method can generate semantically correct programs conforming to any prescribed scripting API. We further show that, with careful design, our semantic guarantees extend to runtime cor- rectness, validated in the application of generating game mechanics for a roguelike video game.
Introduction
The increasing adoption of large Language Models (LM) for code generation has revolu- tionized software development, particularly in the realm of Al-assisted programming tools such GitHub Copilot (Dakhel et al., 2023). These tools offer real-time code suggestions and completions, enhancing developer productivity across various domains. However, in runtime critical applications, such as control logic in embodied agents and on-the-fly gen- erative mechanics in video games, since there is no human programmer in the loop, the generated code must be semantically correct with runtime guarantees in one shot.
Recent advances in constrained decoding have allowed LMs to generate structured data that provably conform regular expressions (regexes) and more generally Context-Free Grammars (CFGs) (Koo et al.) 20244 Ugare et al.) 2024 Dong et al.) 2024). However, con- forming context-free grammatical rules far from semantic and runtime correctness. Although it is generally believed that constrained decoding can be extended to ensure se- mantic correctness, two main challenges remain.
First, the sequential nature of LMs requires immediate semantic feedback for each token generation in an incomplete program, which contrasts with the traditional compiler design that relies on an Abstract Syntax Tree (AST) of a complete program before performing semantic checks.

---

Published as a conference paper at COLM 2025
Secondly, the atomic building blocks of traditional parsing algorithms are terminals, which do not align with the tokens of the LM, resulting in challenges such token alignment and parser state bookkeeping.
To address the first challenge, we propose general recipe for building a context-sensitive Tree of Parsers (ToP) that flexibly incorporates semantic information and handles ambiguity. This is achieved by maintaining dynamic tree, each node containing a parser that cor- responds to a modular CFG of a language construct (Section 4 From an incomplete pro- gram, ToP generates regex satisfying crucial non-extensible property (Assumption that determines the successive character sequences capable of extending the present pro- gram while adequately long to move the parser state forward.
To address the second challenge, we have introduced constrained decoding method (Al- gorithm [ that coordinates a context-sensitive ToP with an LM to produce semantically correct programs that can be parsed by the ToP. At each step, the regex output by the ToP guides the LM in generating the next sequence of tokens, which are then used to advance the parser state, resulting in an incremental generation process. Our algorithm includes token healing procedure (Fig. 2 to handle misalignment when tokens cross the boundaries of the regexes.
We construct a ToP for a custom language, sLua (Section 5), a strongly typed version of Lua with simplified language features. sLua code can be easily translated to Lua for execution. Although our recipe for building a ToP' is language-agnostie need for type inference and the number of tree branches (Theorem 5.1). Combining sLua's ToP with Algorithm [ we have obtained a constrained decoding algorithm that generates semantically correct sLua code, while preserving the ability generate all possible seman- tically correct programs.
strong typing reduces the
As an application, with an off-the-shelf LM, we show how our method can be used to generate new mechanics for a roguelike video game, producing diverse and creative code that conforms to a scripting API (Section 6.1)). Moreover, with careful API design and rea- sonable language feature restrictions, we show that our semantic correctness guarantees can extend to runtime correctness without losing expressiveness (Theorem 6.1). Our ap- proach opens up new possibilities for using LMs in runtime-critical applications, enabling the generation of complex, error-free code within production environments.
2 Preliminaries
Constrained decoding (Deutsch et al. 2019) is a popular technique for generating struc- tured output with LMs. At each decoding step, tokens that violate the constraint have their probability set to 0 in the next-token probability vector output by the LM. The masked-out probability vector is then renormalized before sampling the next token. While constrained decoding can distort the distribution (Park et al. 2024), it is widely used in both closed-
source (OpenAl 2024) and open-source tools (Willard & Louf 2023 Dong al.. 2024) due to its simplicity.
The crux of constrained decoding relies on having a stateful oracle that can efficiently re- turn mask for the invalid next tokens at each decoding step. When the constraint is regex (Chomsky) 1956), the oracle can be implemented as a Finite-State Automaton (FSA) that accepts the language, so that the set of valid next tokens can be deduced from the tran- sitions from the current FSA state by indexing (Willard & Louf 2023) or transducing (Koo) et al. 2024 These techniques can be extended to CFGs by using a pushdown automaton (PDA) (Hocrrof et al., 2001) instead of an FSA. However, formal models such as FSAs and PDAs are not powerful enough for context-sensitive parsing, rendering these constrained decoding techniques unsuitable.
Poesia et al. (022) proposed using completion engine that takes partial program and outputs the set of valid tokens that extend the program while incorporating semantic con-
Throughout we will use "tokens" to refer to the LM tokens, not to be confused with terminals in CFG.
2

---

Published as a conference paper at COLM 2025
straints. However, their completion engine is not incremental, leading to full verification of the program after each token generation. In our work, we identify a core requirement (As- sumption (A1) that leads to incremental constrained generation with token healing (Algo- rithm 1.. Moreover, they target relatively simple programming languages such as SQL and SMCalFlow and do not have a general-purpose solution to handle ambiguities arising from multiple context-dependent rules. The approach Agrawal et al.) (2023) also addresses se- mantic correctness via constrained decoding, but in narrower setting that focuses on the language feature of dereferencing an object. One key limitation of their method is that it can incorrectly accept long tokens that start with valid prefix but end with an invalid suf- fix. Our approach differs by incorporating a token healing algorithm specifically designed to handle such boundary-crossing token errors, ensuring greater program integrity.
Most relevant to our method, the concurrent work of Mündler et al. 2025 developed type-constrained decoding approach using prefix automata to reduce compilation errors in TypeScript. Their prefix automata are similar in spirit to our Tree of Parsers (Tol",, as both ensure that every reachable state can be extended to a valid final program. Our con- struction, however, leverages general-purpose CFG parser generator (Shinan 2018 to process modular grammar templates enriched with contextual information. This allows us to offload the direct handling of grammar parsing to the generator. In addition, our work focuses on generating code with formal runtime correctness guarantees, ensuring that scripts terminate and execute without errors in a live environment, whereas the goal of Mündler et al. (2025) is to reduce compilation errors and improve functional correctness.
Context-Free Grammar (CFG) A CFG (Aho & Lam 2022, Sec. 4.2) is described by set of rules (nonterminals) and terminals. A terminal regex or literal string. A rule list of terminals and rules. The language of CFG is the set of strings that can be generated by starting from the start rule and repeatedly unrolling rules until only terminals remain. Á program is syntactically correct if it is contained in the language of the CFG. An example CFG for type specification for sLua shown in Appendix B.2.6 whose language includes strings like number, (string, (roblenn)>stiinng
3 Context-Sensitive Constrained Decoding
Overview We start by presenting our overall algorithm in Algorithm which takes context-sensitive parser and a language model and generates programs that can be parsed by P. We defer the construction of P to Section 4 and assume for now that P supports the following:
has finished(): Whether complete program has been parsed.
next.regex (): Returns a regex satisfying Assumption (A1) match the next segment.
feed (s): Takes in a segment advances the parser state.
At each step of the generation algorithm (Algorithm 1. use the regex output of to guide the generation of the next segment of the program that will then be fed to advance the state of P. We use token healing procedure (Fig 2 to handle the token misalignment issue when a token crosses the boundary between two consecutive regexes.
Regex Requirement When using regexes to successively guide constrained decoding, main challenge is to construct the regexes such a way that the LM has the option to stop generation when the regex matched, so that the parser state will advance. Normally, an LM outputs a special stop token to end the generation. However, here we are using an LM to generate one segment of the program at time. Since LM is typically trained complete programs, the probability of sampling a stop token mid-program is close to zero.
Example 3.1. Suppose that the parser indicates that the next program segment should be an in- teger and the regex is / /[0-9]+/. Since this regex match digits indefinitely, in order to stop generation, the constrained decoding algorithm must decide when to stop. However, if we modify the regex to / [[--]]++0 +]++<N+++>>>>>>>> where <END> is set of symbols that signal the end of integer
3

---

Published as a conference paper at COLM 2025
Algorithm 1: Context-sensitive constrained decoding with token healing
Input:
Context-sensitive parser P, language model L, prompt prompt Output:
Generated program
prog, prefix, prompt tokens +- "" "", L. tokenize (prompt)
while not P. has fiasffinshed(( do
// Modify regex from P.next_reeex) to support token healing (Fig. I f re. re.escape (prefix)+ "(" + P. next.regex ()+ ")" ".*"
A < build
// build deterministic finite automaton (DFA) from
s, output.tokent + A. iniitallsstttee, []
while $ A. finall states do
// adaptive rejection sampling to find valid token
logits <- next token (proms tokens + output.tokens)
order argsort (log(-log (random (len (logits)) logits) // Gumbel-top-k trick (Kool et al 2019
for t in order do if acceptsss then
S A. transitionn t)
titput..okkns. break
output, new prefix "" woi.totttuuutttoooooo.o..... token))) if A. coutppu
then
// last token is partially matched
last.token output.tokess.... ()
output + join (output.tokenss
new new.prefix f prefix of last. such that A. wcc.ctts prefix)
new prog f (output
pew.prefix [len(prefix):]] :J)
P. tex
// advance parser
prompt.tokens t prompt.tokens output,token
prefix, prog <- new new.pree www.prfix prog + new.prog
return prog + prefix
Go/Mam: raal
namber
Assignment
Godharn: vol mumber
Block
LocalVarbef
Block
LocalVarDef
Block
LocalVarDef
WhileBlock
TypeSpec
EXp<SELF>
Exp
PrefixExp
IfBlock
PrefixExp
ocal xo number Getilmm))
Tumber Gathumi))
local x: number
GetNumm))
Geriomm: void number
Gethum void +> rumber
GcNum vod number
Assi Assignnent
LocalVarDef
LocalVarDef
LocalVarDef
EXL<S
Exp
Exp
PrefixExp
Whileblock
PrefixExp
Anglist
PrefixExp
IfBlock
xt: Sathumi)
number
GetNumm
local number GetNNum))
Figure 1: Illustration of the dynamic tree of parsers on an sLua statement. The purple box represents the environment which tracks variable scopes and types. The yellow box shows the parsed program (in black) and the future segments rectangles represent parser nodes, and the arrows point from parent nodes to their chil- dren. Red arrows indicate parser nodes that will be pruned upon consuming the next segment. Each path from the root to a leaf represents a possible stack of parsing states that could lead to a complete program. See Appendix C.10 for examples of regexes output by the root parser.
be parsed (in gray). Rounded

---

Published as a conference paper at COLM 2025
NewTalent (Iname
prev regex
prec: next regex
Figure 2: Illustration of token healing for a code segment in the talent script of DCI (Sec- tion6.1). Left: blue (resp. red) brackets indicate boundaries of the regexes from the context- sensitive parser (resp. of LM tokens). For instance, while {f is single token, it crosses the boundary between two regexes, one for NewTalent and one for just the curly brace {- Right: our token healing method in Algorithm that prepends the matching prefix of the previous token to the regex while allowing the last token to be partially matched.
depending on the current context, then the responsibility to stop is delegated to the LM which is after all the code generator. For example, if the integer is the last argument of function call, then <END> should include ); if the integer is part of an arithmetic expression, then <END> should include any arithmetic operators, and if there is matching in the parsed program.
To formalize intuition in Example 3.1 we impose the following requirement:
Assumption (A1) (Non-extensible match). In Algorithm 7 any regex returned by P. Peext_regex () must satisfy: If a string s matches the regex, then any extension of s must not match the regex.
In other words, in Deterministic Finite Automatons (DFAs) constructed in Algorithm 1 one cannot reach a final state from another final state. Therefore, once the DFA is in a final state, we can confidently stop the generation and move on. We defer to Section on how to make the parser satisfy Assumption (A1) using a look-ahead strategy.
Speeding up with Adaptive Rejection Sampling In order to use regex to guide gener- ation, we first build a character-accepting DFA and then use adaptive rejection sampling Gilks & Wild 1992) to sample a valid next token at each decoding step. We use adap- tive rejection based on the observation that modern LMs generate correct code without constrained decoding in most cases; indeed, adaptive rejection reduces to unconstrained sampling if the first sampled token is valid. The alternative is to compile the character- accepting DFA into token-accepting DFA (Willard & Louf 2023 Koo et al. 2024). How- ever, as the regex is constantly changing, the cost of compilation for each semantic segment of the parser is very high. In Table [ we benchmark the generation speed of the alterna- tives, showing that the adaptive rejection sampling is more than three times faster than Willard & Louf (2023) and Koo et al. (0024) when used in Algorithm
Handling Token Misalignment at Regex Boundaries Since LMs have custom subword tokenizers, their tokens can cross the boundary of successive regexes output by the context- sensitive parser. To address this misalignment issue, we added token healing strategy in Algorithm [illustrated in Fig. ? We use prefix variable to keep track of the prefix of the partially matched token from the previous regex, while modifying the regex by prepending the escaped string of prefix and appending * to match an arbitrary suffix. This guaran- tees that the first generated token must start with prefix and the last token is allowed to partially match. Thanks to Assumption (A1) after the modification of the regex, if the cor- responding DFA is in a final state, then we know the last token fully or partially matched and we can stop the generation for the regex.
Context-Sensitive Parsing via a Dynamic Tree of Parsers
Our context-sensitive parsing design is based on two insights:
It is difficult to inject context into the full CFG of programming language. However, if we concerned with only specific language construct (e.g. type specification), locally, it is possible to create another CFG that is enriched with semantic context (e.g. Appendix B.2.6) and only accepts semantically correct code.
5

---

Published as a conference paper at COLM 2025
Many CFG rules naturally align with the context boundaries. For example, scoping changes when entering blocks, and the context gets updated after processing variable declarations.
Based these insights, we developed two-stage solution that builds dynamic tree of parsers (ToP). Each node this tree is associated with a CFG and an interactive parser (Appendix A.1 generated for that CFG.
The value our ToP construction goes beyond constrained decoding. It can incremen- tally verify the semantic correctness of an incomplete program. This can be utilized as reward model for reinforcement learning to finetune a language model to better produce semantically correct code.
Stage 1: Refactor the complete CFG into modular CFG templates
First, we refactor the complete CFG of the target language into modular CFG templates. These templates leave out slots that are populated with semantic context during parsing. We add special terminals called placeholders the CFGs to indicate recursion point where a child parser needs to be spawned the corresponding placeholder is in the accepting of terminals of the parent parser. In Appendix B.2 refactoring is done for sLua.
we detail how the complete CFG
Example 4.1. Consider simple modular CFG for string expressions in sLua:
str_exp: str_sum str sum: str_atom (".." " .str ator)
str atom: STRING | "(" exp ")" "<STR PREF EXEFIXXEE EXP>""
This grammar matches string atoms that can be concatenated using the operator. String atoms can be literal quoted strings (represented by the terminal STRING whose regex is omitted), paren- thesized string expression, or a prefix expression of the string type (such as string variable, function that relurns string, or a chained function call that eventually refurns string). We use indicate that upon expecting this terminal to one of the possible outcomes (in addition to string literals and parenthesized str_exp), the parser of this CFG should create a child parser of type string prefix expression (Appendix B.2.7
the placeholder <STR PWWPPRRFFIEEEEXE
Stage Define the Tree Parser Nodes
Next, to form the ToP,, for each modular CFG template from the first stage, we define tree node type. Each instance of the node contains a parser generated from the corresponding CFG template (Appendix A.1 whose slots are populated with semantic context during parsing. Each node supports three functions, finisen,, next.regex, and feed_text, similar to those described in Section but specialized for the modular CFG associated with the node. Each node manages its own parser state, and the overall context-sensitive parser is simply the root node of the tree.
The parsing process involves the following. Fig. iillustrates how ToP evolves when pars-
ing local variable definition for sLua
Get next regex: Before forming regexes, parser node checks whether there are place- holder terminals in its accepting set; if so, a child node will be created for each place- holder. If the accepting set contains terminals that not placeholders, the parent node spawns copy of itself as a child node to handle the continuation. To produce a regex for the next valid program segment, union of all accepting terminals of its parser is returned; otherwise, it forms the union of the regexes from all its children's 's next regex. This combined regex describes all valid continuations of the current program.
node has no child, the regex representing the
Advance parser state: When new segment (e.g. sequence of tokens generated by an LM) is fed to a parent node, delegates the segment to all its children. any child fails to parse the text indicating conflict, then that child is removed from the parent. If child's has finished returns true after feeding a segment, all children the parent are removed, and the parent parser is advanced with the placeholder of the finished child

---

Published as a conference paper at COLM 2025
(or, in the case of the child being copy of the parent, the parent's parser state is replaced with the child's) s).
In Algorithm 2 we provide a pseudocode for base class for the nodes. At any point, any path from the root node to leaf represents stack of nested parsers that at least one valid complete program can continue from these parser states. As more code is consumed, the tree branches that result in conflicts are pruned, ensuring that only valid paths remain.
Environment management As in static analysis, we assume that the static environment is being tracked based on the parsed program thus far; the implementation of the track- ing is language dependent, for example, as stack that tracks scopes and symbols in each scope. Before creating a parser node, if its CFG template has slots, we query the current environment and populate the slots accordingly. The environment is then updated when certain parsers finish parsing (e.g. when defining a local variable) or when certain termi- nals are consumed (e.g. when entering/ peerrinngxxxiting /exiting a scope by encountering do ta/tthen/ente For instance, when spawning the string prefix expression child parser in Example 4.1 we need to query the environment for all symbols (variables and functions) that can eventu- ally result in a string type. While ToP has multiple branches to handle future ambiguities, we only need a single environment since it is based on the parsed program.
Controlling the size of ToP The time complexity of parsing with ToP is directly propor- tional to the size of the tree. While in general this size can be large, when the programming language front loads specifications that reduce ambiguity of parsing (e.g. type specification before any expression), the tree size can be significantly reduced. We characterize the case where the ToP has "broom" shape, ensuring the tree remains compact. In Lemma B.1 we show that our sLua ToP satisfies this assumption.
Assumption (A2) (Broom-shaped ToP).. When parser node spawns more than one child, all ancestors of x can have only one child.
Satisfying the non-extensible match property To ensure that the regex of the ToP root node satisfies Assumption (A1) we recommend a look-ahead strategy that requires the following assumption in modular CFGs:
Assumption (A3). A terminal that is either a placeholder or violates Assumption (A1) in a mod-
ular CFG must be followed by non-placeholder terminals satisfying Assumption (AD)
This assumption is typically met by popular programming languages, which often include many delimiters, such as; following a statement in C-style languages, end concluding block in Lua, or) succeeding a function call in various languages. We prohibit follow-up with placeholder to prevent recursive look-ahead.
Look-ahead strategy to extend regexes for non-extensibility When a terminal or the regex returned by child node violates Assumption (A1) we look ahead at the set of next
terminals after accepting the terminal or the placeholder and append a regex matching the
set of next terminals to the regex. To ensure that modular CFGs do not end with terminal
that breaks Assumption (A1) we add a slot for ending symbols at the end of the starting rule when needed. At instantiation, we query its parent parser for terminals after accepting the child's placeholder and insert a regex representing the union of these terminals to the ending symbols slot. Example regexes obtained after applying this strategy for sLua can be found in Appendix C.10
5 sLua Language and Parsing
We have designed a custom programming language called sLua and developed a ToP for it based on the framework in Section sLua is strongly typed variant of Lua with re- stricted language features. It supports common types such as numbers, strings, booleans, functions, and user-defined fixed-size tables. Additionally, it supports variable declara- tions, standard control flow constructs, expressions, and function calls. In particular, state- ments must end with semicolon to satisfy Assumption (A3) and type annotation in
7

---

Published as a conference paper at COLM 2025
the style of Luau [Roblox] 2019) is required after the declaration of the local variable to en- sure satisfaction of Assumption (A2) Dynamic data structures, nil pointers, and recursive function calls are not supported in favor of runtime correctness guarantees (Theorem 6.1
See Appendix B.1 for more details and Example B.1 for an example.
In Appendix B.2 we provide implementation of the ToP for sLua which offers the fol- lowing timear-tie parsing guarantee, as proven in Appendix B.3
Theorem 5.1 (Linear-time parsing of sLua). Consider the implementation of ToP for sLua de- scribed in Appendix [8.2] Suppose that during parsing the number of variables in the scope, the number of nested function calls, and the number of scopes are bounded by a constant. Then, both the functions next_regen and has fasifinssedd of the root node in the ToP have constant time complexity, and the feed.text function has linear time complexity in the size of the input.
We selected Lua as our base language because our primary focus is to generate programs conforming to certain API specifications which is achieved by defining global tables in the environment. The embedded nature of Lua makes it particularly well-suited for this purpose. Moreover, LLMs have been trained on substantial amounts of Lua code, so they generalize sLua well with proper instructions and few in-context examples.
To run the sLua code, we augment each node of the ToP to output an AST. This involves replacing each placeholder with the corresponding AST of the child node. Based on the AST, we then translate the sLua program to Lua program (e.g., remove type annotations) and use the Lua interpreter to execute the translated code. The same procedure can be adapted to translate sLua to other host languages.
On-the-Fly Generative Game Mechanics
6.1 Dungeon Crawl Infinite
Recent efforts to integrate LLMs into games at runtime have primarily focused on narrative generation (e.g. [nworld (2021) or black boxes (Al Dungeon, 2019) to predict outcomes. We instead consider creating game mechanics on the fly by generating scripts (e.g. Lua) that the game engine can directly run. This approach offers several benefits: direct en- gine compatibility, consistent and reusable scripts that reduce computational costs, and full transparency provided way to accurately describe the scripts to the player. The pri- mary challenge, ensuring that the generated code is correct and does not crash the game, is precisely what our work addresses.
We built turn-based roguelike game called Dungeon Crawl Infinite (DCI) to demonstrate the capabilities of our serrectness-guaaanteen code generation framework. DCI directly inspired by Casalini 20122), highly rated roguelike RPG featuring turn-based combat and advanced character building. In DCI, the player controls a character exploring a dungeon, fighting monsters, and building up their character procedurally with generated talents and effects given the player's 's input. See Appendix C.1 for an overview of the game flow. Both talents and effects are implemented as sLua scripts:
Talent: Contains a Do function that executes whenever a player or enemy uses the talent.
Effect: Tracks states (e.g., poison stacks) and implements hook functions (e.g., OnTurnEnd, OnDamageReceived) that the game engine calls at specific moments.
Both include a GetDescription function that returns dynamic text description reflecting the current game state, informing players about the talent or effect's functionality. Scripts can reference each other through API functions (e.g., effect. Apply (actor, param)), en- abling complex and synergistic combinations despite the system's simplicity. We design comprehensive sLua API (Appendix C.3) for DCI containing 55 functions (also extended by each effect definition) that cover rich game mechanics.
To generate talent and effect sLua scripts using Algorithm 1 we have developed special- ized root parser nodes (Appendix (C.) on top of the sLua parser nodes to ensure that the generated programs fit the templates for talents and effects. The effect parser node
8

---

Published as a conference paper at COLM 2025
demonstrates how to easily parse user-defined classes by extending the provided set of sLua parser nodes.
Provably runtime error-free design While determining whether program in a Turing- complete language executes without errors is NP-hard (as demonstrated by the halting problem), we achieve provable error-free execution by carefully restricting sLua's language features and designing DCI's API. Our approach combines several key strategies detailed in Appendix C.5 safe callback pattern that eliminates null pointers, guaranteed termi- nation through limited loop iterations and lexical scope function references, and capped recursion depth for effect hooks. This design trades some expressiveness for safety, a rea- sonable compromise since most game scripts are relatively simple and do not require com- plex language features. We formalize this below (proved in Appendix C.5).
Theorem 6.1. Given the API in Appendix Cad using the techniques described in Appendix C.5 scripts successfully generated for talents and effects in DCI using Algorithm are guaranteed to terminate and execute without runtime errors in the game engine.
Despite this strong runtime-correctness guarantee, Algorithm iitself is not guaranteed to terminate. Nontermination a well-known issue in constrained decoding; it is part of the more general issue of distribution distortion, where the LM could get the constraints slightly wrong and then corner itself to generate repetition or junk text. We discuss this challenge further in Appendix C.9
6.2 Experiments and Evaluation
To evaluate our pipeline, we propose the following challenging task: generate a talent cate- gory in DCI. A talent category in DCI consists of 4 talents and up to 4 effects whose theme adheres to given prompt. Talents and effects can refer to each other in the same cate- gory, enabling a complex web of interactions. We use a simple LLM agent to guide the generation of a category (Appendix(Co. C.6).
We prepared a total of 8 talent category prompts (detailed in Appendix C.8) test each method. The effects are generated first, followed by the talents. Generated scripts are reg- istered in the environment and included in future prompts, so that future scripts can refer to previously generated scripts. This extends the correctness guarantees of Theorem 66.1 talent categories. For in-context examples used in the prompts, we handcrafted effects and 6 talents that cover various API usages.
Talent Category Score Distribution Across Methods
Unconstralnediuwe222 5:328-Codar)
Ubconstrained/(0we2 5-328-Oodw)) Reflection
UnconstraineeiClludpp
3.t. S.5:oonatt))
UrcconttaiieedjClaaddl 3.5-Sonnet) -eellction
Frequency
Durs(Qwen225- 5-22 Coder)
Oursi (-322-Codrrr-- Reflection
15
12
2
40-55
60-79
80-102
Talent Category Score (0-100)
Figure 3: Histogram on talent category scores for various methods. For each of the 8 tal- ent category prompt, we each method 10 times, for total of 80 data points for each method in the histogram. An unsuccessful generation is treated as 0 in score. Our method with constrained decoding achieves the highest success rate and quality scores, especially when combined with reflection. For highest quality scripts in score range 90-100, Claude- 3.5-Sonnet (with reflection) has 38 data points compared to 33 data points of ours (with reflection). Our method failed only when the generation did not terminate (Appendix C.9
For baselines, we consider unconstrained generation using Claude-3.5-Sonne' (Anthropic 2024), one of the best closed-soure coding LLMs, and @wwen2.5-32B-Codee HHui et al. 2022
one of the leading open source coding LLMss. For method in Algorithm

---

Published as a conference paper at COLM 2025
Unconstrained
Willard Louf (2023) Koo et al. (2024)
Ours
tokens/sex
18.89
2.04
1.47
7.64
compilation/ton tootal
0%
73.35%
79.41%
4.98%
Table 1: Time comparison of regex-compilation subroutines for constrained decoding in Algorithm [ for generating single DCT talent category with prompt "Magic that mixes the power of ice and poison." Measured time excludes the parser update which consis- tently has throughput of over 1500 characters per second. All methods first compile logit processor and then use VLLM's API (Kwon et al. 2023 to carry out constrained de- coding. For Willard & Louf (2023), the compilation step involves indexing that converts character-acceptingg DFA to token-accepting DFA. For Koo et al. (2024), the compila- tion step involves concatenating the DFA of the regex with a character-to-toker transducer (precomputed), followed by a determination step using the OpenFST library (Allauzen et al. 2007]. Note that we did not implement the wildcard handling in Koo et al. 2024), which could explain the speed drop compared to Willard Louf (2023) as reported in their paper, as their wildcard handling strategy reduces the flexibility of the regexes. The significant speedup of our adaptive rejection sampling is explained by the fact that as the regex is constantly changing, front-loaded compilation to token-accepting DFA is waste- ful compared the lazy construction of the same DFA of adaptive rejection sampling, This experiment is done with 8 A100 GPUs running Qwen2.5-32B-Cod just like the rest of the experiments.
finite state
the LM. In addition, each method includes reflection version. If the initial code generation inllc-indccated by parsing error of our parser- then the same LM is prompted to correct the generated code using the error location and the anticipated subsequent regex as guidance in the prompt. This reflection strategy represents the typical rejection sampling technique use LMs to correct the generated code. For evaluating quality, we use Claude-3.5-Sonme
use the same Qwen2.5-32B-Code
to output score between 1-100 to judge the code quality and how well the generated program matches the description returned by the GetDescription function for each talent.
The results are reported in Fig. 3 For our method, we terminate the generation and count as failure if the total number of output tokens is over 1500-this typically leads to indefinite repetition of output. In Appendix C.10, we provided examples of failure cases for each method. While unconstrained methods typically failed due to hallucination of variables in scope and incorrect syntax, our method failed only when did not terminate after the output token limit, when constrained decoding cornered the LM to output an indefinite repetition due to distortion of distribution (Appendix C.9
In Table 1
we show the inference speed of our method with adaptive rejection sampling compared to regex-compilation alternatives.
7 Conclusion
We presented Algorithm 1 to generate porrectness-guaranted programs via constrained decoding with a context-sensitive parser built tree of parsers (Section This demon- strated through sLua, strongly-typed version of Lua, a roguelike game DCI. As shown by our results and discussed in Appendix C.9 auto-regressive constrained decoding can distort distribution, resulting in nontermination of generation or sub-par quality program quality. A unique opportunity that the context-sensitive parser can provide additional context information for the LM that can help restoring the distribution. Exploring post- training techniques that use parser hints to combat the distribution distortion issue promising future direction for generating high-quality, and perretness-guarrntee pro- grams.
10

---

Published as a conference paper at COLM 2025
Acknowledgment We thank Alain Dessureaux, Sun, and Danny Diaz for the discus- sion of on-the-fly code generation in video games and for their feedback on the Dungeon Crawl Infinite game prototype. We also thank Dawen Liang and Nathan Kallus for the discussion on LLM post-training techniques and for their feedback on the initial research plan.
References
Lakshya A Agrawal, Aditya Kanade, Navin Goyal, Shuvendu Lahiri, and Sriram Rajamani. Monitor-guided decoding of code Ims with static analysis of repository context. Advances in Neural Information Processing Systems,
2023.
Alfred Aho and Monica $ Lam. Compilers principles techniques tools. Pearson, 2022.
AI Dungeon. Ai dungeon. https://aidunngenn.com com/ 2019.
Cyril Allauzen, Michael Riley, Johan Schalkwyk, Wojciech Skut, and Mehryar Mohri. Openfst: A general and efficient weighted finite-state transducer library: (extended ab- stract of an invited talk). In Implementation and Application of Automata: 12th International Conference, CIAA 2007, Praque, Czech Republic, July 16-18, 2007, Revised Selected Papers 12, pp. 11-23. Springer, 2007.
Anthropic. Claude 3.5 sonnet. httos://ww..nnttrpiic.cc/cccaaa 2024.
Nicolas Casalini. Tales of maj'eyal, 2012. URL https://////
Noam Chomsky. Three models for the description language. IRE Transactions on infor- mation theory, 2(3):113-124 1956.
Arghavan Moradi Dakhel, Vahid Majdinasab, Amin Nikanjam, Foutse Khomh, Michel C Desmarais, and Zhen Ming Jack Jiang. Github copilot ai pair programmer: Asset or liability? Journal of Systems and Software, 203:111734, 2023.
Daniel Deutsch, Shyam Upadhyay, and Dan Roth. A general-purpose algorithm for con- strained sequential inference. In Proceedings of the 23rd Conference on Computational Natu- ral Language Learning (CoNLL), pp. 482-4922 2019.
Yixin Dong, Charlie F Ruan, Yaxing Cai, Ruihang Lai, Ziyi Xu, Yilong Zhao, and Tianqi Chen. Xgrammar: Flexible and efficient structured generation engine for large language models. Xrviv preprint ar arXiv:2411.15100 2024.
Walter R Gilks and Pascal Wild. Adaptive rejection sampling for gibbs sampling, Journal of the Royal Statistical Society: Series (Applied Statistics), 41(2):337-348, 1992.
John E Hopcroft, Rajeev Motwani, and Jeffrey Ullman. Introduction to automata theory, languages, and computation. Acm Sigact News, 32(1):60-65, 2001.
Binyuan Hui, Jian Yang, Zeyu Cui, Jiaxi Yang, Dayiheng Liu, Lei Zhang, Tianyu Liu, Jiajun Zhang, Bowen Yu, Keming Lu, et Qwen2. 5-coder technical report. arXio preprint MxXi::209.122888 2024.
Inworld. Inworld ai. https://inworld.alt 2021.
Terry Koo, Frederick Liu, and Luheng He. Automata-based constraints for language model decoding. Xiv preprint ar Xxiv:2407.088003 2024.
Wouter Kool, Herke Van Hoof, and Max Welling. Stochastic beams and where to find them: g
The gumbel-top-k trick for sampling sequences without replacement. In International Conference on Machine Learning, pp. 3499 3508.. PMLR, 2019.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. Proceedings of the ACM SIGOPS 29th Symposium Operating Systems Principles, 2023.
11

---

Published as a conference paper at COLM 2025
Niels Mündler, Jingxuan He, Hao Wang, Koushik Sen, Dawn Song, and Martin Vechev. Type-constrained code generation with language models. Proceedings of the ACM on Pro- gramming Langunges, 9(PLD1):601626, 2025.
OpenAI. Structured outputs, 2024.
URL https://laatromm...ppaa..c//c//p
structured-outputss
Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrice Nadia Polikarpova, and Loris D'Antoni. Grammar-aligned decoding. arXiv preprint ar Xf:::2245522147, 2024.
Gabriel Poesia, Oleksandr Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models. Xrviv preprint ar Xri::2201.11227, 2022.
Roblox. Luau programming language. https://luau.or org// 2019.
Erez Shinan. Lark: A modern parsing library for python, 2018. URL htLhhtts:///gthhbb com/ park-parsr
Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. Im- proving Ilm code generation with grammar augmentation. CoRR, 2024.
Brandon T Willard and Rémi Louf. Efficient guided generation for llms. arXiv preprint imXiv:2307.09702 2023.
A Details on Tree of Parsers
We provide in this section our implementation of the ToP framework discussed in Section
A.1 Interactive CFG Parser
Our tree-of-parsers framework (Section 4 requires generator of interactive parsers (IPs) from modular CFGs during parsing. An interactive parser is parser that provides the following functions:
An accepts () function that returns the set of terminals (and their regexes) currently accepting.
A (sed.text(s) function that advances the parser state by consuming the input string and raises error if the input is invalid.
While several parser tools can be used to generate IP's, we use the LALR(1) implementation in Lark (Shinan, 2018) for its linear time complexity and ease of use. While this poses some restrictions on the allowed CFGs, most programming languages can be rewritten in a CFG that belongs to LALR(I).
A.2 Implementation of ToP
We use object-oriented approach to define classes for the parser nodes. Recall that each parser node is associated with modular CFG, and the parser node is only responsible for parsing the program described by its modular CFG. Each parser node class inherits from an abstract base class BaseParser that implements has-fing has.finished next_regex, and feed_text we provide pseudocode (using Python syntax) for these functions in Algo- rithm 2 and needs to implement the following fields/fung functiins
ip: An IP for the modular CFG.
placeholders: A set of terminals corresponding to placeholder terminals, indicating when to spawn children.
spawn child (t): function that returns a child parser corresponding to the placeholder
t.
12

---

Published as a conference paper at COLM 2025
finish.child(t): A function that merges the result of the child parser corresponding to the placeholder back to the parent parser.
Child classes of BaseParser may override functions has has_finished, next_regex, and feed_text to implement more complex parsing logic. Not included in Algorithm iis the lookahead strategy described at the end of Section to make the resulting regex satisty As- sumption (A1) This needs to be applied on a case-by-case basis depending on the specific CFGs and the child parsers.
A.3 Using ToP for Parsing
We describe in this section the simple algorithm (Algorithm 3) of using context-sensitive parser with interface described in Section to parse complete or incomplete program.
B Details on sLua Language and Parsing
B.1 sLua Language
Here are the main differences between sLua and Lua:
Statements must end in ;. This is to simplify the parsing algorithm to satisfy Assump-
tion (A3) by having natural boundaries between statements.
The basic types are number, boolean, and string. Custom fixed-size table types (such as Actor and Coord) are supported similar to named Lua tables. Dynamic data structures and nil pointers are not supported in favor of runtime correctness the scripting API usually has workaround (e.g. via safe callback patterns as in Example(C.I)
The definition of a local variable or function must fully specify the types using the syntax local <var>: <type> = <exp>. For instance,
local b: boolean x == 3; local foo: (number) boolean function(x) return 0; end; local target: Actor nil;
local coord: Coord {x 3, = 4};
For functions with non-void return types, all control branches must return with the cor- rect return type.
Comments (e.g., -- in Lua) are not supported to simplify parsing. is possible to sup- port comments by pausing the parsing process and resuming after the comment, but this would complicate the parsing algorithm and can cause tokenization issues.
Strong typing is essential, knowing the type of an expression before parsing the expres- sion significantly reduces the number of branches in the parsing tree, ultimately leading to our linear-time parsing guarantee (Theorem 5.1
We feed these specifications about sLua as part of the system prompt whenever we are generating sLua code.
Example B.1. Below are two example sLua scripts for implementing a poisoned effect and a catalyst talent in DCI (Section (). The poisoned effect inflicts damage to the target at the end of each turn. The catalyst talent doubles the poison count on the target if is already poisoned, otherwise it inflicts a new poison effect. Variable names prefixed with g are global variables. Note all methods are called with. instead of in usual Lua. In our Lua engine, modified metatables for all involved classes so that self will be automatically passed as the first argument if what follows is function.
interface ParamData { poison: number,
};
do
NewEffect ({
13

---

Published as a conference paper at COLM 2025
Algorithm 2: Base parser class for tree-of-parsers nodes
Function BaseParser next nextt regex
accepts <- accepts))) existtnonpllcceoolder k- false self. children is empty then for in accepts do if t in self. plachholerrs then
self. celf.cnhidrrent] self. spwwn. ctild(t)
else
exist.nonplaceholder <- true
if self. children is empty then
// We leaf node, so collect regexes from nonplaceholder terminals.
regexes t regexes from terminals accepts seel. placeholerss else
if wwwesxtnonpplateeeeee nomplaccohee then
There are nonplaceholder terminals in addition to placeholders, so we need to make sure there is continuation of the current parser state. self. www.echhcllenneeeee self.ip
//
+ spawn copy of self with clone of
regexes < []
for child in self. col.deheidren... values do regexes. append (child .nxxt regex())
// Not included in this pseudocode is the lookahead strategy to make the resulting regex satisfy Assumption (A1) This needs to happen before taking the union the regexes.
return "("
(Iegexe))) ")"
Function BaseParser. fee. feel, s)
if self. children is empty then
L self. feed text(s)
else
fort, child in self. children. () do
try
child. (s)
except
del child[]]
prune the errored child parser
if children is empty then raise exception; // dead end
else if self. children. keys ()== ("<SELF>") then
// other children failed; merge back parent.
self. ip +- self. chwldrenild""" ("seen=("""L""]] selldchi O
else
for child in self. children. items () do
if child. has finished() then
One child succeeds in parsing; merge back to parent. self. children 0 self. diiishhchildd
break
Function BaseParser. www.
return self. self.ip. accepts ()== ("$END")
// "/ENNND" is special terminal for the
interactive parser to indicate the end of parsing
14

---

Published as a conference paper at COLM 2025
Algorithm 3: Parsing program using context-sensitive parser
Input: Context-sensitive parser P, program prog
Output: (success, finished), where success indicates whether parsing is successful without error, and finished indicates whether the the program is complete.
i +0 0
while not has finished do
r f P. .next_regex
// r satisfies Assumption
(A1)
build_DFA(r)
S - A. iiiitiill state
segment <-
while & A. s.final.states do
try
A. transitionns,, prog[i])
except
return False, False
// parsing
peggentt.apenddprroo
i 1 if == len (prog) then return True, False
// incomplete program
P. Feed_text(ssegne success + == len // handle the case where prog has extra characters at the end return success, success
name = "Poisoned", beneficial false, detrimental true, OnTurnEnd function (param) param.. ownor. wwwpuuaateeeeaaaaaeeee end,
data. poison);
OnMerge function (param, new_param)
param. duraaidurationn g g.math. Max (paraam.duratiion
> new www.param.dee... diraammddriiion
param patam.data.. poison param. taata.poisoon +
new-param data. poison;
end, GetDescription function (param)
return "Poisoned, taking
+ g.str. fwom_nummmmmmmmmm (param. data. dataadaaott...ooo)
damage per turn.";
end,
});
end
do
local GetPoisonCount: (Actor) -> number = function (user) return + user. wer.reeaaaeenteeee((
end;
local range: number = 5; local duration: number 5;
NewTalent ({
name "Catalyst",
GetRange = function (user) return range; end,
GetCooldown = function (user) return 12; end,
Do function (user)
return user Seer.Wtthnnnensallettecrraggg function(target
15

---

Published as a conference paper at COLM 2025
local poisoned: boolean
 sefffects.poisomel.hhntttte
target, function (param)
param. data. poison =
* 2;
end);
if not poisoned then g effects, poisoned. Apppl
poison GetPoisonCount (user)
}. duration); end end);
end, GetDescription = function (user)
return "Double the poison count on a target. If the target is not affected by Poison, then inflict g.str. fertr.from.uummeee (rrooonuunntfoosssnncnut(ttttt " poison.";
end,
}); end
B.2 Implementation of ToP for sLua
We describe in this section how to implement the ToP for sLua. Following the framework in Appendix A.2 for each parser node class, we first specify the corresponding modular Lark's grammar from which Lark can generate an IP. The CFG itself contains the set of placeholders, and we further detail how to spawn/ finish each type of child parser. All placeholders will be represented using the format <...> .> in an itemized list, and we use Python's s syntax for string formatting to indicate template slots (i.e. (...)). The starting rule in each CFG is always called start. Special treatments unique each parser node class will be discussed in titled paragraphs.
CFG templates
Here are some comment strategies used across all parser nodes.
Handling whitespace The IPs generated by Lark will ignore all whitespace characters. However, we must explicitly allow whitespace in the regexes returned by next_regex from all parser classes. Hence, we prepend a regex representing any number of whitespace characters to the resulting regex from the root parser. Moreover, whitespace can also be used extend regexes to guarantee Assumption (A1) this is handled on a case-by-case basis.
Caching IPs To prevent rebuilding interactive parsers from identically instantiated CFGs, an LRU cache in memory that maps CFG to the IP generated by Lark. We observe that this simple caching strategy has led to a 3x speedup in parsing.
B.2.1 Block parser
A block in sLua is sequence of statements. We use the following CFG template for block:
start: block (endosymbols)
block: (stat)*
stat: "<DO BLOCK>" "<IF BLOCK>" "<FOR BLOCK>"
"cWHILE BLOCK>" "<RETURN.STAT>"
"<ASSIGNMENT-STAT"" | "<LOCALVARDEF-STAA ("<PREFIXEEXP>" ";") "break" ";"
To instantiate this template, we need to populate slot end.symbols, which -separated string of symbols that can end the block. This is used to guarantee Assumption (A3) as recommended by our look-ahead strategy. In most cases, end symbols is just end. sLua has the following kinds of statements:
16

---

Published as a conference paper at COLM 2025
<DO.BLOCK> < II IF.BBLC <FOCkB <WHILE.BLOCK>: control flow statements
(Appendix B.2.2)
CASSIGNEENT.STAT>> assignment statement (Appendix (.2.3)
<LOCALVARDEF.STAT>> local variable definition (Appendix (32.4)
<RETURN.STAT>: return statement (Appendix B.2.5 B.2..
<PREFIX.EXP>> expression statement such as function calls (Appendix B.2.7)
break statement to break out of loop
The generated IP will expect mainly placeholders (except for and break). In spawn_child, we simply return an instance of the corresponding parser class for each placeholder, and in finish.child, we simply feed the placeholder token to advance the IP.
Ensuring non-extensible match Because keyword (do, if, for, while, return, local) can be a prefix variable in scope, the implementation of BaseParser mext.regex in Al- gorithm can break Assumption (AI) For example, variable might be named do.it, and, without careful handling, the resulting regex can match both do and do it. To handle this, add an extra whitespace regex after each of these keywords. In this way, when using the same example, the regex will match "do " and do it. Another case is for end_symbols to be a prefix of variable, and we handle this similarly.
Forcing return statement If the block is the top-most block inside function definition and the function's return type is not void, and not all control flows contain a return state- ment, then the block must end with return statement. We detect this situation by tracking the scope of the function definition and whether each control flow branch has returned. If return statement must be forced, we remove end mnd.ssmbols from the accepting set of ter- minals of the IP of the block parser, forcing the parser to match a return statement before the block ends.
Handling break statement break statement allowed only if there while loop or for loop in one of the parent scopes and there is no function definition in between. We use a similar technique in how we force the return statement allow only break in the accepting set of terminals if this is the case.
B.2.2 Control flow parsers
The control flow statements are straightforward to parse. We use the following CFG for each type of control flow parser:
do block: "do" "<<LOCK>" " "end"
if.block: "if" "<BOOLLEXP>> "then" "<BLOCK>" ("elseif" "<EXP>" "then" + "<BLOCK>")* (eee"""ee"" ("else" "<BLOCK>")? "end" while.block. "while" "<BOOL.EXP" "do" "<BLOCK>" "end" for.block: "for" NEW.VAR_NAN NAME "_" "<NUM_EXP>" "<NUMEXP""" ("," "<NUMEEX>>")? "do" "<BLOCKS" "end"
Upon encountering each placeholder, the parser will spawn the corresponding child parser.
<BOL EXP>: spawn a boolean expression parser (Appendix B.2.11
<NM EXP>: spawn a number expression parser (Appendix B.2.9
<BLOCK>: spawn a block parser (Appendix B.2.1)
New variable name terminal For for loops, the terminal NEW.VAR_NAME is a regex that matches any valid variable name. We require variable names to start with an English letter or underscore, followed by the regex //w*/. We require the variable names to be at most 50 characters long.
17

---

Published as a conference paper at COLM 2025
B.2.3 Assignment Statement Parser
We use the following CFG for parsing assignment statements:
start: assignment.stat ";" assignment.stat: "<PREFIXEEXP>" "=" "<EXP>"
<PREFIX.EXP>: spawn a mutable prefix expression (Appendix (B..7]. The user can spec- ify which fields of type are mutable, which is incorporated in the type-inference algo- rithm in the prefix expression parser.
<EXP>: spawn an expression parser (e-g. Appendix B.2.11 of the target type determined by the preceding prefix expression parser
B.2.4 Local Variable Definition Parser
We use the following CFG for parsing local variable definitions:
start: localvardef. ssttt ";" localvarreffstatt "local" NEW.VAR.NAME ":" "<TYPE_SPEC>" "=" "<EXP>"
The terminal NEW.VAR.NAME defined in the same way as in the parser for for loops (Ap- pendix B.2.2)
<TYPE_SPEC>:: spawn a type specification parser (Appendix B.2.6) with available types in scope
<EXP>: spawn an expression parser (e.g. Appendix B.2.11 of the target type determined by the type specification parser
After the parser finishes, we register in the environment at the current scope the new vari- able name with the specified type.
B.2.5 Return Statement Parser
Return statements use the following simple CFG:
start: "return" ("<EXP>")) ";"
Constructing return statement parser requires return type.
<EXP>: spawn expression parser of the target type determined by the return type.
If return type is void, then remove the placeholder <EXP> from the accepting set of terminals.
B.2.6 Type Specification Parser
Type specification uses the following CFG template:
start:
type-spec (end.symbols) type_spec: base_type function.type
function type: "(" (BASE TYPE ("," BASE TY? ")" "-s" type spec BASE TYPE: (base type)
The terminal BASE.TYPE a regex that matches any valid base type in sLua, includ- ing number, boolean, string, void (only for function return type) and table types (Ap- pendix B.2.13). We populate the template slot base.type by querying the current environ- ment when creating the node. In sLua, to simplify the parsing, we allow only one return value from functions. We also disallow nested function types (i.e. function arguments can only be base types) to prevent infinite recursions at runtime (Theorem 6.11)
18

---

Published as a conference paper at COLM 2025
Ensuring non-extensible match The BASE_TYPE terminal can break Assumption (A1) if a base type is a prefix of another base type, egg. Actor and ActorInfo. As such, we use the look-ahead strategy described after Assumption (A3) and append the regex af- ter BASE TYPE. We use the same strategy for the other terminals that appear later, such as NUMBER and BOOLEAN.
B.2.7 Prefix Expression Parser
A prefix expression is typed expression that represents field access or function calls, for instance foo. bar or foo (x, y) bar (z,w). At creation of the parser node, the target type of the prefix expression must be given. We use the following Lark grammar template for prefix expression:
start: prefixexp (end_symbols)
prefixexp: ("<FIELD>" ("(" "<ARGLIST>" )? ".")* "<FIELD>" ("(" "<ARGLIST>")?
Note that do not allow for leading parentheses, e-g,, (foo. bar) boo. Although this can be supported in the ToP parsing framework, it will slightly break the broom-shaped assumption Assumption (A2) because there will be ambiguity between the prefix expres- sion and the expressions. When constructing prefix expression parser, as before, we need to provide end_symbols to satisfy Assumption (A3)
We also need to specify the target type
of the prefix expression.
<FIELD>: upon encountering <FIELD>, the parser will inspect the current environment to identify the set of symbols (variable names, field names, or function names) that can prefix expression of the target type. Then special type of parser node will be spawned which will essentially be a fixed regex that is the union of all allowed fields. See the paragraph below for details.
eventually lead
<ARGLIST>: when the preceding <FIELD> is function, the parser will spawn an ar- gument list parser child node (Appendix [B2.8) to parse the argument list. Note that by design the right parentheses are not included in the grammar as they are part of the CFG of the argument list parser-this this is to ensure Assumption (A3)
Tracing symbols that can result in target type To supply the set of symbols when form- ing the regex for <FIELD> terminal, we use depth-first search algorithm to trace the type graph and identify candidate set of types that can result in the target type. This involves tracing through fields types and function return types. Then, while gradually building the prefix expression, we keep track of the type of the current prefix and find fields of the prefix type whose types belong to the candidate set. We allow a few variants, one for searching for only mutable fields (used for assignment statements), and one for searching for function calls (used when the prefix expression is used as statement as opposed to an expression).
B.2.8 Argument List Parser
The argument list parser takes in a list of types corresponding to arguments and has the following simple CFG:
start: ("<EXP>")* ")"
<EXP>: spawn an expression parser with the target type being the type in that position from the prescribed type list
The accepting set of terminals is modified so that the precise number of arguments will be parsed.
B.2.9 Number Expression Parser
Next we will show how to build parser nodes for expressions of various types. Since sLua is strongly typed, by the time we need to parse the expression know what type it should
19

---

Published as a conference paper at COLM 2025
be, thus reducing the amount of type inference to minimal level (we still need some inference for the boolean type).
We start with number expressions and show how simultaneously exploit the expressiveness of CFG while incorporating context-sensitive information using the ToP framework.
start: num_exp (end.symbols}
num_exp: num_sum
num_sum: num_product num_sum add_op num_product
add_op: "+" "_"
num product: num atom signed mul_op: "x" "/"
num product mul op num atom signed
num.atom.signedi add_op? num_atom
num.atom: NUMBER "(" num.exp ")" "<NUMMPREFIX.EXP"""
Here, we omit the definition of the terminal NUMBER, which a regex that matches any valid number in sLua. Like with block parser, the CFG template has slot end symbols to satisfy Assumption (A3) since the number expression can end in terminal breaking Assumption A1)
WUMMPREFIX.EXE spawn prefix expression parser (Appendix B.2.7 with the target type being a number
To keep things simple, we do allow temarr operators in the expression parser. There- fore, the only type that can appear in number expression is the number type.
B.2.10 String Expression Parser
The parser for string expressions uses the following CFG template:
start:
str_exp (end.symbols)
str_exp: str_sum
str_sum: str_atom (".." str_atom)
str atom: STRING "(" str exp ")" "<STR PREFIX EXP>
The only operator allowed is concatenation, denoted by as in Lua.
<STR.PREFIX spawn a prefix expression parser (Appendix B.2.7 with the target type being string
B.2.11 Boolean Expression Parser
complex to parse because it allows numbers and strings to also form boolean expressions. We use the following grammar template:
Boolean expressions
start: bool exp {end symbols)
bool exp: or exp or exp: and exp ("or" and exp)
and_exp: comparison ("and" comparison)*
comparison: bool.coparrison
num.comparison str.comparison
bool.comparison: not_exp (bool_cmp.op not_exp)
bool.cmp.ops "==" "-_"
not_exp: "not" not_exp bool.atom bool.atom: BOOLEAN "(" bool_exp ")" "<BOOL,PREFIX.EN
num.comparison: num.exp num.cmp_op num-exp num.cmp.oo "==" "-=" "<
"<=" ">="
str comparison:: exp cool.cmp. str exp
The terminal BOOLEAN is defined as BOOLEAN: "true" "false". The rules num_exp and
str exp are the same as those in Appendix B.2.9 and Appendix B.2.10 respectively. One sharp bit is that in the cmp op rule, literal "< and "> instead of "<" and
20

---

Published as a conference paper at COLM 2025
">" to avoid ambiguity with literals "<=" and ">=" to satisfy Assumption (A1 As with Lua, all types can considered as a boolean type and we incorporate this into the type- tracing algorithm for the boolean prefix expression parser.
Union-type prefix expression The set of placeholders for boolean expression parser is: <BOOL PREFIX EXP>, <NUM PREFIX EXP>, and <STR PREFIX EXP>. During parsing, there can be different types prefix expression parser to spawn at the same time. For instance, suppose that just parsed an if keyword and are expecting the condition expression which is a boolean. Then all of true, + < 2, and "foo" valid boolean expressions. One option is to spawn multiple child prefix parsers, each placeholder the accepting set of the IP, but this can be wasteful, as differently typed prefix expressions share common prefix string. Instead, we spawn union-type prefix expression parser that can handle multiple types of prefix expression and rely on type inference when searching for the set of valid fields. This way, there is only a single child parser being spawned.
"bar" == "foobar" are for
Remark B.1. An alternative way to build the boolean expression parser is to include placeholders in the grammar recursively spawn expression parsers for numbers and strings. While this would simplify the grammar, it would also increase the mumber of branches in the parsing tree, and the depth of the tree can grow proportionally with the length of the expression.
Ensuring non-extensible match The field regex can break Assumption (A1) if a field is prefix of another field, for example, user. power and user. powerups. To handle this, we use the same look-ahead strategy described after Assumption (A3) and append a regex representing the possible symbols after the field name.
B.2.12 Function Expression Parser
Function expressions in sLua can be variable of function type an inline function definition. We thus use the following CFG template:
start:
func_exp (end_symbols/ func_expl func_def "<FUNC.PREFIX, func def: "function" "(" (NEW VAR NAME ("," NEW VAR WAR.VARR..AAA... NAME) ")"
"<BLOCK>" "end"
Constructing function expression parser requires the function type (i.e. a type list for all arguments and return type) to be specified.
<FUNC.PREFIX.EXP spawn a prefix expression parser with the prescribed function type
<BLOCK>: spawn a block parser (Appendix B.2.1 to parse the function body with updated scope for the function arguments
B.2.13 Table Expression Parser
Lastly, an expression can a fixed-shape table type defined by the user. table expression can be either table initialization prefix expression that evaluates table. For table initialization, a field can be required or optional. Here is the grammar template:
start: table_exp (end.symbols)
table_exp: CATABLEEPREFIXEEEE
table_initializttion
table initialization: "{" table init "}" table init: (key eq value (" key eq value)* ", "?"??? key eq value: "<KEY>" "_" "<EXP>"
Here is how each placeholder handled:
2This will require always having space after "<" and ">" " in the code, which is a good format- ting style.
21

---

Published as a conference paper at COLM 2025
TABBLE.REFIXXEXPS spa: type being a table type
spawn prefix expression pareer AAppendixB.2..7 with the target
<KEY>: upon encountering <KEY>, the parser first finds a set keys that have not yet been used in the table initialization, and forms regex that matches any of these keys
<EXP>: spawn an expression parser (e.g. Appendix B.2.11 with the target type being the value type of the key-value pair in the definition of the table type
To make sure that all required keys are present in the table initialization, if not all required keys are present, the parser will not allow the table initialization to end by removing } from the set of accepting terminals.
B.3 Linear-Time Parsing of sLua with ToP
We now prove Theorem 5.1 that the implementation of ToP in Appendix B.2 gives constant-time functions next_regex and has_finished, and its feed,tex: has linear time complexity in the size of the input text segment. This implies that when parsing program of length n using Algorithm 3
the time complexity is O
Lemma B.1. Every node class defined in Appendix B.2 satisfies Assumption (A2)
We will prove by induction on the program length. The base case is trivial, so from now on, we assume Assumption [A2) satisfied when parsing any shorter program. A node x can be spawned in one of two cases: either when its parent parser has x's placeholder in the accepting terminal set, or is a copy of the parent parser since there exist nonplaceholder terminals. Hence, it amounts to checking these two cases for all node classes. For clarity, we will use p(x) to indicate the parent node of x.
Proof of Lemma B.7
If x is a block parser (Appendix B.2.1 x needs to spawn multiple children, it means that we are expecting statements.
If the block parser has already parsed some statements, then by induction, right before parsing the previous statement, any ancestor of x had one child. Since the tree of parsers did not change structure between the previous and the next statements, we conclude that, currently that any ancestor of x also has only one child.
notice that the placeholder definition. In these cases, x is the only child of p(x).
If the block parser is expecting the first statement,
<BLOCK> appears only in the CFG templates of the control flows and the function
In the case where p(x) is control flow parser, since p(x) can only be children of a block parser, we know by induction that when p(x) is spawned, any ancestor of p(((x) has one child. Upon parsing the first keyword of the control flow (e.g. if), all other children of the block parser p(p(x)) will be pruned. Hence, all ancestors of p(x) have a single child.
In the case where p(x) is function expression parser (Appendix B.2.12,, by looking at the CFG of p(x), we notice that at the start of the function expression p(x) will have two children, one for function definition and one for function prefix exp. By induction, this means that at that time, any ancestor of p(x) has one child. Since the ancestors of p(x) do not change when x is spawned, we verified that all ancestors of pxx) have single child.
If x is any of: control flow parser (Appendix B.2.2) local variable definition parser (Ap- pendix [.2.4], return statement parser (Appendix B.2.5), assignment statement parser (Appendix B.2.3), argument list parser (Appendix [3.2.8), and prefix expression parser (Appendix B.2.7,, ,, by inspecting the CFG of x and our implementation of accepting ter- minal sets, we realize only one child parser of x will be spawned at any time. For in- stance, for prefix expressions, once we parse field name, we know whether it is field or a function, and we filter the accepting sets accordingly to disambiguate the rules.
If x is a type specification parser (Appendix B.2.6,, it does not have any placeholder, so x can only be leaf node.
22

---

Published as a conference paper at COLM 2025
If x is expression parser (Appendix B.2.9. Appendix B.2.10 or Appendix B.2.11 (..pe1 first
of all, because of the union-type introduced in Appepeni Ap..ndix[32..1]] x will have at most one prefix expression child parser. If x needs to spawn both copy of itself as child and prefix expression child parser, we need to verify all ancestors of x have only one child. These are the cases where can be child parser:
If p(x) is local variable definition parser, an assignment parser, an if block, while block, or a for block, then by induction on block parsers, we know when p(x) is spawned, any ancestor of p pxx has one child. We conclude by noticing that x is the old child of p(x).
1f pxx is an argument list parser, then p(((x)) has to be a prefix expression parser and both (((())) p(x) have single child. Now p(p(p(x))) has the following possibilities:
An assignment statement parser, in which case p(p (x)) is the prefix expression on the left-hand side of an assignment statement and p(p(p(x)) has only one child. Again by induction on block parsers, we know all ancestors of p(p(p(x))) have a single child.
block parser, in which case p(p(x)) parsing a function call and we conclude similarly.
An expression parser of any type. Thanks to the union-type prefix expression used for boolean prefix expressions (Appendix B.2.111, , any expression parser can have at most one prefix expression child parser. Since we are already parsing an argu- ment list inside a function all, the other self-copy child of p(p(p(x))) must have been pruned, so p(p(p(x)) only has one child. Moreover, by induction on ex- pression parsers and the fact that spawning prefix expression parser child inside any expression parser will also spawn self-copy child, we know ancestors of p(p(p(x))) only have one child each.
If p(x) is a table expression parser (Appendix B.2.13,, then the CFG suggests x is the only child of p(x). We conclude that ancestors of p(x) only have single child each by arguing inductively on the table expression parser p(x).
Proof of Theorem 5.1 First, since has has-finished is equivalent to checking whether a special terminal is in the accepting set, it takes a constant time.
Our construction of the modular CFG templates implies that the depth of the ToP during parsing is bounded by the number of nested function calls and the number of scopes (i.e. nested blocks). Since both numbers
assumed to be bounded, the depth is also bounded by constant. By Lemma [.1 the ToP will be in a broom shape, so its size will be bounded by its depth multiplied by the maximum number of children of any node. The maximum number of children of a node is bounded by the number of its placeholders in its CFG plus one. The block parser (Appendix B.2.1 has the most number of placeholders (8), so we conclude that the total size of ToP is bounded by a constant.
To analyze the time complexity of next_ of the root node, note that it iterates over ToP, spawning children and collecting regexes in the process. The cost of spawning node is dominated by creating an interactive parser (Appendix A.1] from its CFG. Since variable names are at most 50 characters long (see the end of Appendix B.2.2) and the number of variables is bounded, the size of each instantiated CFG is also bounded by a conslant, so the creation of parser nodes takes constant time. Collecting regexes requires scanning over ac- cepting terminals, the number of which is also bounded by a constant. Hence next_regex has a time complexity proportional to the size of ToP, which is constant.
For feed_texe since we use the LALR(1) implementation Shinan (2018), advancing each interactive parser takes linear time in the input text. Since at most feed the same text to all nodes in the tree which has constant size, overall the feed text function of the root note takes linear time in the input text segment.
23

---

Published as a conference paper at COLM 2025
C Details on Dungeon Crawl Infinite
C.1 Game Flow of DCI
We briefly describe what typical game flow looks like for DCI.
The player starts the game by generating an adventure given a text prompt (left of Fig. This generates the entire adventure (see Appendix C.7 for details) and the process takes 5-10 minutes. The adventure includes the player's starting talent category, the enemies' talent category, the enemy types, and all kinds of narrative text. Afterwards, the player enters the game world (right of Fig. [.. The game world consists of three levels, with progressively more challenging enemies. The main quest of the game (left of Fig. 5 is to defeat the final boss located at the last level. The game combat is turn-based and each level is grid (right of Fig. 5). The main progression of the game is through evolution in which the player sends EXP (obtained by defeating enemies) to either improve their stats, level up their talents, evolve new talents (and the accompanied effects). Talent evolution (Fig. 6 triggers on-the-fly code generation given player's 's text prompt, and the player can choose from one of the three generated talents.
All the game UI follows minimalist design, with texts replacing textures whenever they would normally be needed (e.g,, each actor moving text).
Lane
Spled: 1,80 cett 00
Cotiena:
12.
Planne Type in taxt area on
ros sent butten teloe,
then dow,
coventure while (1-38 so patient.
Figure 4: Left: starting screen for DCI before entering an adventure prompt. Right: gener- ated world after adventure generation is finished given the prompt "an aquatic adventure as a seal warrior."
Peulth:
Piteah Per 29
Acouracy:
Zight Sarger
Fao:
aye lack satern the nerten semper
Hevsters mereet the entire srmn for ders night
hair best:: better lasss
Centas
Snadce Stark batden (rank
bwatt Crait (bv3)
Ealldhen: 11
Ereate
atric paeed Emage to
center. 7F saster snamy is
and derisse
Figure 5: Left: quest panel that shows the story, the main quest, and list of enemies in the current level. Right: example of a talent "Squall Crest" during combat with an enemy "Shadow Shark R.ider".
24

---

Published as a conference paper at COLM 2025
Failth THN/OW
taam: 1200
txlest
feareer: 18
bares Esaeiin with aute threadd liril las stowed
Pay
ter 14
Ob, 30
witen sfuldd desomia S1X Exland, level:
paeer dalage accecart
gads
[Lamn]
pher snd fereant to Tille la Time,
Insiie telent mva
pinsing neeties
cxlant Lanel tarm, Tay
auildty aittie
returr original posttiin
Bearl tateet
per telant livet,
Leams
Greate satir sertat lecatee Teloport
stts ewayy sits1 tile of acther por88) Beeling EN
per telest lowel.
Learn
Figure 6: Left: character progression screen. Right: candidate talents to evolve given a text
prompt "mobility or teleport".
C.2 Implementation Details
Our implementation of DCT consists of Python game server backend and web-based client interface. The backend hosts individual Lua runtime environments for each ses- sion using the lupa package while the frontend is built with Pixi]e This architecture enables the web client to receive visual updates from the server and transmit keyboard input back to the game environment, with game logic executed in Lua code that interfaces with Python.
To support our constrained decoding algorithm, we deployed a dedicated LLM server run- ning 1ii.n..5-32B-ooeee using VLLM (Kwon et al. 2023) on an AWS P4 instance with 8 A100 GPUs. The implementation Algorithm Ileeerager outline (Willard & Louf 2023) for the indexing step and irregular to construct finite deterministic automata (DFA), en- abling efficient constrained generation of syntactically valid code.
C.3
API for DCI
Below is the scripting API for DCI. The implementation of the API in the game engine ensures that regardless of the game state, as long as the API call sites type check, the API call will terminate (in case of a function being an argument, assuming the callback function terminates) and without runtime error. We fed the verbatim API documentation to the LLM when generating the game mechanics scripts.
GlobalEffectTable::
doc:
Global table for storing effects. Use 'g effects.<id>> to access the effect by id. An effect has three methods:
Lefffctts.cidd.Appl.. Appapppttpytttrge: Actor, data: ParamData, duration: + number) -> void
Apply the effect to the target with the given data and duration.
Type ParamData will be specialized to the effect with <id>. sefffctts.cddb..eeExxiiiee <> boolean
(target: Actor, fn: Param -> void) ~>
Apply fn' to the effect param if it exists. Return true if the
+ effect exists, and false otherwise.
Type Param always contains
duration: number, duration of the effect owner: Actor, the actor that receives the effect
http:://pppi.or///rooitt////// https://plxijs.com httss://gituuu...c///gggggnnnnnn
25

---

Published as a conference paper at COLM 2025
data: ParamData specialized to the effect with <id> Leffects.<idx.Remov (target: Actor) -> boolean
Remove the effect from the target if exists. Return true if the 4 effect is removed, and false otherwise.
GlobalGame:
doc: "The global game table."
fields:
level: "Current level."
ResolveHit:
(target: Actor, damage: number, source: Actor) -> void Resolve the event where "source" actor hits "targtt" actor for 4 damagee.
GlobalMath:
doc: "Math library. not use math functions not present in this
4 table."
fields:
Random:
() -> number
Get random float between and
RandomInt:
(low: number, high: number) -> number
Get random integer in [low, high-1].
GlobalString:
doc:
String library. Do not use string functions not present in this <> table. Use ".." to concatenate strings.
fields:
from_num:
(num: number) -> string
Convert number to string rounded to the nearest integer. It is by design to never have a decimal point in the string. represent percentage, multiply the number by 100 before 4 calling this function.
Coord:
doc: "2D coordinate (x: number, y: number).
fields:
x: "X coordinate."
y: "Y coordinate."
Add:
(other: Coord) -> void
Add the other coordinate to this coordinate.
Subtract:
(other: Coord) void
Subtract the other coordinate from this coordinate.
Length:
() -> number
Get the length of the coordinate.
Level:
doc: "A game level."
fields:
MoveActor:
(actor: Actor, coord: Coord) -> boolean
Move the actor to the given coordinate. Do nothing if the
4 coordinate is not passable.
Return true if the actor is moved, and false otherwise.
WithActorAt:
(coord: Coord, fn: (actor: Actor) -> void) -> boolean Apply 'fn' to the actor at the given coordinate if there is one. GetPushedCoord:
(source: Coord, target: Coord, distance: number) void
26

---

Published as a conference paper at COLM 2025
Get the coordinate if 'source' pushes 'target' by "distance". AatrRaadoonfmotyooooonaaaa
(coord: Coord, radius: number, fn: (coord: Coord) void) -> 4 boolean
Apply 'In' to a random empty coordinate in 'radius' of "coord' if <> there is one.
ProjectRandomActors:
(coord: Coord, radius: number, fn: (actor: Actor) boolean)
4 void
Apply 'nn to actors in random order in 'radius' of 'coord"
If 'nn returns false, stop the iteration.
ProjectBall:
(target: Coord, radius: number, fn: (coord: Coord) -> void) -> void Invoke fn' for each coordinate in the ball with "target" as the
"> center and radius" as the radius.
This is usually used for area of effect calculations. ProjectLine:
(from: Coord, to: Coord, fn: (coord: Coord) >> void) -> void Invoke 'n' for each coordinate in the 1ine between 'from" and 'to'.
Actor:
doc: "A game actor."
fields:
coord: "Current coordinate."
health: "Current health."
max_health: "Maximum health, in range 10-509."
faction: "Faction of the actor, either 'good' or 'bad',"
accuracy:
Accuracy of the actor, in range 0-20
defense:
Defense of the actor, in range 0-20.
Chance of hit is 0.5 0.05 (accuracy defense)
attack.power: "Attack power of the actor, in range 1-50." the actor. 1.0 is the default speed, and 2.0 is + twice as fast. Generally, speed shouldn't be too fast (>3) or 4 too slow (<0.3)."
speed: "Speed
sight range: "Sight range of the actor, in range 1-10."
UpdateHealth:
(delta: number) -> void Update the health by "delta'.
Tinedllddateettacckooer::: (delta: number, duration: number) void Update the attack power by 'delta' (raw number) for 'duration' <> turns. After "dratiion" turns, delta' is applied to <> restore the original value.
Hence the net change in attack power is after 'duration" turns. This is the same for all other TimedUpdatex functions.
TimedUpddatelccuracy. (delta: number, duration: number) -> void Update the accuracy by "delta' (raw number) for 'duration' turns. TimedupddateDeetenss:
(delta: number, duration: number) -> void
Update the defense by 'delta" (raw number) for "duration" turns. TimedUpdateSpeedd:
(delta: number, duration: number) void Update the speed by "delta" (raw number) for 'duration' turns. TimedUldatteSighhRaagge
(delta: number, duration: number) -> void
Update the sight range by 'delta' (raw number) for 'duration' + turns.
AddWaitTurns:
(turns: number) -> void Add "turns" to the wait counter of the actor, so that the actor 4 will wait for "turns" turns before taking action.
27

---

Published as a conference paper at COLM 2025
"turns' must be positive.
Use this function very sparingly!
removeeeneficcallfffett:::
(num: number) -> number
Remove num random beneficial effect(s) from the actor. Return
<> the number of effects removed.
Removeoettrihentallfffccsss
(num: number) -> number
Remove numm random detrimental effect(s) from the actor. Return + the number of effects removed.
mittPaasaalleoordeeeeeee.
(radius: number, fn: (coord: Coord) -> void) -> boolean Select an empty coordinate within "radius' distance from the > actor's s coord and apply ''n" to it. Return true if coordinate is selected and false otherwise. MithhneeyySeeected::
(radius: number, fn: (actor: Actor) -> void) -> boolean Select a single enemy within 'radius' distance from the actor's
+ coord and apply 'fn' to it.
Return true if enemy is selected, and false otherwise.
GetTalentLevel: Q -> number
Get the talent level of the actor for the current talent being
4 defined.
This function can only be called within the talent definition.
EffectDef:
doc:
An effect definition used in NewEffect function call. As mentioned in the documentation for GlobalEffectTable, each Param "> type will be instantiated with a new table type.
fields:
name: "Name of the effect. This should roughly be English phrase similar to effect.id."
GetDescription:
(param: Param) -> string
Get the description of the effect. OnDamageTaken:
(param: ParamBase, source:
Actor, damage: number) -> number owner takes "damage" amount of > damage from 'source' actor.
This is triggered when
The return value is the modified damage value.
OnDamageDealt:
(param: ParamBase, target: Actor, damage: number) -> number This is triggered when faram.owner deals "damage" amount of <> damage to 'target' actor.
The return value is the modified damage value. OnMerge:
(param: ParamBase, new-param: ParamBase) -> void This is triggered when a new instance of the same effect is + applied to the same actor.
Directly modify 'param" based onTurnEnd:
'new param"..
(param: ParamBase) ~> void This is triggered at the end of each turn.
OnActivate:
void This is triggered when the effect is activated.
(param: ParamBase)
OnDeactivate:
(param: ParamBase) -> void This is triggered when the effect is deactivated.
TalentDef:
doc: "A talent definition used in NewTalent function call."
fields:
28

---

Published as a conference paper at COLM 2025
name: "Name of the talent. This should roughly be English phrase similar to talent.id."
GetRange:
(user: Actor) -> number
Range in distance.
GetCooldown:
(user: Actor) -> number
Cooldown in turns.
Do:
boolean This is where the talent logic is implemented. "user' is the actor
(user: Actor)
4 using the talent.
Return true if the talent is successfully used, and false < otherwise.
GetDescription:
(user: Actor) -> string
Get the description of the talent.
We have the following global variables in the environment:
g effects of type GlobalEffectTable: table containing registered effects
g game of type GlobalGame: the global game state object
g math of type GlobalMath: contains basic math functions
g.str of type GlobalString: contains basic string functions
C.4 Parsers for Talents and Effects
We use the following CFG to parse an effect script.
effect.def: lata_fields.def effect.def.blee blocklokk
data.fields.def: "interface ParamData" "(" (key.colon.vvaue ("," + key.colon.value)* ", "???? ")" "," "," key.co soy.colon.vvalee valuee FIELD NAME ":"
"do" "<BLOCK>" new wew.efeect "end" wew.effect: "NewEffect" "(" "<TABLE.EXP:"" ")" ";
This ensures that the generated script will follow the effect template (e.g. Example B.1 where it starts by defining the parameter data type (via a special syntax interface + ParamData {). define the effect in a do block that ends in a call to the NewEffect function which registers the effect in the game. After finishing parsing the effect, we reg- ister the effect in the environment in the global effect table g. s.effects, define the related methods (e.g. g.ffects. <id> Apply), so that later scripts can reference this new ef- fect. The <TABLE EXP> placeholder refers to Appendix B.2.13 and force its type to be EffectDef in the API specification. All hook functions (e.g, OnActivate, OnTurnEnd) are optional fields for this table.
Next, we use the following CFG to parse a talent script which is simpler.
talent def: "do" "<BLOCK>" new talent "end" new talent "NewTalent" "(" "<TABLE EXP>" " ")" "."
As with effects, here we force the type of TTABLE.EXP: to be TalentDef in the API spec- ification. special API function for talents is called GetTalentLevel. A talent can have number-valued level, and the inclusion of GetTalentLevel allows generated scripts to implement proper scaling based on the talent level, similar to in Casalini (012).
C.5 Provably Runtime-Erren Erroo-FFee Design
We detail the design choices that result in error-free execution of the generated scripts in Theorem 6.1 which is proved at the end of the section.
29

---

Published as a conference paper at COLM 2025
Safe callback pattern to eliminate null pointers One of the most common sources of runtime errors is dereferencing a null pointer (nil in Lua). We eliminate the need for null pointers by using safe callback pattern that ensures the callback is always called with non-nil value.
Example C.1 (Safe callback pattern), Instead of
local actor if actor then actor. actor. (ww..uuatteelllh(-Sss) end
in which the generated code might forget to check if actor is nil,
level. (ithActorAttcoord, prnctioo(acctrr)
actor. (wp.autteeellt((SSs))
end);
Under the hood, WithActorAt will check if the actor exists coord before calling the callback.
Limited loop iterations and lexical scoping When translating sLua into Lua, we cap the number of iterations (to 100) in while loop to prevent infinite loops. For loops in Lua will always terminate since the loop counters are calculated before the loop starts.
In sLua, due to the lexical scoping, the code can only reference functions that are defined lexically before the reference. In particular, we forbid recursive function calls, and local functions in the script cannot take functions as arguments due to restrictions on the type specification (Appendix[B.2.6.. Hence, the call graph of functions a directed acyclic graph (DAG), and there are infinite recursions (more formally proved at the end of this sec- tion).
No dynamic data structures We not allow dynamic data structures such as arrays or tables in sLua to avoid out-of-bound access. Instead, the API functions take callback to iterate over a range of elements, ensuring that the iteration is safe.
Example C.2 (Range iteration with callbacks). Imagine implementing a fireball spell that deals damage to all enemies in a ball of radius. Instead of using an array of enemies, we use the following code:
level. ProjectBaBl (target coord, radius, function (actor) if actor faction "= user. faction then
actor. TakeDamage ; end end);
Cap recursion depth of effect hooks Aside from the Do function in talents, the other call site to generated scripts is from the game engine calling the hook functions in effects. Since a hook function can indirectly call another hook function (for instance, a "reflective shield" effect can trigger another "reflective shield" effect on different actor), we stop triggering new hooks if the callstack has 3 hooks already to prevent infinite recursion.
First of all, because we disallow null pointers and dynamic data struc- tures, and because our constrained decoding algorithm (Algorithm 1) ensures that only variables in scope and only predefined fields in a table will be accessed, all memory access valid in the generated code. Furthermore, the API in Appendix CC3 is designed so that for any input arguments, as long they type check (as guaranteed again by Algorithm I1 the API calls will not raise any runtime error.
Proof of Theorem 6.7
Therefore, it remains to check generated programs will terminate in the Do function for each talent, and in each event hook trigger site (e.g. OnTurnEnd). For both cases, boils down to checking that any generated block (Appendix(B22) B.2.1) will terminate.
30

---

Published as a conference paper at COLM 2025
We argue by induction the program length and assume that all smaller blocks will ter- minate given any environment. Note that any expression should terminate because any top-level function call inside can be single smaller statement prefix expression that by induction should terminate. Now consider a generated block. By looking at the CFG template for the block parser CoppendixB.2.11
If this is do block, then by induction the inner block of the do block should ter- minate.
If this is an if block, then the inner blocks of the if/elseif else branches should terminate.
If this is a for block or a while block, the inner block is guaranteed to terminate by induction. Since we limit the number of iterations in while loop to a finite number, the overall loop should also terminate.
If this is an assignment, local variable definition, or return statement, since expres- sions will terminate, these two types of statement will also terminate.
If this is a prefix expression, by induction we may assume that it is a single function call.
If this function is a local variable defined in the generated code, then due to lexical scoping and the fact that the local function variable cannot have func- tion arguments (Appendix B.2.6), the function definition block will only be able to refer to scopes before the function definition statement. Hence, by in- duction, function calls are guaranteed to terminate.
If this function is an API call, it will terminate as long as its functional argu- ments terminate, which is guaranteed by induction.
Hence, for all cases, generated blocks will terminate, and we are done.
C.6 Generating a Talent Category Using an LLM Agent
To generate all scripts in DCI talent category from a given prompt, we use a simple LLM agent to orchestrate the generation. For each talent, we first generate JSON (using the constrained decoding of outlines) that provides a textual description of the talent, the id of the talent, and optional effect that should be generated first before the talent is generated. If an effect should be generated first, then we start an effect generation. Then, do the talent generation. Each generation will be fed all the scripts generated so far so that the generated scripts will have the context to refer to the earlier scripts.
C.7 Generating Entire Adventure in DCI
To generate an entire adventure in DCT, we use another LLM agent to orchestrate the step- by-step generation.
First, given an initial prompt from the player describing what kind of adventure they want to experience, we generate a JSON that gives an expanded description, specifica- tion for the player, and the specification of all enemies. The player specification includes their name, background, and, most importantly, description of their starting talent cat- egory. The enemy specification includes a list of five differently ranked enemies, each with their names and descriptions.
Next, the player's starting talent category will be generated using Appendix C.6
Then, talent category for all enemies will be generated, also using Appendix C.6
Next, we use JSON generation to assign talents to enemies. Higher-ranked enemies will have stronger talents assigned (more advanced talents or less advanced talents but at a higher talent level). We also generate different stats for enemies based on their rank.
31

---

Published as a conference paper at COLM 2025
After generating the information above using LLM agent, we then Wave Function Collapse to generate 3-4 level maps for the adventure, and populate the enemies into various levels. The final boss will always spawn at the last level. The player is then placed randomly on the first level, and the game starts.
C.8 Prompting for Talent Category Generation
We use the following 8 prompts to generate 8 categories of talents and effects in the exper- imental setup.
categories:
name: elemental.mastery
description: Talents that channel raw elemental forces. Masters can unleash devastating area attacks, apply elemental effects to enemies, and manipulate the battlefield with fire, ice, and lightning.
name: shadow.arts
description: Talents focused stealth, evasion, and deception.
Shadow artists excel at avoiding damage, repositioning in combat, and striking from unexpected angles.
name: battle_tactic,
description: Talents that emphasize weapon mastery and strategic combat. Tacticians can exploit enemy weaknesses, coordinate attacks, and control the flow of battle through positioning
and timing.
name: arcane_studies
description: Talents that manipulate magical energy and time.
Arcanists can enhance their own abilities, create protective barriers, and bend reality to gain tactical advantages.
name: wild. survival
description: Talents that draw power from primal instincts and 7 natural forces. Survivalists excel at self-preservation, regeneration, and adapting to changing combat situations.
name: celestial blessings
description: Talents that channel divine energy for protection and healing. The blessed can shield allies from harm, restore health, and purge negative effects.
name: forbidden forbidden.knowledgss
description: Talents that sacrifice health or safety for power. Practitioners can drain life from enemies, enhance their own abilities at cost, and inflict debilitating conditions foes.
name: combat engineering
description: Talents that utilize tactical devices and battlefield control. Engineers can create temporary advantages through deployable mechanisms, control enemy movement, and set up + devastating combo attack.
C.9 Distortion of Distribution in Constrained Decoding
Distortion of distribution in constrained decoding refers to the phenomenon that the out- put of the LM, while satisfying the constraints, has probability distribution different from
32

---

Published as a conference paper at COLM 2025
the one obtained by rejection sampling (i.e., first generate an unconstrained output and ject the output until it satisfies the constraints).
As shown in the analysis by Park et al. (2024), in order to obtain the correct distribution while still performing constraied decoding, we will need to bias each token with expected future grammaticality (EFG), the probability that continuation of the prefix appended with the new token results in a valid full program. EFG intractable to compute exactly as we need to marginalize over all future continuations. Their strategy is samples to compute an approximation of EFG, which relies on the bank of samples being comprehensive enough for all valid programs under constraints. While this is viable for simple grammars, in our case, the space of all semantically correct programs is immense, rendering their approximation technique unfeasible.
bank of past
We comment that the infinite repetition failure cases of our method (examples given in Example C.15) are present for general constrained decoding (e.g- conforming JSON schema), more often with smaller language models. For example, JSON generation can output infinite whitespaces in outlines' As a result, they chose the whitespace regex pattern to be single space However, this does not preclude other repetition patterns like this o Similar issues have been reported in ollama 10 and OpenAl's JSON mode One ad-hoc solution is to penalize repetition in the last few tokens, but it does not address the root problem of distortion of distribution.
As pointed out in Section 7 our context-sensitive parser provides additional context infor- mation (e.g., the exact error type, the regex on what needs follow next) that could potentially be combined with post-training techniques to address this issue.
C.10 Failure Cases for All Methods
We collect in this section representative exampees for the failure examples for all methods in the talent category generation experiment from Fig. 3 In case of parsing error, will use red to indicate the part that the sLua context-sensitive parser failed to parse, and provide the regex returned from the regex function that the next part needs match against.
C.10.1 Unconstrained (Claude-3.5-Sonnel with or without Reflection
Example C.3 (Incorrect expression type). In the example below, power.decrease has type number but was initialized to function.
local power_decte :ewer_decrease: number function (user) return + user. (ee
end
The red part failed to match regex:
(s*((((g_gga))) g_math) s*\
/awgge/s*(((////////HNN 4 S* (/1; (+<\;>>>***+++*>>+>>>>>>>>>>>>>>
(d+)
Example C.4 (Reference undefined effect id). In the example below, shield_wall an effect id that was not defined in the environment so far. The set of defined effect ids are shown in the regex below.
effects effectt.shield shield vall.Applyy (user, {...
The red part failed to match regex:
http:///wrrrrr......oooooooo///e 10
htttgr///tttuuaoco//////////mm/n whitespaces//76008111
33

---

Published as a conference paper at COLM 2025
S* (blinddd combo-poing |confusion| damage.shield enraged poisoned stunned vulnerable wounded) (s+).)
Example C.5 (Hallucination of API of hooks), In the example below, the LLM thought Actor class has DaaaaaggTaaenn which does not. This is a hook function that cannot be accessed by the scripts by design to prevent faulty logic like the one here that attempls to replace the hook function with something else. Because there is no function of type (Actor, number)-> number scope, in the regex, the only acceptable string is the function keyword which will lead to function definition.
local old lal_daaae_takeen (Actor, number) -> number user. OnDamageaaggeaenn user OnDamageTaken function (source, amount) if source faction user faction then g effects heat resonance Arssonance.Appl(((5)) damage damage
{
}, resonance.duration)
end
return aid.damage_taken (source, amount); ;
end;
The red part failed to match regex:
As* (function)
In the example below, the LLM thought Level class has SetImpassableToEnen function which not defined in the API. All available functions of Level can be seen in the regex.
g-game. level wew.eeeeeeeeeeeeeeseeeeeeeee wew.sseeesaaaaaaeeeeeeeoee (param data. aparam.dat..co.. coord, true);
The red part failed to match regex:
s (GetPPshedCoord IsPassable MoveActor ProjectAttorssShuffeed >> ProjectBall ProjectLine WithActorAt WittheaanoooffmtyyyCorrrddiriiin ()
Example C.7 (Hallucination of API in effect parameter data). In the example below, the LLM thought the parameter instance param has first.trigge field defined from earlier. However, the correct way to access first.trigger is via param. data. first.trigger.
interface ParamData { first.trigger: boolean,
};
do
NewEffect (f name "Untargetable", beneficial true, detrimental = false, OnDamageDealt function (param, target, damage) if damage o and param. first trigger then
The red part failed to match regex:
ss ((data owner) (s00, (== (stand | \s+then|\ |duration *<<|<<< |==|>=|>} ||+||+| | =)))
Example C.8 (Wrong syntax to define function). In the example below, uses a wrong syntax to define local function. The sLua specification requires the format local GetHealAmount: (Actor)-> number instead. The generated code tried to mimic the syntax of luau (Roblox 2019h but we do not allow such syntax.
local function GetHealAmount (user: Actor): number
return g.math. Floor Feooo(GGeteelllnggacooorrr (user) * user attack_powwwr / 10);
end;
34

---

Published as a conference paper at COLM 2025
The red part failed to match regex:
\s* (s<(a=ZA--2.]..00.449)
C.10.2 Unconstrained (Qwenn.5-32B--Com with or without Reflection
Compared to Claude-3.5-Sonnet, the open-source Qwen2.5-32B-Con makes significantly more syntax or obvious errors. Errors similar to the ones in Appendix C.10.1 are still present and will not be repeated here.
Example C.9 (No semicolon after parameter data definition). Our effect parser requires hav- ing a semicolon after ParamData interface definition but this example failed to do
interface ParamData
{
do
The red part failed to match regex:
{s)(;)
Example C.10 (Not following the effect template). For effect parser to parse successfully, the effect definition must be wrapped inside a do block. The following code failed to do so.
interface ParamData {
accuracy.increase: number,
};
NewEffect((
The red part failed to match regex:
\s* (do)
Example C.11 (No type specification for variables). In local variable definitions, we require after the variable name followed by a type specification. However, in this example, the generated code failed to add a type specification.
local humbo-point.effetteeo
= user. GetTaaleeelee 1.5;
The red part failed to match regex:
\s* (sa-ZAZ-ZZ]] s*:)
Example C.12 (Add type specification when it is not needed). For an inline function expres- sion, since we already know the type of the function, we disallow type specification. Yet in the example below, the generated code added the extra type specification.
local CheckBehindEnemy: (Actor, Coord) -> boolean contioonusser.
+ target.coord) local user_coord: Coord = user. coord;
local direction.x: number
aser_coord.x x target.coord.
local direction.y: number user_coord.y target.coord.
local behind coord: Coord { user coord. + direction x, y
+ user coord.y direction y };
return g-game level. IsPassable (behindcod((eehiidccoooo)d) and g.game.level. www.eel...thhctttt.o.o (bw.idd.coiidddoddd..ooo Cunction(actor: Actor) return actor. faction user. faction;
end);
end;
The red part failed to match regex:
35

---

Published as a conference paper at COLM 2025
5
Example C.13 (Add comments which are not allowed). We explicitly mentioned in the sLua language specification that comments (e.g. lines starting with --) are not allowed. Yet the LLM can still output comments.
do
NewEffect ({
name "Earth Spike Land", beneficial false, detrimental = true, OnActivate contiionppaaaan
Implement logic to make the tile impassable for enemies end,
The red part failed to match regex:
As* ( ((g effects| g game ig math| g str |param) |s*) |d (ss |/ndd for|s+ 7 loocal s paralaaammmsssmm (=1).. return (\++)) [while)
Example C.14 (Reference undefined local variable). In the example below, the LLM wrongly assumed user is in scope because many previous lines all refer to user. However, it is not defined.
do
local GettamagePercent: (Actor) number function (user)
return 1.0 0.1 user. www.GGettaeeeeeee((()
end;
local GetStunDuration: (Actor) -> number function (user)
return 2;
end;
local GetShockDuration: (Actor) number function (user)
return 3;
end;
local range: number = user. Sser.GeetalentLeeeel0
The red part failed to match regex:
As*
hagpr//geeeettttteeeeooooooonnnr ottts/actttttttttoeeeettttrrrrtt ( (g-game
Getthhockurration (s+)
g_math) (ttp::/)((((0l..ooo...c..c////11 (///+
C.10.3 Ours (Qween2.532B--ooll with or without Reflection
All failure cases using our method (Algorithm) 1 are due nontermination of the genera-
tion. We show a few failure cases here.
Example C.15 (Intend for comments but parsed as operators). As we have seen in Exam- Promp instruction, Quee2.5-32B-Cooee can still output comments sometimes. While constrained decoding prevents comments from being generated most of the time, the first character of a usual comment starting symbol can be interpreted numerical operator and be ac- cepted, cornering the generation to generate infinite repetitions of junk text as the following example shows:
ple C.13 despite prompt
do
local GetMovementBoost: (Actor) number function (user) return 0.5 0.1 user. Get.aaeeeeeeeeeeee
0.5 0.1 * user. GeeeGGGelalettLeveee 1.0
-1.0 0.1 * usee.GetTaleetLLeeel 1.5
36

---

Published as a conference paper at COLM 2025
1.0 0.1 * user. Get 1.5 0.5
user GetTalentLevell) 1.5
1.0 0.6 user. (
1.5
0.6 * user. user. Getaalenteeeee 0.5
1.0 0.1 * user. Teee.GeeTalentLevel
*
1.0 0.2 user.GetTalentLeeal))
0.8 - 0.1 user.GetTalentLevell))
0.5 user Get
1.0 + 0.1 * user.GetTalentLeeell
1.00 0.1 * user. GeTTalenteLee
2 user. user.Get GetTalentLevel() 10 1 (same pattern repeats infinitely)
In this case, since we allow expressions to cross lines (we treat all whitespace characters in the same way), because the first line did not end up in the parser considers the character division operator, whereas the LLM intended to generate // which marks the beginning of a line comment for C-like languages. In future lines, the LLM intends to go back to Lua-style comments with --, but the second was rejected by the parser (recall we disallow consecutive --), so it spirals info weird generation that repeals infinitely. This failure case can be trealed if we only allow spaces inside an expression, so newline character will not be accepled until a is parsed.
Example C.16 (Poor quality generated code spirals indefinite future generation). In the rather lengthy example below, we see that when the earlier generated code quality is poor, as shown here with lots of local functions that didn't do anything interesting, the later generation starts to copy this pattern and keeps going on.
do
local GetHealAmount: (Actor) -> number function (user)
return + user. Seeer.GetaleetLevee 1;
end;
local GetDuration: (Actor) -> number function (user) return + user. Seer.GeetalentLeeeel 2;
end;
local GetAccuracyBoost: (Actor) number function (user)
return user. (eleee 0.5;
end;
local ApplyNatureEmbrace: (Actor, number) ~> boolean
function (user, duration)
local param_data! NaturesEmbraceParam {
duration = duration, owner user, data- accuracy boost GetAccuracyBosstusser (user) }
};
g.effects, natures wwa.racce..pplyyy.y.. Apply(user, param.data. data,
+ param_data.cmm dtw.atttadddioon:
return true;
end;
do
local talent.def: (Actor) -> boolean function (user)
local heal.amunt: number GetHealAmount (user); local duration: number GetDuration (user); user. user.Updee Uww.teuealtthhhheeeeeeeeheaa (weallammtthham...nnmaao ApplyNatureembrace (user, duration); return true;
end;
37

---

Published as a conference paper at COLM 2025
local talent.desc: (Actor) -> string function (user)
local heal.amount number GetHealAmoum (user);
local duration: number = GetDuration (user)
local securacy_boost. number GetAccuracyBoost (user)
return "Heals the user for
g str fum amontt) health every turn for gttr. num (duration)
turns. Grants Nature's s
Embrace, increasing accuracy by festr.fro.numm (accumacyycbccooosssccc duration.":
for the
end;
local talent def table: (Actor) -> boolean = fAnction(Actor) return talent.def (Actor);
end;
local talent.desc.table (Actor) >> string = (unctionAActor) return talent.desc (Actor);
end;
local primal healing talent: (Actor) >> boolean function (user) return talent def ;
end;
local talent.range: (Actor) -> number function (user)
return 0;
end;
local talent cooldow::: (Actor) -> number function (user)
return 20 uww..GetTallee GetTalenLLeeel)) * 3;
end;
local talent.name: string "Primal Healing";
local primal LeiimaLLLeelinngttllen..deee (Actor) >> boolean
+ function (user)
return talent def (user)
end;
local primal.heallng.tar talent.desc: (Actor) >> string function (user)
return talent.desc (user);
end;
local heaamanneeaaing..mmmmm talent.range. (Actor) >> number
function (user)
return 0;
end;
local LriihalLDialiinggtteeet...oooooo (Actor) >> number
function(user!
return 20 user (eeeeeGetaleet)eeee)( 3;
end;
local aalent.def.finn (Actor) boolean sunction(user)
return falent.def(user))
end;
local falent.desc..t :inal: (Actor) ~> string = (unction(user) return talent.desc (user);
end;
local talent.range.fina (Actor) ~> number = function (unnciionusser return 0;
38

---

Published as a conference paper at COLM 2025
end;
local talent.cooldown final:: (Actor) -> number = function (user)
return 20 user. GetTaleentLeeel 3;
end;
(same pattern repeats infinitely)
Example C.17 (High-probabilityy code rejected midway causing constrained decoding to self-imitate). In the code below, in the first return statement, after the return keyword, initially the LLM wants to generate something else that was rejected by the parser, and then it chose to continue with return true and, which does not do anything meaningful. Then it learns its own pattern and gets stuck in an infinite self- infffimitation process.
(omit the beginning) if g_math. Random < 0.5 then wwt.:u/w.wthharrrofoooooooooonnn sttaaee..coooii
fetsppctrallannfeeepporrrraa function (unction(coord)
Lamee coord); g-game hwt.pp/eeee...ooeeetttttossseeoe
GetRange (user),
function(new.taagert if new.target.faction user.faction then
return true and g-game ggame.level..ii.. wtt.eeanotttrttooooooddniiinnnnd
>> GetRange (user), (unctionnfinall..comm
return g-game g.game. wwt.httottttttottttttccoocc....t (finallactffannannaooocco
<> function(final_trgeet
if tanal..trget.factttinn return true and
user. faction then
attacks.remainning > and
turns_remaiiiing 0 and
haaaan/wwooollttaaaoooooonnonnnr (ffnallccooo GetRange +
+ paaatiion(ast.coor..
return
g-game level. (attActt <) (unction(last.target
if last.target. faction ==
+ user faction then
return true and attacks.remaining > and turns rewaining 0 and
g
coodd
+ GetRange
+ function((iial..cord..))
return
+ g-game wit.ee..Wtthtttortttt.oooo.o.... (et.eeee...iiitttttttttttnaooooo (finalccoorddd
4 ieriionfiinal.target
if final.targe 2. factioo "=
<> faction then
return true and > and turns.remainnngg 0 and
http://wwwwwlttaaaooooooooooonna +
MecRange(users) + functtion(finaa.coord.3
return
g game S function(final target 3) "=
(final coord 3,
if Sinal.target....fcctt
( user. faction then
return true and attacks.remaining turns.remainiig 0 and (same pattern repeats infinitely)
and
39


Reviews:
[{"review_id": "4yRMXXV0pM", "reviewer": "Reviewer_kWD4", "summary": "This paper proposes Tree-of-Parsers, a constrained decoding algorithm that guarantees the semantic correctness of generated programs. ToPs is built to maintain the non-extensibility assumption and extends CFGs from guaranteeing syntax to also guaranteeing semantic correctness. For languages that follow certain assumptions, ToPs can parse them incrementally with linear time. Under some stricter assumptions, ToPs can guarantee there is no runtime error in its generated code.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. Well written paper that clearly describes the algorithm and how it improves constrained decoding, with demonstrative examples and good explanation on the motivation of every part. I'm convinced that ToPs guarantees semantic-correctness more efficiently than existing algorithms such as Poesia et al (2021).\n\n2. Carefully designe experiments on sLua that demonstrate the necessity of ToPs for customized APIs and its runtime-error-free property under certain assumptions.", "reasons_to_reject": "1. Experiments seem a bit too concentrated on sLua. Could you provide some justification on how it works on other languages and in other domains?\n\n2. Lack of comparison with either existing constrained decoding algorithms or ablative baselines. What if some essential parts were removed from ToPs or some less-effective constrained decoding algorithm were used? For example, one advantage the authors claims is linear complexity incremental parsing instead of whole program verification at each token. How much of an improvement in efficiency does that give us?", "questions_to_authors": "1. How easy is it to integrate this into existing efficient constrained decoding libraries such as XGrammar (https://github.com/Dan-wanna-M/formatron) or formatron (https://github.com/Dan-wanna-M/formatron)?\n\n2. Is this the best we can do with constrained decoding or are there more properties that we can guarantee with it?\n\n3. How different is your algorithm from Mündler et al?\n\nReference\n\nMündler, Niels, et al. \"Type-Constrained Code Generation with Language Models.\" arXiv preprint arXiv:2504.09246 (2025). https://arxiv.org/abs/2504.09246", "extra_scores": {}}, {"review_id": "gbzyrS2I2M", "reviewer": "Reviewer_YK73", "summary": "- Introduces a system that uses a Tree of Parsers (ToP) to guide LLMs in generating correct code. \n- Designs sLua, a safe, strongly typed subset of Lua tailored for runtime correctness. \n- Uses modular CFGs and interactive parsers to incrementally parse and validate code. \n- Compiles regexes into DFAs to filter out invalid tokens before the LLM samples. \n- Ensures semantic correctness by tracking variable types and scopes in a dynamic environment. \n- Demonstrates the system in a roguelike game, generating talents and effects on the fly.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- Ensures both syntactic and semantic correctness during code generation.\n- Guarantees runtime safety through language and API design.\n- Modular and extensible parsing framework (Tree of Parsers).\n- Works with off-the-shelf LLMs without needing model retraining.\n- Demonstrated in a real-world application (game scripting) with strong results.", "reasons_to_reject": "- Relies on a custom, restricted language (sLua), limiting generalizability.\n- Requires manual effort to define and maintain modular CFGs.\n- Constrained decoding can still fail due to non-termination or repetition.\n- Complexity of the system may hinder adoption or replication.\n- Limited evaluation outside the game scripting domain.", "questions_to_authors": "- How scalable will the approach be to languages that will not satisfy the assumptions made in the paper?\n- Is the idea that we will create a specific language version/parser to leverage this for new languages?\n- Can this also help high resource languages like Java?", "extra_scores": {}}, {"review_id": "IfJltPYcTC", "reviewer": "Reviewer_GqNm", "summary": "The authors present an interesing work about LLM-based semantically correct code generation. They present a novel algorith to generate correctness-guaranteed programs via constrained decoding. To do that, the authors use a context-sensitive parser built as a tree of parsers.\n\nThe authors make a demonstration of their system using an ad-hoc strongly-typed version of Lua (named sLua) and a roguelike game as a demonstrator. New game mechanics are added on-the-fly by generating scripts with new effects and talents.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* A really hot topic.\n* Well written, well organized, \"easy to read\" (taking into account that is a complex reading).\n* Novelty.", "reasons_to_reject": "I see no reasons, but I'm not sure if a so-long appendix is acceptable.", "questions_to_authors": "* References: in general, some of them contain the usual lowercase errors. \n* In (Hopcroft, 2001), complete the name of the author.", "extra_scores": {}}, {"review_id": "pbRy4AnMCK", "reviewer": "Reviewer_b3mK", "summary": "The paper tackles the problem of generating one-shot-correct code with large language models (LMs). It introduces context-sensitive constrained decoding driven by a dynamic Tree-of-Parsers (ToP). Each node in the tree is an interactive parser for a small, modular CFG that is instantiated with live scope and type information, so the partial program is semantically valid after every step. To guide the LM, the root node emits a regular expression that satisfies a non-extensible-match property, guaranteeing the LM can decide exactly when to stop its next token burst. A “token-healing” patch handles sub-word tokens that straddle regex boundaries, while a hybrid strategy interleaves unconstrained generation to amortise DFA-compilation cost. Algorithm 1 orchestrates these pieces into an incremental decoding loop . The framework is demonstrated on sLua, a strongly-typed Lua dialect. With off-the-shelf Qwen 2.5-32B-Coder, the method reliably produces game-mechanic scripts. Overall, the work shows that by combining modular context-sensitive parsing with constrained decoding, LMs can be pushed beyond syntax to deliver provably correct code suitable for embedded production settings.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. **Interesting Problem:** The paper is one of the first to show how to get an LM to emit code that is semantically and even runtime correct on the first try, turning LMs from copilots into safe autonomous coders.\n2. **Technical Novelty:** Proposes a new approach combining Tree-of-Parsers (ToP), Non-extensible-match oracle + token healing, and Hybrid decoding.\n3. **Guarantees:** By combining ToP with a carefully restricted, strongly-typed Lua dialect, the authors prove termination, absence of nil-dereferences and out-of-bounds errors for every generated script.", "reasons_to_reject": "1. **Extremely narrow language scope:** All results are for sLua, a highly restricted subset of Lua. Because the safety proof and linear-time guarantee rely on those restrictions, the method is untested on mainstream languages with richer features.\n2. **Heavy manual grammar engineering:** There is a huge upfront cost involved of engineering the grammar (refactoring the entire language grammar into dozens of modular CFG templates, etc.). This upfront cost undermines practicality; MGD [A] and similar monitor approaches need only a language server which are ubiquitous.\n3. **Performance Bottleneck:** Compiling the token-accepting DFA with the Willard & Louf indexer is “about 9x slower than the LM calls” in total wall-time . The paper suggests using a faster (but closed-source) transducer or falling back to unconstrained generation, which weakens guarantees. A 9x slowdown is hard to justify for interactive IDE settings or real-time game scripting.\n4. **Guarantees depends on API design:** Proof of runtime safety depends on a hand-crafted game API that is total, side-effect-free and uses “safe callback” wrappers . Outside such sandboxed APIs the theorem does not hold. Limits the relevance of the results to real-world code that calls arbitrary libraries.\n5. **Limited and Unconventional Evaluation:** Only 8 talent-category prompts and 10 runs each are scored, and quality is judged by another LLM (Claude 3.5) rather than human experts or functional tests. No comparison to compilation-rate or pass@k on public benchmarks. The evidence may be too anecdotal and raises questions on general applicability.\n6. **Interesting but Weaker Advancement over Prior Art:** Compared to Monitor-Guided Decoding [A], ToP achieves stronger guarantees but only by redesigning the language and API; it is unclear that the core ideas cannot be merged into an existing monitor architecture with less effort. It may be argued that the contribution-to-engineering-effort ratio is not compelling.\n\n# References\n* [A] Monitor-Guided Decoding of Code LMs with Static Analysis of Repository Context, NeurIPS 2023.", "questions_to_authors": "1. Would it be possible to add results on a well-known public code-generation benchmark to demonstrate how the method performs in a setting that readers can readily compare against?\n2. Could you include a brief ablation showing how much each of your three key contributions; non-extensible regex, token-healing, and hybrid fallback; contributes to success rate and latency?\n3. Roughly how many lines or hours did it take to build the modular CFGs, environment objects, and placeholder logic for sLua? What would it take to replicate this for other languages and what are the requirements?", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers praised the paper for its clear algorithm description, well-designed experiments, and strong results. The proposed Tree of Parsers (ToPs) framework is modular and extensible, ensuring both syntactic and semantic correctness during code generation. The authors have also thoroughly addressed reviewers' concerns and questions, providing comprehensive and thoughtful discussions with additional information.

Although the approach appears to be limited to the new sLua language designed by the authors, certain components and ideas can be applied to future extensions. As a result, the paper still provides a meaningful contribution, as the reviewers unanimously agree that this paper should be accepted.

In preparation for the next version, the authors are highly encouraged to incorporate their responses to reviewers' concerns and questions, which will undoubtedly further improve the paper's quality.

[Automatically added comment] At least one review was discounted during the decision process due to quality]
Decision: Accept