The invention relates to a method for determining the permissibility of a series of a1 . . . an end symbols as being derivable by means of a set of production rules on the basis of a pre-determined context-free grammar G, by assigning dotted rules to elements Ti,j (0.ltoreq.i.ltoreq.j.ltoreq.n) of a recognition matrix, which dotted rules indicate the derivability of a series of end symbols a(i+1), a(i+2) . . . aj, in which respect the assignation to element Ti,j (i.noteq.j) takes place on the basis of dotted rules assigned to element Ti,(j-1) by means of a scan operation, and of dotted rules assigned to a first series of element combinations Ti, (j-1)/T(j-1),j; Ti,(j-2)/T(j-2),j; . . . ; Ti,(i+1)/T(i+1),j; Ti,i/Ti,j by means of respective complete operations, and the assignation to element Tj,j on the basis of dotted rules assigned to a second series of elements (TO,j . . . T(j-1),j) by means of respective predict operations. The investigation therefore gives an answer to the question: can the series of elememts be generated by the relevant grammar? Or also: is the relevant series of elements a sentence of the language that can be constructed with the aid of the relevant context-free grammar. In the literature this investigation is known as--Parsing--. As general background references to the technology of parsing the following two books are cited: A. Aho et al., "The Theory of Parsing, Translation and Compiling", Vol. 1: Parsing, Prentice-Hall 1972, or also S. L. Graham et al., "Parsing of General Context-Free Grammars", Advances in Computers, Vol. 14, Academic Press, 1976. However, the present invention does not improve on the theory of parsing per se, but only to the technological realization of such parsing. A test of the above permissibility is a first step before a translation operation can be carried out. The translation may be that between two natural languages, in so far as these are completely context-free, between two artificial languages (for example computer languages) or, with the above-mentioned restriction, between an artificial language and a natural language. Earley's method for carrying out such a test is given on pages 320-322 of the first book cited. This method requires a great many operations and its performance on a sequential computer is very time-consuming. It can be proved that for a series of end symbols consisting of n elements the number of operations is of the order of (n.sup.3). An object of the invention is to structure the performance of this method in such a way that the processing speed can be substantially increased when it is mapped on a multimodular device. In itself, an advantageous structure of a network of processing modules in which the method referred to can be implemented is described in U.S. application Ser. No. 007,155, and incorporated herein by way of reference. In this reference a network of processing modules is described in which at a limited degree G of the network (number of connecting lines per module) the maximum distance between two arbitrary modules (diameter of the network) expressed in the number of communication lines needed for this remains limited between two modules.
USPTO Backgrounds
USPTO Backgrounds