Parsing and Type Inference For Natural and Computer Languages

Abstract

Computational and theoretical linguists and computer scientists interested in the computer processing of natural language have converged on a class of grammar formalisms for describing the well-formedness conditions of natural languages. This class is distinguished by its reliance on systems of declarative constraints to explicate natural-language syntax axiomatically, rather than generatively or procedurally. Intuition suggests that these various efforts from a broad range of disciplines form a natural methodological class; still, there is no general foundation on which to ground this impression. We provide a method for abstractly and uniformly characterizing a class of formalisms based on logical constraints, and use the uniformity to define and prove correct a parsing algorithm that applies to any formalism in the class. We discuss the applicability of these techniques to computer languages as well, specifically to type inference. In so doing, extensions of the simple formalism instances typically considered in natural-language analysis are motivated. This dissertation thus provides a mathematical and computational foundation for, and extensions of, current practices in theoretical and computational linguistics, as well as initiating a rapprochement between the techniques for describing well-formedness of natural and computer languages.