Linguists have long written grammars as sets of rules plus feature constraints, and have often run them by translating them into Prolog programs called Definite Clause Grammars (DCGs). A DCG is a grammar in which each rule is a logic clause, so Prolog's built-in matching of terms builds the parse and the feature structure together in one pass. The approach has one well-known weakness: Prolog searches depth-first, so a rule like "a noun phrase is a noun phrase followed by a modifier" sends it into an infinite loop. Grammar transformations exist that remove these loops while keeping the set of accepted sentences the same. Nobody has checked whether they also keep the set of analyses the same, meaning the exact number and shape of parses and the feature structure each one yields. Those analyses are the point of running a linguistic grammar in the first place. The transformations also exist only for grammars whose constituents are contiguous stretches of words. They do not cover the discontinuous-constituent grammars needed for German word order.
This note proposes a termination transform for DCGs with two properties. First, it is derivation-faithful: for every sentence, the transformed program's successful proofs correspond one-to-one with the original grammar's derivations and yield identical feature structures. Second, it extends to tuple-valued grammars, where a single constituent can cover several separate stretches of the sentence. The formal-equivalence literature provides the yardstick: it distinguishes grammars that accept the same strings from grammars that also assign the same structures. The compilation literature provides the object being measured, which is the translated Prolog program. The contribution is to measure the second with the first, and then to build the transform that passes the test.
Core Claim
Work on relating grammar formalisms separates weak equivalence (same strings) from structural equivalence (same analyses). Convergence and Diversity in the Control Hierarchy makes this precise with d-weak equivalence, a yield-preserving bijection between derivation trees. The paper proves that tree-adjoining grammars, linear indexed grammars and their automaton counterparts are equivalent in that sense. Dependency Trees and the Strong Generative Capacity of CCG shows the distinction has teeth: two string-equivalent formalisms can have strictly incomparable sets of dependency structures. Neither paper touches compiled logic programs.
On the compilation side, A Simple Transformation for Offline-Parsable Grammars and its Termination Properties makes any offline-parsable DCG terminate and enumerate all solutions under ordinary Prolog. A grammar is offline-parsable if its context-free skeleton has no empty rules and no cycles that consume no input. The method first removes empty rules, then replaces left recursion with auxiliary predicates and a transitive-closure predicate. Its guarantee is stated at the level of the declarative meaning of the program on non-empty strings. It says nothing about whether the correspondence between proofs and original derivations is one-to-one.
We claim the right correctness criterion for a grammar-compiling transform is d-weak equivalence lifted to feature structures. Let $G$ be the source grammar and $P$ the transformed program. Let $D_G(w)$ be the set of derivations of string $w$ in $G$, and let $\Pi_P(w)$ be the set of successful proof trees of $P$ on $w$. We require a map $\varphi$, computable from each proof tree, such that
$$\varphi : \Pi_P(w) \to D_G(w) \text{ is a bijection, and } F_P(\pi) = F_G(\varphi(\pi)) \text{ for every } \pi \in \Pi_P(w),$$
where $F$ denotes the feature structure (for Lexical Functional Grammar, the f-structure) produced by a proof or derivation. We then make two constructive claims. The first is a variant of Dymetman's transform that threads an explicit derivation-reconstruction argument through the auxiliary and closure predicates, and so satisfies this criterion by construction. The second is a generalization of both offline-parsability and the transform to Linear Context-Free Rewriting Systems (LCFRS). In an LCFRS, a nonterminal of fan-out $k$ spans $k$ separate stretches of the sentence. In a DCG it becomes a predicate carrying $k$ pairs of difference lists, one pair per stretch.
Research Program
The first stage is analytic. We characterize exactly when Dymetman's original transform is and is not derivation-faithful. There are two concrete failure risks.
The first risk is that the transitive-closure predicate can reach the same pair of categories by different chains. Each chain must correspond to a distinct left-recursive derivation, with no duplicates and no merges. Whether that holds depends on how the closure is written.
The second risk is that turning left-branching recursion into iteration re-brackets the derivation and so reorders feature unifications. Plain term unification is order-independent, so the final f-structure should be unaffected. That argument breaks as soon as the grammar uses non-monotonic checks. Examples are LFG's constraining equations, negative constraints, and the completeness and coherence tests that A Lexical Functional Grammar System in Prolog runs during or right after parsing. The same paper already flags left recursion under correct constraint evaluation as a difficulty. We will prove faithfulness for the purely monotonic fragment, give counterexamples or a proof for grammars with delayed and non-monotonic checks, and derive the placement rule for those checks that restores faithfulness.
The second stage builds the transform. Each auxiliary predicate receives one extra argument: a partial derivation term with a hole. It records which original rule and which closure step produced the current state, so $\varphi$ is simply reading off that term. The closure predicate is written so that each closure fact is derived exactly once per original rule chain. Checks that are not monotonic are postponed to the points where the original grammar would have run them, which the derivation term identifies.
The third stage is the tuple generalization. For LCFRS we define offline-parsability-k: no rule may produce an empty component, and every cycle in the skeleton must advance at least one component's difference list. Left recursion then becomes a component-wise notion. A call is left-recursive if it re-enters a predicate without having consumed input in any of its $k$ input positions. We extend the empty-rule elimination and the closure encoding to this setting and prove termination, completeness and derivation-faithfulness.
The link to the formal-equivalence literature is deliberate. The skeleton of an LCFRS derivation is a regular tree language. This is the same property that lets tree-adjoining grammars be compiled to regular tree grammars and then to DCGs, as in Comparing the performance of two TAG-based surface realisers using controlled grammar traversal, and it is why a bijection on derivations is the natural target.
Baselines
Naive DCG execution. The first reference point is direct execution of the untransformed DCG under standard depth-first Prolog, the approach of the classic LFG-in-Prolog systems such as A Lexical Functional Grammar System in Prolog. It is faithful by definition whenever it terminates, so on grammar fragments without left recursion it acts as an oracle for derivation counts. On left-recursive grammars we expect it to loop. We will run it with a fixed timeout and report the fraction of sentences on which it terminates. The only numbers the file gives for it are a parse time of about 2.3 seconds for one Kaplan/Bresnan sentence on a VAX 11/780, and a French grammar of about 50 rules. Neither is comparable to modern hardware, so no accuracy or throughput figure is available to beat.
Dymetman's transform. The strongest existing method for the termination problem is A Simple Transformation for Offline-Parsable Grammars and its Termination Properties, applied unmodified. It is the direct competitor because it already guarantees termination and completeness, so our variant earns its place only if the original actually breaks faithfulness or cannot handle tuples. We run both transforms on identical grammars under the same Prolog system and time budget. The paper reports no empirical results: no reported result found on Lacuna for the Dymetman transform on any treebank-derived grammar. Our variant beats it if either of two things holds. One is that the original yields derivation counts or f-structures that differ from the reference on some sentences while ours matches on all. The other is that ours matches it exactly and additionally covers fan-out-2 grammars that it cannot express, at no more than a small constant-factor runtime cost.
Chart-based reference parsers. For the tuple experiments, the reference is an exhaustive LCFRS chart parser over the same extracted grammar, in the spirit of Span-Based LCFRS-2 Parsing and Supertagging-based Parsing with Linear Context-free Rewriting Systems. The first of these reports Negra Dis-F1 of 72.58 and 57–68 sentences per second with a BERT supertagger at $k=10$, against 1–2 sentences per second for earlier LCFRS parsers. We do not compete on Dis-F1. A faithful transform run on the same grammar must produce exactly the chart parser's derivation set, hence identical accuracy. The chart parser therefore serves as the ground truth for derivation sets and as the speed yardstick. The comparison uses the same extracted grammar, the same supertag-restricted lexicon where pruning is used, and the same sentences. "Beating" here means exact agreement on derivation sets, with throughput reported honestly.
For the tree-adjoining grammar setting, the analogous reference is RTGEN from RTG based surface realisation for TAG. On MODIFIERS it builds an average unpacked chart of 918.31 structures against 2,018 for GENI.
Ablation. The ablation removes the derivation-reconstruction argument and the check-placement rule from our transform, keeping the rest identical. This isolates whether faithfulness comes from those ingredients or from the closure rewrite itself.
Why not just…?
Why not just use tabled Prolog, which handles left recursion natively? This is the most serious alternative, and we will run it as an additional baseline. Tabling stores each distinct answer once, deduplicating answers that are variants of each other. Two distinct derivations that yield the same feature structure therefore collapse into one answer, which is exactly the loss of derivational ambiguity our criterion forbids. Adding derivation terms to the tabled arguments restores the distinction but removes the sharing that made tabling attractive. Tabling also interacts awkwardly with the non-ground, open-ended feature lists used in LFG compilation. If tabled execution with derivation terms matches our derivation counts at comparable cost, the transform's advantage shrinks to portability and a proof of correctness, and we will say so.
Why not just use a chart parser with packing and skip DCGs? For pure throughput on a fixed formalism, a dedicated chart parser may well win, and the LCFRS parsers above show strong numbers. The question here is different. When the DCG compilation route is used for its single-pass unification of features and structure, is it faithful? RTG based surface realisation for TAG shows that stripping features from the skeleton (its RTGen-level0 setting) inflates charts and runtime on complex inputs. That result supports keeping constraints interleaved with structure building, which is what a DCG does. Our experiments report chart-parser speed alongside ours so readers can judge the trade-off directly.
Why not just use a neural parser? End-to-End Graph-Based TAG Parsing with Neural Networks reaches 93.26 UAS on the WSJ treebank, but it answers a different question. It predicts one analysis without guaranteeing grammaticality or enumerating a grammar's analyses, and its authors note difficulty with rare constructions such as right node raising. Grammar engineering, grammar-based test-suite generation of the GENSEM kind, and precision parsing all need the exact derivation set of a given grammar, which is what we certify.
Proposed Experiments
Experiment 1 uses hand-built LFG fragments. These cover the Kaplan/Bresnan test sentences from the Eisele–Dörre system, extended with left-recursive modifier and coordination rules and with constraining equations. On sentences where naive execution terminates, we compare derivation multisets and f-structures across the naive program, the original transform, our transform and tabled execution. Canonicalized f-structures are compared up to variable renaming.
Experiment 2 uses SEMXTAG compiled through the regular-tree-grammar route of Comparing the performance of two TAG-based surface realisers using controlled grammar traversal, on the MODIFIERS and COMPLEXITY benchmarks. Modifier stacking produces heavy attachment ambiguity and left-recursive derivation chains, which is exactly where re-bracketing could merge or duplicate analyses. RTGEN's packed derivation forest serves as the reference count.
Experiment 3 uses fan-out-2 LCFRS grammars extracted from Negra and Tiger. For each sentence up to a length where exhaustive enumeration is feasible, we compare our tuple transform's derivation set against the exhaustive chart parser. We report termination rate, exact-agreement rate, the ratio of rule count after transformation to rule count before, and runtime as a function of sentence length.
The decisive checks come in three outcomes. We expect 100% exact agreement for our transform on all three suites. If the original transform disagrees on any sentence, the faithfulness gap is real and fixed. If it never disagrees, we will have turned an open question into a proof for the monotonic case, and the novelty rests on the non-monotonic check-placement result and the tuple extension. Failure of our transform to terminate on any offline-parsable-k grammar would falsify the proposed generalization.
References
- Convergence and Diversity in the Control Hierarchy
- Dependency Trees and the Strong Generative Capacity of CCG
- A Simple Transformation for Offline-Parsable Grammars and its Termination Properties
- A Lexical Functional Grammar System in Prolog
- Comparing the performance of two TAG-based surface realisers using controlled grammar traversal
- Span-Based LCFRS-2 Parsing
- Supertagging-based Parsing with Linear Context-free Rewriting Systems
- RTG based surface realisation for TAG
- End-to-End Graph-Based TAG Parsing with Neural Networks