Grammar-Driven Unparsing for Bidirectional Code Transformation and Generation
Lars Shakya Buch-Jepsen
Grammar-Driven Unparsing for Bidirectional Code Transformation and Generation
1. Introduction
Parsing - turning source text into structure - is the classical problem of language tooling. Its dual, unparsing - regenerating faithful source text from structure - is equally necessary and far less theorized in practice. Any system that transforms code structurally (a refactoring engine, a translator, a repair tool, a code-generating model) must eventually emit text that human beings can read, review and edit. The gap between a semantically correct graph edit and a well-formatted, style-preserving source file is where many structural tools quietly fail.
This article describes the Unparser component of the Minotaur compiler- compiler platform: the component that renders human-readable source code from the CognitiveGraph representation. Its distinguishing commitment is that unparsing is grammar-driven: the same grammar data that drives parsing also drives rendering, through per-language plugins whose code-generation rules are derived from the grammar rather than hand-written per node type. This is the key innovation we highlight, and it is what makes bidirectional transformation - parse, edit the graph, unparse, re-parse - a natural round-trip rather than an aspiration.
2. Background: Pretty-Printing and Its Algebra
The foundational treatment of pretty-printing is Oppen’s [1], which formulates layout as a computation over breaks and groupings solvable with a linear-time pretty-printing algorithm. Hughes recast pretty printing as a library problem with combinators whose design makes formatting decisions contextually [2], and Wadler refined the algebra into a minimal set of primitives for “a prettier printer” [3]. These works share a premise we adopt: layout is a first-class computation over document structure, not a string-assembly afterthought.
Where classical pretty-printers start from a document AST of their own invention, the Minotaur Unparser starts from a language’s grammar: the ConcreteNodes of the CognitiveGraph carry node types and children that the grammar already defines, and the unparse strategy walks these nodes. The grammar is therefore the single source of truth for both directions of the round-trip.
Maintaining both directions from one artifact has a consequence worth making explicit. When a language grammar gains a construct, the parser’s coverage and the unparser’s rendering vocabulary update in the same stroke: the ConcreteNode the parse step produces is precisely the node type the unparse strategy must render, and both are projections of the same grammar data. In a conventional toolchain these are two codebases that drift apart - a parser maintained by one team, a printer or formatter by another - so every grammar change is a coordination event between them. Here that drift is structurally impossible: there is one grammar artifact, and parsing, unparsing and compiler-backend generation are all consumers of it.
3. Architecture
3.1 The GraphUnparser
The core engine, GraphUnparser, is part of the Minotaur
core components alongside the parsing integration. Unparsing is
deliberately separated from parsing at the architectural level:
StepParser handles all parsing, grammar and syntax as the single source
of truth; the plugin layer handles unparsing and compiler backend
generation only. The seam between them is the CognitiveGraph,
and the data flow across it is zero-copy - the unparser walks the same
graph objects the parser produced, with no serialization to an
intermediate form.
3.2 Strategies and plugins
Rendering is abstracted behind IUnparseStrategy and
exposed through the language plugin system. The
LanguagePluginManager resolves a plugin by language name or
file extension (GetPlugin("csharp"),
GetPluginByExtension(".cs")), and a plugin provides
both:
var plugin = integration.PluginManager.GetPlugin("csharp");
var code = await plugin.UnparseAsync(cognitiveGraph);and backend rule generation for the compiler-compiler:
var backendRules = await csharpPlugin.GenerateCompilerBackendRulesAsync();The second call is the grammar-driven half of the design: plugins emit generation rules derived from the language’s grammar, so the rendering knowledge for a language is compiled from grammar data rather than encoded node-by-node in printer code. Adding a language means supplying its grammar and a plugin, not writing a bespoke printer.
3.3 How a node becomes text
At the level of a single node, an unparse is a grammar echo. The strategy consults what the grammar says the node is and renders accordingly: a node produced under a grammar alternative for a block emits the block’s delimiters, renders each child statement in order, and closes them; a node produced under an expression alternative renders its sub-expressions in the shape and precedence the grammar gives them. The strategy never has to guess a node’s shape, because the alternative that produced the node during parsing is the same alternative that dictates its textual form. Handling a new construct is therefore not a printer-engineering decision; it is a consequence of the grammar already knowing the construct’s shape.
This is also what makes the unparser a credible consumer for edited graphs. After a transformation inserts, rewrites or removes nodes, the resulting graph is not the parse artifact of any text - it exists only because structure was manipulated as data. Rendering such a graph is the same walk as rendering a parsed one, because both are just graphs whose nodes honor the grammar’s node type and child constraints. The round-trip suite exercises precisely this case: a graph that was never text must still emit text that re-parses to the same structure.
3.4 Round-trip and the bidirectional property
The bidirectional framing is testable, and tested: the test suite includes dedicated parse-unparse integration tests, parse-edit-unparse round-trip tests (a graph is edited between the two directions, exercising the transformation case that motivates the component), and advanced unparser tests covering boundary behavior. The property of interest is that unparsed output re-parses to the same structural graph - the fixed point of the round-trip. Canonical formatting is the baseline guarantee; round-trip stability under edit is the property that makes structural transformation trustworthy.
4. Style Preservation
Preserving the original formatting of untouched code is the hard half of pretty-printing in practice: developers do not accept a refactoring that reformats their file. Two observations shape the current design. First, the CognitiveGraph can carry source-position and formatting metadata as first-level data, so the unparser is not forced to re-derive layout that the parser observed. Second, because strategies are per-language and grammar- driven, style rules (indentation, line-breaking, brace placement) are expressible in the same rule vocabulary as syntax templates rather than as special cases. Full fidelity-style preservation - byte-identical emission of unmodified regions - remains an engineering goal; the shipped guarantee today is canonical, grammar-faithful output with stable round-trip.
The style problem, stated without rose tinting, is that canonical output buys round-trip correctness but not round-trip invisibility: a whole-file canonical emission is a semantically faithful but visually aggressive change to a file a developer has opinions about. The current design keeps that boundary honest: the graph’s source-position and formatting metadata make region-local emission a natural extension of the existing walk rather than a reimplementation, and the round-trip tests pin exactly what is guaranteed today, so that future style-preserving work starts from a stated, tested baseline instead of an implied one.
5. Implementation Status
The component is shipped and tested in Minotaur: the GraphUnparser engine, the IUnparseStrategy abstraction, the plugin system with C#, JavaScript, Python and LLVM plugins, and the integration and round-trip test suites. Compiler backend rule generation is likewise shipped as part of the plugin API. The component is consumed by Minotaur’s own tooling and by Golem’s translation pipeline, which unparses translated graphs back to source.
6. Related and Future Work
The natural extensions follow the grammar-driven principle: (1) style profiles as data - per-project formatting conventions compiled into strategy rules the same way grammars compile; (2) lossless round-trip as a checked invariant in CI for every supported language; and (3) unparsing as a target for learned preferences, where the plugin’s rule vocabulary gives a constrained, formally checkable output space for a model to choose within - in contrast to free-form code generation. Each extension keeps the same shape as the core design: the grammar constrains, the component renders.
7. Conclusion
The Unparser completes the bidirectional loop of grammar-driven code transformation. By deriving rendering from grammar data through per-language plugins, and by testing the parse-edit-unparse round trip directly, Minotaur treats code generation not as string synthesis but as the dual of parsing - with the same source of truth for both directions.