The translation of constitutent structure grammars into connectionist networks

The translation of constitutent structure into connectionist networks Helmut SCHNELLE and Roll WILKENS Sprachwissenschaftliches Institut Ruhr Universitat D-4630 Bochum 1 Germany grammars Abstract: Description of a connectionist implementation of an Earley parser. 1. Introduction We are going to describe a connectivity structure which is a quasi neuronal representation of the computational knowledge usually presented in terms of rules and algorithms. Our system provide.,; the proof that connectionist networks can represent cognitive knowledge of high complexity a fact that has recently been questioned by critics of connectionism (cp. FODOR and PYLYSHYN 1988). However, our system is of the variety of an implementational connectionism imple- menting systems, whose computational knowledge is already defined by rules - it is not a system which generates new knowledge structures through learning. More specifically, our system implements parsers for constituent structure grammars according to Earley's rules in terms of networks of Boolean operators. The implementation is automatic, i.e. executed by a compi-ler which automatically translates a grammar into a set of Boolean equations. Our connectionist net is thus like a special purpose parser network defined by the Boolean equations in the same way as any costums specific circuit definition. We shall now explain the essential ideas which characterize the parallel (connectionist) networks compiled from constituent structure rule systems through parallelizing Earley's algorithm. The formal def'mifions of the compilation algorittun and of the definition of the resulting connectionist network can be found in SCHNELLE and DOUST (1989). In the following paragraphs our essential ideas will be presented by means of a simple example, the system of constituent structure rules S °-> aA, S --> Ab, A --> aa, A -- > a to be applied in a parsing process on the string aab. 2. Earley's Representation Let us first summarize the essentials of Earley's algo-rithm. It operates in two stages: In the first stage, a parse list is computed and in the second stage the correct parse is filtered out from the parse list. For the string aab the information contained in the parse list can be represented as in figure 1 by a superposition of possible sub-trees found applicable in going through the string from left to fight. The correct parse "filtered out" is represented in figure 2. Earley uses another way of representing parse lists and correct parses. He represents them by means of dotted rule symbols and dominance scope numbers entered in ists, one for each input interval. The parse list containing the same information given in the superposifion of the trees is as in figure 3. The meaning of such a list should be clear: The SS a a b S A a a b Figure 1: Figure 2: Parse list tree Correct parse tree symbols of the input string represented at the bottom exist in the intervals <0,1>, <1,2>,<2,3>. At each completed inter- val, the rules which have found application so far are entered in the corresponding list.s, together with a number indicating the number of intervals dominated by the head symbol …

Content truncated to 500 words