Artificial Intelligence 6:53-74.

In Schank, 157-288.

Publication 29, Institute of Linguistics, University of Stockholm.

In Rustin, 111-154.

The aim of this paper is to present in a rigorous way the syntax and semantics of a certain fragment of a certain dialect of English. Patrick Suppes claims, in a paper prepared for the present workshop [the 1970 Stanford Workshop on Grammar and Semantics], that at the present time the semantics of natural languages are less satisfactorily formulated than the grammars ¼ [and] a complete grammar for any significant fragment of natural language is yet to be written.'' This claim would of course be accurate if restricted in its application to the attempts emanating from the Massachusetts Institute of Technology, but fails to take into account the syntactic and semantic treatments proposed in Montague (1970a, b). Thus the present paper cannot claim to present the first complete syntax (or grammar, in Suppes' terminology) and semantics for a significant fragment of natural language; and it is perhaps not inappropriate to sketch relations between the earlier proposals and the one given below. Montague (1970b) contains a general theory of languages, their interpretations, and the inducing of interpretations by translation.

Dept. of Computer Sciences and CAI Laboratory, University of Texas, Austin.

In R. J. O'Brien (Ed.), Report of the twenty-second annual round table meeting on linguistics and language studies. (Monograph Series on Languages and Linguistics, No. 24.) Washington, D.C.: Georgetown University Press, 35-56.

Full text available for a fee. "The use of augmented transition network grammars for the analysis of natural language sentences is described. Structure-building actions associated with the arcs of the grammar network allow for the reordering, restructuring, and copying of constituents necessary to produce deep-structure representations of the type normally obtained from a transformational analysis, and conditions on the arcs allow for a powerful selectivity which can rule out meaningless analyses and take advantage of semantic information to guide the parsing. The advantages of this model for natural language analysis are discussed in detail and illustrated by examples. An implementation of an experimental parsing system for transition network grammars is briefly described." Communications of the ACM, Vol. 13, No. 10, October, 1970, pp. 591-606 (reprinted in RNLP: 71-88).

A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to n3 (where n is the length of the string being parsed) in general; it has an n2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.

See also: ACM Digital Library.CACM 13 (1):15-30