A ciear and powerful formalism for describing languages, both natural and artificial, follows from a method for expressing grammars in logic due to Colmerauer and Kowalski. This formalism, which is a natural extension of context-free grammars, we call “definite clause grammars” (DCGs). A DCG provides not only a description of a language, but also an effective means for analysing strings of that language, since the DCG, as it stands, is an executable program of the programming language Prolog. Using a standard Prolog compiler, the DCG can be compiled into efficient code, making it feasible to implement practical language analysers directly as DCGs. This paper compares DCGs with the successful and widely used augmented transition network (ATN) formalism, and indicates how ATNs can be translated into DCGs.

We describe an approach to parsing and logical translation that was inspired by Gazdar's work on context-free grammar for English. Each grammar rule consists of a syntactic part that specifies an acceptable fragment of a parse tree, and a semantic part that specifies how the logical formulas corresponding to the constituents of the fragment are to be combined to yield the formula for the fragment. However, we have sought to reformulate Gazdar's semantic rules so as to obtain more or less'conventional' logical translations of English sentences, avoiding the interpretation of NPs as property sets and the use of intensional functors other than certain propositional operators. The reformulated semantic rules often turn out to be slightly simpler than Gazdar's. Moreover, by using a semantically ambiguous logical syntax for the preliminary translations, we can account for quantifier and coordinator scope ambiguities in syntactically unambiguous sentences without recourse to multiple semantic rules, and are able to separate the disambiguation process from the operation of the parser-translator.

This is an excerpt from the Handbook of Artificial Intelligence, a compendium of hundreds of articles about AI ideas, techniques, and programs being prepared at Stanford University by AI researchers and students from across the country. In addition to articles describing the specifics of various AI programming methods, the Handbook contains dozens of overview articles like this one, which attempt to give historical and scientific perspective to work in the different areas of AI research. This article is from the Handbook chapter on natural language understanding. Cross-references to other articles in the handbook have been removed-terms discussed in more detail elsewhere are italicized. Many people have contributed to this chapter, including especially Anne Gardner, James Davidson, and Terry Winograd. Avron Barr and Edward A. Feigenbaum are the Handbook's general editors.

The NLC system has grown out of an earlier series of studies on the "autoprogrammer" (Biermann[6]) and bears much resemblance to it. Program synthesis in both the current and the previous systems is based upon example calculations done by the user on displayed data structures. In the current system, the example is done in restricted English with all its power, which is a dramatic departure from the earlier approach, which simply involved pointing with a light pen. However, it is expected that many of the features from the autoprogrammer, such as "continue" and "automatic indexing", will transfer quite naturally into NLC. This paper emphasizes the natural language aspects of the system, while other reports deal with some of the additional automatic programming features. The relationship of NLC to other research in natural language processing is discussed in a later section. The next section presents an overview of NLC, after which subsequent sections discuss scanning, syntactic and semantic processing, and interpretation of commands in the "matrix computer". The next two sections discuss the processing of flow-of-control commands and the level of behavior achieved by the system. The final sections include a discussion of related research and conclusions.

The Hearsay-H speech-understanding system (SUS) developed at Carnegie-Mellon University recognizes connected speech in a 1000-word vocabulary with correct interpretations for 90 percent of test sentences. Its basic methodology involves the application of symbolic reasoning as an aid to signal processing. A marriage of general artificial intelligence techniques with specific acoustic and linguistic knowledge was needed to accomplish satisfactory speech-This research was supported chiefly by Defense Advanced Research Projects Agency contract F44620-73- C-0074 to Carnegie-Mellon University. In addition, support for the preparation of this paper was provided by USC/ISI, Rand, and the University of Massachusetts. We gratefully acknowledge their support. Views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official opinion or policy of DARPA, the U.S. government, or any other person or agency connected with them.

Our purpose in studying natural language understanding in conjunction with problem solving is to bring together the constraints of what formal representation can actually be obtained with the question of what knowledge is required in order to solve a wide range of problems in a semantically rich domain. We believe that these issues cannot sensibly be tackled in isolation. In practical terms we have had the benefits of an increased awareness of common problems in both areas and a realisation that some of our techniques are applicable to both the control of inference and the control of parsing. Early work on solving mathematical problems stated in natural language was done by Bobrow (STUDENT - (i]) and Chamiak (CARPS - [5]). However the rudimentary parsing and simple semantic structures used by Bobrow and Charniak are inadequate for any but the easiest problems. Our intention has been to build on B/RG Chris This work was supported by SRC grant number 94493 and an SRC research studentship for Mellish.

" The author wishes to thank Eileen Fitzpatrick for her helpful suggestions.

Montague's dUficu/t nulalian and complex model theory have tended to obscure potential insights for

Such features include spelling correction, processing of incomplete (ell ipt ic-I) input?, jntfrrog-t ior of th

In English, "1ikewise", "too", "similarly", etc., followed optionally by a preposition and then by a noun phrase indicate that the role filled by the new noun phrase in a previously mentioned predicate is a non-subject one.