Computable Syntactic Analysis: The 1959 Computer Sentence-Analyzer

0. Each sentence-structure is a sequence of marks, each mark a class (category) of words. An attempt is made to describe every sentence as composed of a center string (a particular sequence of marks found in every sentence) and various substrings X which are adjoined at stated points Y (Y ‘relative center’ of X) within any (center or sub-) string. 1. Of the operators FX(Y) which adjoin these substrings X (to their relative center Y), the great majority are recursive with respect to the word categories defined. (Without this the denumerable set of sentences would not be obtainable from a finite vocabulary and set of operations.) For many operators Fx(Y) in English, F = G(Y), i. e. the substring X which is adjoined to Y contains within itself an occurrence of Y. Substrings are nested when the relative center of a right (left) substring is a non-rightmost (leftmost) element of another string. Otherwise, substrings are disjoint. (In this case, the associativity of substring-adjoining can lead to certain ambiguities.) 2. Some 30 string-adjoining operators are listed, these being all the main ones for English. A partial ordering is imposed upon them by the fact that the point of application Y of some substrings is in other (previously imported) substrings. 3. The operators FX(Y), with the sentence-center, can be arranged into a generator which will generate all and only the sentences of the language. Special provision has to be made for operators (especially Fe) whose string-adjoining depends (but not in a completely simple way) upon the operand (the point of application). There are also substrings which replace an element, rather than being adjoined to it. 4. To compute the structure of a sentence is to state a general procedure for scanning the marks of any sentence and deciding what is its center and what are the substrings, to what adjoined. Various related methods of computation are discussed, and it is of interest to see in what respects more is needed than a finite-state device. It is necessary to distinguish first-order strings, and second-order strings which are fixed sequences of the first; this can be expressed as a network of trees having a stateable type of general structure. Nesting of (second-order) strings can be computed by a repeating finite-state recognizer which scans only strings that do not contain strings. The fact that element (string, etc.) A requires the presence of element B can be expressed by counting A as an inverse of B in respect to the larger structure. 5. At various steps of the analysis we may find not one decision but two or more alternative ones, either because a word can be a member of two different classes, or more generally because a sequence can have two different statuses within the string that includes it. The undecidability at a given stage of the analysis is expressed by a decision variable which can take as values the various possible decisions. Further computation then includes this variable, and resolves it on the basis of the neighborhood of other marks in the larger string. The variable may be given preferred values, for one analysis of the string, with the other values being checked later for other analyses. In this way, there is an ordering of analyses; and instead of indecisions along the way, we have a (small) set of alternative analyses for a sentence, each internally decided. 6. The substring analysis of sentence structure, presented here, is compared briefly with the related transformational analysis.