Specifications for a Tree Processing Language

26 1965 International Conference on Computational Linguistics SPECIFICATIONS FOR A TREE PROCESSING LANGUAGE by R. Tabory, F. L. Zarnfaller International Business Machines Corporation Thomas Jo Watson Research Center Yorktown Heights, New York "% ~ y / ,~ ..,. ! • -~, ,,,<;o°/ SPECIFICATIONS FOR A TREE PROCESSING LANGUAGE F. by R. Tabory L0 Zarnfaller International Business Machines Corporation Thomas J. Watson Research Center Yorktown Heights~ New York ABSTRACT: Description of trees and strings - both composed of lexical values - matching of trees and strings against partially or totally defined pattern and operations on trees and strings form the essential part of the Processor° The notion of string has been ex- tended to strings embedded in or extracted from trees, and a modi- fied version of the COMIT rewriting rule applied to these strings. Variables ranging over lexical values, strings and trees can be intro- duced and operated on according to a "pushdown" principle. Besides, variables can be operated either ir~ the "connected" or "autonomous t' mode, depending whether their connections with some parent struc- ture are remembered or not. Variable value structures can be matched against patterns or compared among themselves. Trans- formations on trees and strings are defined, allowing for the devel- opment of a given data structure into a new one. All these features and devices were defined by extracting the elementary steps with which linguists compose their operations and by generalizing these steps reasonably. The resulting language specifications are pro- posed for discussing the solution of a class of non-numerical pro- gramming problems. Introduction Recent developments in computational linguistics have shown the need for a convenient programming formalism enabling linguists to handle data processing problems of natural languages. Especially tree and an extended kind of string processing have to be made con- ceptually easy for the linguistically oriented computer user. This paper proposes specifications for such a language; it should be thought of - theoretically only, since its implementation is not planned presently- as a procedure package attached to NPL (New Programming Language). The reason for this is the desire to take full advantage of the highlights of a modern higher level programming language as well as of the devices any general purpose programming system is in pos- session of. Consequently, the operations described in this paper should be thought of as being complemented by the full power of NPL, the most interesting features of which - from the viewpoint of non- numerical processing - are: recursive procedure calls, dynamic storage a11ocation; numeric, character string and bit string data arranged in structures and multi-dimensional arrays, etc. Description of trees and strings, both composed of lexical values, and operations on them form the essential part of the Processor° The word "processor" covers both a programming language, and a data organizing system in the computer memory° As far as string descrip- tions and string processing is concerned, the influence of COMIT was dominant in elaborating the relevant part of the Processor, but the notion of string has been …

Content truncated to 500 words