Parsing and derivational equivalence
Mark Hepple, Glyn V. Morrill · 1989
It is a tacit assumption of much linguistic inquiry that all distinct derivations of a string should assign distinct meanings. But despite the tidiness of such derivational uniqueness, there seems to be no a priori reason to assume that a grammar must have this property. If a grammar exhibits derivational equivalence, whereby distinct derivations of a string assign the same meanings, naive exhaustive search for all derivations will be redundant, and quite possibly intractable. In this paper we show how notions of derivation-reduction and normal form can be used to avoid unnecessary work while parsing with grammars exhibiting derivational equivalence. With grammar regarded as analogous to logic, derivations are proofs; what we are advocating is proof-reduction, and normal form proof; the invocation of these logical techniques adds a further paragraph to the story of parsing-as-deduction.