The Primordial Soup Algorithm A Systematic Approach to the Specification of Parallel Parsers

The Primordial Soup Algorithm A Systematic Approach to the Specification of Parallel Parsers Wil Janssen, Mannes l)oel, t(laa,s Sikkel, Job Zwicrs University of Twente, Dept. of Computer Science P.O. Box 217, 7500 AE Ensehede, The Netherlands E-mail: {janssenw,mpoel,sikkel,zwiers}(c~cs.utwente.nl Abstract A general framework for parallel parsing is pre- sented, which allows for a unitied, systematic approach to parallel parsing. The l'rimordial Soup Algorithm creates trees by alh)wing par- tial parse trees to combine arbitrarily. By adding constraints to the general algorithm, a large, class of parallel parsing strategies can be detined. This is exemplified by CYK, (hot, torn up) Earley and de Vreught & Honig parsers. From such a pars- ing strategy algorithms for various machine ar- chitectures can be derived in a systematic way. 1 Introduction In this paper we present a general framework for parallel parsing algorithms. Parsing ean be seen ms a process in which a set of partial parse trees is recognized. One starts with the productions as elementary trees. Small trees Cml be combined into larger trees, yielding ew~.r larger and larger structures, until completed parses for a particu- lar target sentence are produced. We envisage the set of recognized trees as a kind of primor- dial soup. Small trees float around and if they fit together they can be combined into a larger tree. This is, in a nutshell, the Primordial Sotq) paradigm. In the most general approach, trees can com- bine in arbitrary ways. That is, a new tree can be created from two existing trees if there is a par- tiaI overlap between the trees. The overlapping part is unified. Tree creation is nondestructive, in tim sense that a tree can be used more than once for the production of a larger tree. Or, t(~ put it in a different way, the initial soup contains an abundant amount of raw material. Thus all relevant trees can actually be created. The Primordial Soup Algorithm can be re- lined into a variety of parsing strategies by add- ing constraints, either on the allowed type of trees or on the way in which existing trees ean be combined. A parsing strategy specifies which trees will be recognizerl, without bothering to specify control and data structures that must be added in order to arrive at practical implemen- tations. For the development of parallel implementa- tions, the (initial) absence of control structure is &n :-:u'~s¢?l;~ a~'~ decisions about system architecture can be deferred to a later stage when the strategy has been fleshed out in more detail. Our specifi- cation of the Primordial Soup Algorithm allows for a systematic derivation of implementations of parsing strategies as is shown in a more detailed technical report [JPSZ]. These derivations are em'ried out within a partial order framework as introduced in [JPZ]. In the restricted space avail- able here we concentrate on the Primordial Soup Algorithm ~ a fi'amework for the specification of parsing strategies. In section 2 the l'rimordial Soup Algorithm is introduced, exemplified by a CYK-like approach. [n section …

Content truncated to 500 words