Syntax-Guided Synthesis (SyGuS)

A context-free grammar (CFG) that defines the set of all syntactically valid candidate programs. This grammar explicitly constrains the search space, specifying the allowed operations, constants, and the structure of expressions. For example, a grammar for synthesizing integer arithmetic functions might be:

• Start ::= Start '+' Start | Start '*' Start | 'x' | 'y' | '0' | '1' This prevents the synthesizer from generating programs with unsupported operations or types, making the search tractable and ensuring the output is in the desired form.

A logical formula that defines the functional correctness condition the synthesized program must satisfy. This is typically a first-order logic formula in a background theory (e.g., bit-vectors, linear integer arithmetic). The specification φ(f, x) relates the target function f to its inputs x. For a function to compute the maximum of two integers, the specification could be: ∀x ∀y: (f(x,y) ≥ x) ∧ (f(x,y) ≥ y) ∧ (f(x,y) = x ∨ f(x,y) = y) The synthesizer's goal is to find a function f (from the grammar) that makes this formula universally true.

The target symbol representing the unknown program. In the logical specification, this is a function symbol (e.g., f) whose definition is to be discovered. The grammar provides the syntactic template for its body. The synthesis problem is essentially to find a concrete implementation (a term from the grammar) to substitute for this function symbol such that the entire specification becomes valid. This separates the "what" (the specification using f) from the "how" (the expression defining f).

The logical domain and its interpretation that gives meaning to the symbols in the grammar and specification. Common theories used in SyGuS include:

• Linear Integer Arithmetic (LIA): For integer expressions with addition and multiplication by constants.
• Bit-Vectors (BV): For fixed-width machine integers and bitwise operations.
• Strings: For string manipulation functions.
• Arrays: For functions that read from or write to arrays. The theory determines the available primitives and the capabilities of the underlying Satisfiability Modulo Theories (SMT) solver used to verify candidate solutions against the specification.

The algorithmic procedure that searches the grammar-defined space for a program satisfying the specification. While not a formal component of the problem definition, it is the essential solver. The dominant approach encodes the search as an SMT constraint-solving problem. The engine iteratively:

1. Proposes a candidate expression from the grammar.
2. Queries the SMT solver to check if it satisfies the specification.
3. If not, uses the solver's counterexample (a concrete input where the candidate fails) to refine the search. This loop is often formalized as the Counterexample-Guided Inductive Synthesis (CEGIS) algorithm.

SyGuS provides a formal umbrella for several synthesis approaches by varying its components:

• Programming by Example (PBE): The specification is a conjunction of concrete input-output pairs. SyGuS generalizes this with a logical formula.
• Sketch-Based Synthesis: The grammar is derived from a program sketch with "holes."
• Type-Directed Synthesis: The grammar is generated from a rich type signature.
• Superoptimization: The grammar consists of low-level machine instructions, and the specification is equivalence to a target code snippet. The standardized SyGuS competition format has driven advances in solvers like CVC4, CVC5, and EUSolver.

A foundational algorithmic loop for program synthesis. CEGIS iterates between a synthesis engine (which generates candidate programs) and a verification engine (which checks candidates against a formal specification). If verification fails, the counterexample (an input where the candidate fails) is fed back to the synthesis engine to refine the search. This loop continues until a verified program is found or resources are exhausted. SyGuS problems are often solved using a CEGIS loop where an SMT solver acts as the verifier.

A synthesis paradigm where the specification is a set of concrete input-output examples. The synthesizer must infer a general program consistent with all provided examples. This is highly user-friendly but can lead to overfitting—the program works on the examples but fails on unseen inputs. SyGuS can be used to implement PBE by encoding the examples as a logical constraint within the broader grammar-guided search, adding robustness against overfitting.

A technique where the user provides a partial program template (a sketch) containing "holes" (syntactic placeholders). The synthesizer's job is to fill these holes with expressions from a defined set to produce a complete, correct program. The sketch acts as a powerful structural constraint, dramatically reducing the search space. SyGuS is the underlying engine for many sketch-based synthesizers, where the sketch defines the grammar's non-terminals and the holes are the synthesis targets.

The automatic creation of programs within a custom, constrained language tailored for a specific problem domain (e.g., data transformations, hardware design, SQL queries). The DSL's grammar defines the legal operations and structure. SyGuS is a perfect fit for DSL synthesis: the DSL's grammar becomes the syntactic template, and a domain-specific semantic specification (e.g., "output table must join these columns") becomes the logical constraint. This approach is used in tools for automated data wrangling and superoptimization.

The use of mathematical logic to prove that a program meets its formal specification. While synthesis generates code, verification validates it. In SyGuS and CEGIS, verification is integral to the loop. Correct-by-construction synthesis is a stronger guarantee where the synthesis process itself produces a proof of correctness. SyGuS, when paired with a sound SMT solver, can provide correctness guarantees for the synthesized expressions within the bounds of the provided specification and theories.