Abstract Syntax Tree (AST)

ASTs break down a flat string of code into a deeply nested tree structure. The root node represents the entire program, while leaf nodes represent atomic tokens like identifiers and literals. This hierarchy explicitly encodes operator precedence and associativity, eliminating the ambiguity present in raw text. For example, the expression x = a + b * c is parsed into an assignment node with an addition node on the left and a multiplication node on the right, ensuring the correct order of operations.

The 'abstract' in AST refers to the omission of syntactic noise irrelevant to program logic. Details like semicolons, parentheses used solely for grouping, and whitespace are typically discarded. What remains is a pure structural representation. For instance, a for loop is not stored as the keyword 'for' but as a dedicated ForStatement node with child properties for the initializer, condition, and increment, making it ideal for static analysis and transformation.

Each node in an AST has a specific type that defines its grammatical category. Common node types include:

• ExpressionStatement: A statement consisting of a single expression.
• BinaryExpression: An operation with a left and right operand.
• Literal: A fixed value like a number or string.
• Identifier: A named reference to a variable or function. This strict typing allows compilers and linters to use visitor patterns to execute logic based on node kind.

ASTs are the essential data structure for programmatic code transformation. Tools like Babel, TypeScript Compiler API, and Clang operate by parsing source text into an AST, applying transformations to the tree, and then generating new code from the modified tree. This is the core mechanism behind transpilation, minification, and automated refactoring. Without an AST, these tools would have to rely on fragile string manipulation.

When a language model generates code, parsing the output into an AST is the most robust method of validation. If the model's output cannot be parsed into a valid tree, it is syntactically broken. This acts as a hard constraint in structured output formatting. Frameworks like Outlines and Instructor use AST generation or grammar-constrained decoding to guarantee that the model's output is not just valid JSON, but a syntactically correct program in the target language.

A standard AST is a lossy representation, stripping away comments and formatting. A Concrete Syntax Tree (CST) or parse tree is a lossless counterpart that contains every token, including whitespace and comments. This distinction is critical for formatters like Prettier, which use a CST to rebuild code with a new style while preserving original comments. For most logical operations like type-checking or optimization, the lossy AST is preferred for its simplicity.

A set of recursive production rules that define all possible valid strings in a formal language. In structured output, a CFG serves as the blueprint for the AST.

• Rules map non-terminal symbols to sequences of terminals and non-terminals.
• Recursive rules enable nesting, which is essential for representing JSON objects or code blocks.
• Ambiguity in a grammar can lead to multiple valid ASTs for the same input, a critical problem to avoid in schema validation.

The process of forcing a language model's output to conform to a formal grammar during token generation. This guarantees the final string is parseable into a valid AST.

• Uses a Finite State Machine (FSM) to track valid next tokens.
• Physically masks invalid token logits at each decoding step.
• Eliminates the need for post-hoc output parsing and error correction.
• Frameworks like llama.cpp use GBNF Grammar notation to define these constraints.

An abstract computational model used during guided generation to track the current valid state of an output sequence. The FSM determines the exact set of permissible next tokens.

• States represent positions within the grammar's production rules.
• Transitions occur when a valid token is generated.
• The FSM advances through the grammar in lockstep with the language model's decoding loop.
• This guarantees that the final string will parse into a syntactically correct AST without errors.

A vocabulary for annotating and validating JSON documents. It defines the expected structure, data types, and constraints that a generated AST must satisfy.

• Specifies type (object, array, string, number, boolean, null).
• Defines required properties and their individual schemas.
• Supports enum values, pattern regex constraints, and numeric ranges.
• Serves as the contract between the language model's structured output and the consuming API.

A decoding technique that dynamically sets the probability of invalid tokens to zero before sampling. This physically prevents the model from generating text that would break the target AST structure.

• Operates on the logits vector before softmax normalization.
• A mask value of -inf ensures the token has zero probability.
• Unlike post-processing, masking guarantees structural validity at every step.
• Essential for enforcing bracket matching, key quoting, and value type constraints.

The post-processing step of converting a raw language model string into a structured data format. When an AST is not guaranteed by constrained generation, parsing is the fallback.

• Regex extraction attempts to find JSON blocks within markdown fences.
• Error recovery heuristics fix trailing commas or unquoted keys.
• Libraries like Pydantic and Instructor validate the parsed result against a schema.
• Parsing is inherently fragile compared to grammar-constrained generation, which prevents errors entirely.