Introduction
In the early 1990s, natural language generation (NLG) systems primarily relied on the Semantic-Head-Driven (SHD) algorithm. While SHD successfully combined top-down and bottom-up processing, its heavy reliance on backtracking made it inefficient for large-scale grammars. When a generation path failed, the system discarded all progress and restarted, creating a significant bottleneck for complex linguistic tasks. Furthermore, these systems struggled with dialogue recovery; if a user failed to understand an explanation, the generator lacked a structured "memory" to identify failure points and offer alternatives.
The Bidirectional Chart Generation (BCG) Algorithm
To address these inefficiencies, the authors introduced the Bidirectional Chart Generation (BCG) algorithm. BCG adapts the concept of a "chart"—a memoization table traditionally used in parsing—to the generation process. By storing partial results, BCG transforms a search-heavy problem into a table-filling task, effectively eliminating the need for backtracking.
A key challenge in applying charts to generation is that, unlike parsing where words have a fixed linear order, semantic components in generation are non-linear. BCG solves this using "forward links" to dynamically manage the adjacency of edges in the chart. The algorithm was implemented using Guarded Horn Clauses (GHC), a parallel logic programming language, enabling the simultaneous processing of different sentence segments or planning nodes.
Uniform Control for Syntax and Planning
One of BCG's most significant contributions is its uniform treatment of surface-level syntax and high-level text planning. The algorithm applies the same chart-based logic to Rhetorical Structure Theory (RST) plan operators.
As shown in the planning tree, the system identifies "choice points" where multiple rhetorical strategies might apply. Because the chart preserves every partial structure created, the generator maintains a trace of its reasoning. This allows for "recovery through relaxation": if a user indicates they do not understand, the system can inspect suspended edges in the chart and relax specific constraints—such as assumptions about the user's prior knowledge—to find an alternative explanation path without re-planning from scratch.
Evaluation and Results
The algorithm was evaluated using two primary datasets: a sample Japanese grammar designed to test semantic-head and non-chain rules, and a set of RST-based plan operators for an expert system explaining Prolog programming.
The results demonstrated that BCG could generate complex sentences without any backtracking, significantly improving efficiency over the standard SHD algorithm. In the context of the Prolog explanation system, BCG successfully handled follow-up queries. For instance, if an initial explanation of tail-recursion optimization failed, the system could pivot to explaining the necessity of the "cut" symbol by traversing alternative paths already stored in the chart.
Conclusion and Future Work
BCG represents a significant step forward in making NLG systems more robust and efficient. By treating parsing and generation as two sides of the same coin—where the "semantic head" in generation mirrors the "left-corner" in parsing—the authors brought the efficiency of chart parsing to text production.
However, challenges remain. While the chart provides the necessary data for recovery, defining the optimal "recovery heuristics" to choose between alternative paths is an ongoing area of research. Additionally, while the parallel implementation shows promise, the mapping of chart edges to exact surface word order in highly flexible languages requires further exploration.
Summary updated