A connectionist symbol manipulator that induces rewrite rules in context-free grammars

A connectionist architecture is described that is able to learn to parse strings in a context-free grammar (CFG) from positive and negative examples. The architecture attempts to learn explicit rewrite rules in a grammar, to be able to reduce (or correctly parse) positive examples. This involves the ability to iteratively substitute a single nonterminal in place of a string of symbols, that is, reduce more than one symbol to one. Since this architecture takes a left-to-right parsing strategy, it is suitable for LR grammars. Any CFG can be classified as LR(n) grammar, which means that strings can be parsed from left to right with n symbols of lookahead. The authors examine only LR(0) grammars, although the architecture can be generalized to any n