Syntactic and Semantic Parsability

SYNTACTIC AND SEMANTIC PARSABILITY Geoffrey K. Pullum Syntax Research Center, Cowell College, UCSC, Santa Cruz, CA 95064 and Center for the Study of Language and Information, Stanford, CA 94305 ABSTRACT This paper surveys some issues that arise in the study of the syntax and semantics of natural languages (NL's) and have potential relevance to the automatic recognition, parsing, and translation of NL's. An attempt is made to take into account the fact that parsing is scarcely ever thought about with reference to syntax alone; semantic ulterior motives always underly the assignment of a syntactic structure to a sentence. First I con- sider the state of the art with respect to argu- ments about the language-theoretic complexity of NL's: whether NL's are regular sets, deterministic CFL's, CFL's, or whatever. While English still appears to be a CFL as far as I can tell, new argu- ments (some not yet published) appear to show for the first time that some languages are not CFL's. Next I consider the question of how semantic filtering affects the power of grammars. Then I turn to a brief consideration of some syntactic proposals that employ more or less modest exten- sions of the power of context-free gr-mm-rs. I. INTRODUCTION Parsing as standardly defined is a purely syn- tactic matter. Dictionaries describe parsing as analysing a sentence into its elements, or exhibit- ing the parts of speech composing the sentence and their relation to each other in terms of government and agreement. But in practice, as soon as parsing a natural language (NL) is under discussion, people ask for much more than that. Let us distinguish three kinds of algorithm operating on strings of words: recognition output: a decision concerning whether the string is a member of the language or not parsing output: a syntactic analysis of the string (or an error message if the string is not in the language) translation output: a translation (or set of transla- tions) of the string into some language of semantic representation (or an error mes- sage if the string is not in the language) Much potential confusion will be avoided if we are careful to use these terms as defined. However, further refinement is needed. What constitutes a "syntactic analysis of the string" in the defin- ition of parsing? In applications development work and when modeling the whole of the native speaker's knowledge of the relevant part of the language, we want ambiguous sentences to be repesented as such, and we want Time flies like an arrow to be mapped onto a whole list of different structures. For rapid access to a database or other back-end system in an actual application, or for modeling a speaker's performance in a conversational context, we will prefer a program that yields one syntactic description in response to a given string presenta- tion. Thus we need to refer to two kinds of algo- rithm: all-paths parser output: a list of all structural descriptions of the string that the grammar defines (or an error …

Content truncated to 500 words