ABSTRACT

ACL '92

Comparing Two Grammar-Based Generation Algorithms: A Casestudy Miroslav Martinovic Tomek Strzalkowski

TOPIC AREA: WRITTEN LANGUAGE GENERATION.

ABSTRACT

We compare two grammar-based generation algorithms recently published, the Semantic-Head-Driven Generation Algorithm (SHDGA), and the Essential Arguments Algorithm (EAA). Both have successfully addressed, and resolved several outstanding problems left unresolved by the previous work in this field, such as handling semantic nonmonotonical grammars, error-prone left-recursive rules, nondeterminism, etc. In this paper, we concentrate on the comparison of selected properties of the two: their generality, efficiency, and determinism. It is discussed and shown that EAA's traversals of the analysis tree for a given language construct, include also the one taken on by the SHDGA. We also point out a specific and very common situation, that causes SHDGA to run into serious inefficiency, and non-determinism, which is handled by the EAA in an efficient and deterministic manner. One more aspect in which the EAA can be regarded as superior over SHDGA is discussed as well: its multidirectionality.